View source for Recurrence relation

{{TEX|done}}
''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|geometric progression]]; 2) $a_{n+1}=a_n+d$, an [[Arithmetic progression|arithmetic progression]]; 3) $a_{n+2}=a_{n+1}+a_n$, the sequence of [[Fibonacci numbers|Fibonacci numbers]].

In the case where the recurrence relation is linear (see [[Recursive sequence|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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.I. Markushevich,   "Rekursive Folgen" , Deutsch. Verlag Wissenschaft.  (1973)  (Translated from Russian)</TD></TR></table>



====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$.