Recurrence relation
In mathematics, a recurrence relation is an equation according to which the {\displaystyle n}nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only {\displaystyle k}k previous terms of the sequence appear in the equation, for a parameter {\displaystyle k}k that is independent of {\displaystyle n}n; this number {\displaystyle k}k is called the order of the relation. If the values of the first {\displaystyle k}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 {\displaystyle k}k previous terms. A famous example is the recurrence for the Fibonacci numbers,
{\displaystyle F_{n}=F_{n-1}+F_{n-2}}{\displaystyle F_{n}=F_{n-1}+F_{n-2}}
where the order {\displaystyle k}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 {\displaystyle n}n. For these recurrences, one can express the general term of the sequence as a closed-form expression of {\displaystyle n}n. As well, linear recurrences with polynomial coefficients depending on {\displaystyle n}n are also important, because many common elementary 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 {\displaystyle n}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.