Namespaces
Variants
Actions

Difference between revisions of "Recurrence relation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
 +
{{TEX|done}}
 
''recurrence formula''
 
''recurrence formula''
  
 
A relation of the form
 
A relation of the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r0801501.png" /></td> </tr></table>
+
$$a_{n+p}=F(n,a_n,\ldots,a_{n+p-1}),$$
  
permitting one to compute all members of the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r0801502.png" /> if its first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r0801503.png" /> members are given. Examples of recurrence relations are: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r0801504.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r0801505.png" />, a [[Geometric progression|geometric progression]]; 2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r0801506.png" />, an [[Arithmetic progression|arithmetic progression]]; 3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r0801507.png" />, the sequence of [[Fibonacci numbers|Fibonacci numbers]].
+
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.
 
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.
Line 15: Line 16:
  
 
====Comments====
 
====Comments====
A sequence of elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r0801508.png" /> of a commutative ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r0801509.png" /> with a unit element satisfies a linear recurrence relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r08015010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r08015011.png" />, if and only if the formal power series <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r08015012.png" /> is a rational function of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r08015013.png" />, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r08015014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r08015015.png" /> a polynomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080150/r08015016.png" />.
+
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$.

Revision as of 13:34, 15 August 2014

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

How to Cite This Entry:
Recurrence relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Recurrence_relation&oldid=32959
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article