Gradient

Article

August 8, 2022

A recurrence relation in mathematics is an equation that recursively determines a sequence in the sense that each term is determined as a function of the terms before it. A class of recurrence equations is often called a difference equation. Also, the term "difference equation" is often treated simply as synonymous with "recurrence formula". As an example of a recurrence formula, the logistic map x n + 1 r x n ( 1 − x n ) {\displaystyle x_{n+1}rx_{n}(1-x_{n})} is mentioned. Such simple recurrence formulas often exhibit very complex (chaotic) behavior, and research on such phenomena forms a field called nonlinear analysis. . Solving a recursion means obtaining a closed form expression that expresses the general term as a non-recursive function with respect to index n.

Simple example

The Fibonacci sequence is a linear recurrence formula F. n F. n − 1 + F. n − 2 {\displaystyle F_{n}F_{n-1}+F_{n-2}} to the initial value, F. 0 : 0 , F. 1 : 1 {\displaystyle F_{0}:0,\ F_{1}:1} obtained by giving This recurrence formula can be written explicitly as F. 2 F. 1 + F. 0 , F. 3 F. 2 + F. 1 , F. Four F. 3 + F. 2 , … {\displaystyle F_{2}F_{1}+F_{0},\ F_{3}F_{2}+F_{1},\ F_{4}F_{3}+F_{2}, \dots } is the same as an infinite number of expressions such as If we write the beginning of the Fibonacci sequence obtained in this way, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Solving the recurrence formula in the manner described below yields a closed formula using two roots of the characteristic polynomial (proper polynomial) t2 - t - 1 . The generating function of the Fibonacci sequence is t 1 − t − t 2 {\displaystyle {\frac {t}{1-t-t^{2}}}} is a rational expression.

structure

Constant Coefficient Homogeneous Linear Recurrence Formula

A d-order homogeneous linear recurrence of constant coefficients is generally a n c 1 a n − 1 + c