Recurrence relation

In mathematics, a recurrence relation is an equation that expresses the nth term of a sequence as a function of the k preceding terms, for some fixed k (independent from n), which is called the order of the relation. Once k initial terms of a sequence are given, the recurrence relation allows computing recursively all terms of the sequence.

Most general results on recurrence relations are about linear recurrences, which are recurrence relations such that the nth term is linear with respect to its preceding terms. Among them, linear recurrences with constant coefficients, and linear recurrences with polynomial coefficients are especially important. In the first case, this is because one can express the general term of the sequence as a closed-form expression of the index of the term. In the second case, this is because many common elementary and special functions have a Taylor series whose coefficients satisfy such a recurrence relation (see holonomic function).

The concept can be extended to multidimensional arrays, that is, indexed families that are indexed by tuples of natural numbers.