Recurrence relation

From Encyclopedia of Mathematics
Revision as of 17:14, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

recurrence formula

A relation of the form

permitting one to compute all members of the sequence if its first members are given. Examples of recurrence relations are: 1) , a geometric progression; 2) , an arithmetic progression; 3) , 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.


[1] A.I. Markushevich, "Rekursive Folgen" , Deutsch. Verlag Wissenschaft. (1973) (Translated from Russian)


A sequence of elements of a commutative ring with a unit element satisfies a linear recurrence relation , , if and only if the formal power series is a rational function of the form , with and a polynomial of degree .

How to Cite This Entry:
Recurrence relation. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article