# Recurrence relation

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

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