Recurrence relation

recurrence formula

A relation of the form

$$a_{n+p}=F(n,a_n,\ldots,a_{n+p-1}),$$

permitting one to compute all members of the sequence $a_1,a_2,\ldots,$ if its first $p$ members are given. Examples of recurrence relations are: 1) $a_{n+1}=q\cdot a_n$ $(q\neq0)$, a geometric progression; 2) $a_{n+1}=a_n+d$, an arithmetic progression; 3) $a_{n+2}=a_{n+1}+a_n$, the sequence of Fibonacci numbers.

In the case where the recurrence relation is linear (see Recursive sequence) the problem of describing the set of all sequences that satisfy a given recurrence relation has an analogy with solving an ordinary homogeneous linear differential equation with constant coefficients.

References

[1]	A.I. Markushevich, "Rekursive Folgen" , Deutsch. Verlag Wissenschaft. (1973) (Translated from Russian)

Comments

A sequence of elements $\alpha_0,\alpha_1,\ldots,$ of a commutative ring $R$ with a unit element satisfies a linear recurrence relation $\alpha_n=p_1\alpha_{n-1}+\ldots+p_m\alpha_{n-m}$, $n\geq m$, if and only if the formal power series $\alpha(x)=\alpha_0+\alpha_1x+\ldots$ is a rational function of the form $\alpha(x)=p(x)/q(x)$, with $p(x)=1-p_1x-\ldots-p_mx^m$ and $q(x)$ a polynomial of degree $\leq m-1$.