# Recursive sequence

recurrent sequence

A sequence $a_0,a_1,\dots,$ defined over a field $K$ that satisfies a relation \begin{equation}\label{eq:1} a_{n+p}+c_1a_{n+p-1}+\dots+c_pa_n=0, \end{equation} where $c_1,\dots,c_p$ are constants. The relation permits one to compute the terms of the sequence one by one, in succession, if the first $p$ terms are known. A classical example of such a sequence is the sequence of Fibonacci numbers $1,1,2,3,5,8$ defined by $a_{n+2}=a_{n+1}+a_n$ with $a_0=0$, $a_1=1$.

The sequences satisfying satisfying \eqref{eq:1} form a vector space over $K$ of dimension $p$ with basis given by the impulse response sequence $(0,0,\dots,1,\dots)$ and its left shifts.

The characteristic polynomial (also, companion or auxiliary polynomial) of the recurrence is the polynomial $$F(X) = X^p+c_1 X^{p-1}+\dots+c_{p-1} X + c_p\ .$$ It is the characteristic polynomial of the left shift operator acting on the space of all sequences. If $\alpha$ is a root of $F$, then the sequence $(\alpha^n)$ satisfies \eqref{eq:1}.

A recursive series is a power series $a_0+a_1x+a_2x^2+\dots$ whose coefficients form a recursive sequence. Such a series represents an everywhere-defined rational function: its denominator is the reciprocal polynomial $X^p F(1/X)$.