Recurrence relation

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