Recurrence relation
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.
An example of a recurrence relation is the logistic map:
with a given constant r; given the initial term x0 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.
The recurrence satisfied by the Fibonacci numbers is the archetype of a homogeneous linear recurrence relation with constant coefficients (see below). The Fibonacci sequence is defined using the recurrence
with seed values
Explicitly, the recurrence yields the equations
etc.
We obtain the sequence of Fibonacci numbers, which begins
The recurrence can be solved by methods described below yielding Binet's formula, which involves powers of the two roots of the characteristic polynomial t2 = t + 1; the generating function of the sequence is the rational function
A simple example of a multidimensional recurrence relation is given by the binomial coefficients , which count the number of ways of selecting k elements out of a set of n elements. They can be computed by the recurrence relation
...
Wikipedia