information:filtering
In mathematics, 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 n th 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 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.