In mathematics, a recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given: each further term of the sequence or array is defined as a function of the preceding terms.

The term difference equation sometimes (and for the purposes of this article) refers to a specific type of recurrence relation. However, "difference equation" is frequently used to refer to any recurrence relation.

Examples

Logistic map

An example of a recurrence relation is the logistic map:

with a given constant r; given the initial term x₀ each subsequent term is determined by this relation.

Some simply defined recurrence relations can have very complex (chaotic) behaviours, and they are a part of the field of mathematics known as nonlinear analysis.

Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of n.

Fibonacci numbers

The Fibonacci numbers are the archetype of a linear, homogeneous recurrence relation with constant coefficients (see below). They are defined using the linear recurrence relation