Namespaces
Variants
Actions

Difference between revisions of "Recursive sequence"

From Encyclopedia of Mathematics
Jump to: navigation, search
(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,\ldots,$ defined over a [[field]] $K$ that satisfies a relation
+
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}+\ldots+c_pa_n=0,
+
a_{n+p}+c_1a_{n+p-1}+\dots+c_pa_n=0,
 
\end{equation}
 
\end{equation}
where $c_1,\ldots,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$.   
+
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,\ldots,1,\ldots)$ and its left shifts.
+
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}+\ldots+c_{p-1} X + c_p\ .
+
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+\ldots$ 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)$.
+
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. Molin (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>
+
<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
This article was adapted from an original article by BSE-3 (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article