In mathematics and computer science, a recurrence relation is an equation according to which the n {\displaystyle n} th term of a sequence of numbers is equal to some combination of the previous terms. Often, only k {\displaystyle k} previous terms of the sequence appear in the equation, for a parameter k {\displaystyle k} that is independent of n {\displaystyle n} ; this number k {\displaystyle k} is called the order of the relation. If the values of the first k {\displaystyle k} numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation. In linear recurrences, the nth term is equated to a linear function of the k {\displaystyle k} previous terms. A famous example is the recurrence for the Fibonacci numbers,
F n = F n − 1 + F n − 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}}
where the order k {\displaystyle k} is two and the linear function merely adds the two previous terms. This example is a linear recurrence with constant coefficients, because the coefficients of the linear function (1 and 1) are constants that do not depend on n . {\displaystyle n.} For these recurrences, one can express the general term of the sequence as a closed-form expression of n {\displaystyle n} . As well, linear recurrences with polynomial coefficients depending on n {\displaystyle n} are also important, because many common elementary functions and special functions have a Taylor series whose coefficients satisfy such a recurrence relation (see holonomic function). Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of n {\displaystyle n} . The concept of a recurrence relation can be extended to multidimensional arrays, that is, indexed families that are indexed by tuples of natural numbers.
Definition A recurrence relation is an equation that expresses each element of a sequence as a function of the preceding ones. More precisely, in the case where only the immediately preceding element is involved, a recurrence relation has the form
u n = φ ( n , u n − 1 ) for n > 0 , {\displaystyle u_{n}=\varphi (n,u_{n-1})\quad {\text{for}}\quad n>0,}
where
φ : N × X → X {\displaystyle \varphi :\mathbb {N} \times X\to X}
is a function, where X is a set to which the elements of a sequence must belong. For any u 0 ∈ X {\displaystyle u_{0}\in X} , this defines a unique sequence with u 0 {\displaystyle u_{0}} as its first element, called the initial value. It is easy to modify the definition for getting sequences starting from the term of index 1 or higher. This defines recurrence relation of first order. A recurrence relation of order k has the form
u n = φ ( n , u n − 1 , u n − 2 , … , u n − k ) for n ≥ k , {\displaystyle u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{n-k})\quad {\text{for}}\quad n\geq k,}
where φ : N × X k → X {\displaystyle \varphi :\mathbb {N} \times X^{k}\to X} is a function that involves k consecutive elements of the sequence. In this case, k initial values are needed for defining a sequence.
Examples
Factorial The factorial is defined by the recurrence relation
n ! = n ⋅ ( n − 1 ) ! for n > 0 , {\displaystyle n!=n\cdot (n-1)!\quad {\text{for}}\quad n>0,}
and the initial condition
0 ! = 1. {\displaystyle 0!=1.}
This is an example of a linear recurrence with polynomial coefficients of order 1, with the simple polynomial (in n)
n {\displaystyle n}
as its only coefficient.
Logistic map An example of a recurrence relation is the logistic map defined by
x n + 1 = r x n ( 1 − x n ) , {\displaystyle x_{n+1}=rx_{n}(1-x_{n}),}
… excerpt ends here. Continue reading the full article.
