Namespaces
Variants
Actions

Difference between revisions of "Recurrence relation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX)
m (dots)
 
Line 4: Line 4:
 
A relation of the form
 
A relation of the form
  
$$a_{n+p}=F(n,a_n,\ldots,a_{n+p-1}),$$
+
$$a_{n+p}=F(n,a_n,\dotsc,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]].
+
permitting one to compute all members of the sequence $a_1,a_2,\dotsc,$ 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 16: Line 16:
  
 
====Comments====
 
====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$.
+
A sequence of elements $\alpha_0,\alpha_1,\dotsc,$ of a commutative ring $R$ with a unit element satisfies a linear recurrence relation $\alpha_n=p_1\alpha_{n-1}+\dotsb+p_m\alpha_{n-m}$, $n\geq m$, if and only if the formal power series $\alpha(x)=\alpha_0+\alpha_1x+\dotsb$ is a rational function of the form $\alpha(x)=p(x)/q(x)$, with $p(x)=1-p_1x-\dotsb-p_mx^m$ and $q(x)$ a polynomial of degree $\leq m-1$.

Latest revision as of 13:04, 14 February 2020

recurrence formula

A relation of the form

$$a_{n+p}=F(n,a_n,\dotsc,a_{n+p-1}),$$

permitting one to compute all members of the sequence $a_1,a_2,\dotsc,$ 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,\dotsc,$ of a commutative ring $R$ with a unit element satisfies a linear recurrence relation $\alpha_n=p_1\alpha_{n-1}+\dotsb+p_m\alpha_{n-m}$, $n\geq m$, if and only if the formal power series $\alpha(x)=\alpha_0+\alpha_1x+\dotsb$ is a rational function of the form $\alpha(x)=p(x)/q(x)$, with $p(x)=1-p_1x-\dotsb-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