# Difference between revisions of "Recursive sequence"

(define characteristic polynomial, expand) |
m |
||

(One intermediate revision by one other user not shown) | |||

Line 2: | Line 2: | ||

''recurrent sequence'' | ''recurrent sequence'' | ||

− | A sequence $a_0,a_1,\ | + | A sequence $a_0,a_1,\dots,$ defined over a [[field]] $K$ that satisfies a relation |

\begin{equation}\label{eq:1} | \begin{equation}\label{eq:1} | ||

− | a_{n+p}+c_1a_{n+p-1}+\ | + | a_{n+p}+c_1a_{n+p-1}+\dots+c_pa_n=0, |

\end{equation} | \end{equation} | ||

− | where $c_1,\ | + | 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,\ | + | 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 | The ''characteristic polynomial'' (also, companion or auxiliary polynomial) of the recurrence is the polynomial | ||

$$ | $$ | ||

− | F(X) = X^p+c_1 X^{p-1}+\ | + | 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}. | 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+\ | + | 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)$. |

See also [[Shift register sequence]]. | See also [[Shift register sequence]]. | ||

Line 25: | Line 25: | ||

====References==== | ====References==== | ||

<table> | <table> | ||

− | <TR><TD valign="top">[a1]</TD> <TD valign="top"> A.J. van der Poorten, "Some facts that should be better known, especially about rational functions" R.A. | + | <TR><TD valign="top">[a1]</TD> <TD valign="top"> A.J. van der Poorten, "Some facts that should be better known, especially about rational functions" R.A. Mollin (ed.) , ''Number theory and applications (Proc. First Conf. Canadian Number Theory Assoc., Banff, April 1988)'' , Kluwer (1989) pp. 497–528 {{ZBL|0687.10007}}</TD></TR> |

</table> | </table> |

## Latest revision as of 16:38, 30 December 2018

*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)$.

See also Shift register sequence.

#### Comments

A good reference treating many aspects of such sequences is [a1].

#### References

[a1] | A.J. van der Poorten, "Some facts that should be better known, especially about rational functions" R.A. Mollin (ed.) , Number theory and applications (Proc. First Conf. Canadian Number Theory Assoc., Banff, April 1988) , Kluwer (1989) pp. 497–528 Zbl 0687.10007 |

**How to Cite This Entry:**

Recursive sequence.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Recursive_sequence&oldid=35993