, a recurrence relation is an equation
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.
A ''recurrence relation'' is an equation that expresses each element of a sequence
as a function of the preceding ones. More precisely, in the case where only the immediately preceding element is involved, a recurrence relation has the form
is a function, where is a set to which the elements of a sequence must belong. For any
, this defines a unique sequence with
as its first element, called the ''initial value''.
It is easy to modify the definition for getting sequences starting from the term of index 1 or higher.
This defines recurrence relation of ''first order''. A recurrence relation of ''order'' has the form
is a function that involves consecutive elements of the sequence.
In this case, initial values are needed for defining a sequence.
is defined by the recurrence relation
and the initial condition
An example of a recurrence relation is the logistic map
with a given constant ''r''; given the initial term ''x''0
each subsequent term is determined by this relation.
Solving a recurrence relation means obtaining a closed-form solution
: a non-recursive function of ''n''.
The recurrence of order two satisfied by the Fibonacci number
s is the archetype of a homogeneous linear recurrence
relation with constant coefficients (see below). The Fibonacci sequence is defined using the recurrence
with initial condition
s (seed values)
Explicitly, the recurrence yields the equations
We obtain the sequence of Fibonacci numbers, which begins
:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
The recurrence can be solved by methods described below yielding Binet's formula
, which involves powers of the two roots of the characteristic polynomial ''t''2
= ''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 coefficient
, 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
with the base cases
. Using this formula to compute the values of all binomial coefficients generates an infinite array called Pascal's triangle
. The same values can also be computed directly by a different formula that is not a recurrence, but that requires multiplication and not just addition to compute:
Relationship to difference equations narrowly defined
Given an ordered sequence
of real numbers
: the first difference
is defined as
The second difference
is defined as
which can be simplified to
More generally: the ''k''-th difference of the sequence ''an
'' written as
is defined recursively as
(The sequence and its differences are related by a binomial transform
.) The more restrictive definition of difference equation is an equation composed of ''an
'' and its ''k''th
differences. (A widely used broader definition treats "difference equation" as synonymous with "recurrence relation". See for example rational difference equation
and matrix difference equation
Actually, it is easily seen that,
Thus, a difference equation can be defined as an equation that involves
etc. (or equivalently
Since difference equations are a very common form of recurrence, some authors use the two terms interchangeably. For example, the difference equation
is equivalent to the recurrence relation
Thus one can solve many recurrence relations by rephrasing them as difference equations, and then solving the difference equation, analogously to how one solves ordinary differential equations
. However, the Ackermann number
s are an example of a recurrence relation that do not map to a difference equation, much less points on the solution to a differential equation.
See time scale calculus
for a unification of the theory of difference equations with that of differential equations
s relate to difference equations as integral equation
s relate to differential equations.
From sequences to grids
Single-variable or one-dimensional recurrence relations are about sequences (i.e. functions defined on one-dimensional grids). Multi-variable or n-dimensional recurrence relations are about n-dimensional grids. Functions defined on n-grids can also be studied with partial difference equations.
Solving homogeneous linear recurrence relations with constant coefficients
Roots of the characteristic polynomial
An order-''d'' homogeneous linear recurrence with constant coefficients is an equation of the form
where the ''d'' coefficients ''ci
'' (for all ''i'') are constants, and
A constant-recursive sequence
is a sequence satisfying a recurrence of this form. There are ''d'' degrees of freedom
for solutions to this recurrence, i.e., the initial values
can be taken to be any values but then the recurrence determines the sequence uniquely.
The same coefficients yield the characteristic polynomial
(also "auxiliary polynomial")
whose ''d'' roots play a crucial role in finding and understanding the sequences satisfying the recurrence. If the roots ''r''1
, ... are all distinct, then each solution to the recurrence takes the form
where the coefficients ''ki
'' are determined in order to fit the initial conditions of the recurrence. When the same roots occur multiple times, the terms in this formula corresponding to the second and later occurrences of the same root are multiplied by increasing powers of ''n''. For instance, if the characteristic polynomial can be factored as (''x''−''r'')3
, with the same root ''r'' occurring three times, then the solution would take the form
As well as the Fibonacci number
s, other constant-recursive sequences include the Lucas number
s and Lucas sequence
s, the Jacobsthal number
s, the Pell number
s and more generally the solutions to Pell's equation
For order 1, the recurrence
has the solution ''an
'' = ''rn
'' with ''a''0
= 1 and the most general solution is ''an
'' = ''krn
'' with ''a''0
= ''k''. The characteristic polynomial equated to zero (the characteristic equation
) is simply ''t'' − ''r'' = 0.
Solutions to such recurrence relations of higher order are found by systematic means, often using the fact that ''an
'' = ''rn
'' is a solution for the recurrence exactly when ''t'' = ''r'' is a root of the characteristic polynomial. This can be approached directly or using generating function
s (formal power series
) or matrices.
Consider, for example, a recurrence relation of the form
When does it have a solution of the same general form as ''an
'' = ''rn
''? Substituting this guess (ansatz
) in the recurrence relation, we find that
must be true for all ''n'' > 1.
Dividing through by ''r''''n''−2
, we get that all these equations reduce to the same thing:
which is the characteristic equation of the recurrence relation. Solve for ''r'' to obtain the two roots ''λ''1
: these roots are known as the characteristic root
s or eigenvalues of the characteristic equation. Different solutions are obtained depending on the nature of the roots: If these roots are distinct, we have the general solution
while if they are identical (when ), we have
This is the most general solution; the two constants ''C'' and ''D'' can be chosen based on two given initial conditions ''a''0
to produce a specific solution.
In the case of complex eigenvalues (which also gives rise to complex values for the solution parameters ''C'' and ''D''), the use of complex numbers can be eliminated by rewriting the solution in trigonometric form. In this case we can write the eigenvalues as
Then it can be shown that
can be rewritten as
Here ''E'' and ''F'' (or equivalently, ''G'' and δ) are real constants which depend on the initial conditions. Using
one may simplify the solution given above as
are the initial conditions and
In this way there is no need to solve for λ1
In all cases—real distinct eigenvalues, real duplicated eigenvalues, and complex conjugate eigenvalues—the equation is stable
(that is, the variable ''a'' converges to a fixed value pecifically, zero
if and only if ''both'' eigenvalues are smaller than one in absolute value
. In this second-order case, this condition on the eigenvalues can be shown to be equivalent to |''A''| < 1 − ''B'' < 2, which is equivalent to |''B''| < 1 and |''A''| < 1 − ''B''.
The equation in the above example was homogeneous
, in that there was no constant term. If one starts with the non-homogeneous recurrence
with constant term ''K'', this can be converted into homogeneous form as follows: The steady state
is found by setting ''bn
'' = ''b''''n''−1
= ''b''* to obtain
Then the non-homogeneous recurrence can be rewritten in homogeneous form as
which can be solved as above.
The stability condition stated above in terms of eigenvalues for the second-order case remains valid for the general ''n''th
-order case: the equation is stable if and only if all eigenvalues of the characteristic equation are less than one in absolute value.
Given a homogeneous linear recurrence relation with constant coefficients of order ''d'', let ''p''(''t'') be the characteristic polynomial
(also "auxiliary polynomial")
such that each ''ci
'' corresponds to each ''ci
'' in the original recurrence relation (see the general form above). Suppose λ is a root of ''p''(''t'') having multiplicity
''r''. This is to say that (''t''−λ)''r''
divides ''p''(''t''). The following two properties hold:
# Each of the ''r'' sequences
satisfies the recurrence relation.
# Any sequence satisfying the recurrence relation can be written uniquely as a linear combination of solutions constructed in part 1 as ''λ'' varies over all distinct roots of ''p''(''t'').
As a result of this theorem a homogeneous linear recurrence relation with constant coefficients can be solved in the following manner:
# Find the characteristic polynomial ''p''(''t'').
# Find the roots of ''p''(''t'') counting multiplicity.
# Write ''an
'' as a linear combination of all the roots (counting multiplicity as shown in the theorem above) with unknown coefficients ''bi
#:This is the general solution to the original recurrence relation. (''q'' is the multiplicity of λ*
# Equate each
from part 3 (plugging in ''n'' = 0, ..., ''d'' into the general solution of the recurrence relation) with the known values
from the original recurrence relation. However, the values ''an
'' from the original recurrence relation used do not usually have to be contiguous: excluding exceptional cases, just ''d'' of them are needed (i.e., for an original homogeneous linear recurrence relation of order 3 one could use the values ''a''0
). This process will produce a linear system of ''d'' equations with ''d'' unknowns. Solving these equations for the unknown coefficients
of the general solution and plugging these values back into the general solution will produce the particular solution to the original recurrence relation that fits the original recurrence relation's initial conditions (as well as all subsequent values
of the original recurrence relation).
The method for solving linear differential equations
is similar to the method above—the "intelligent guess" (ansatz
) for linear differential equations with constant coefficients is ''e''λ''x''
where λ is a complex number that is determined by substituting the guess into the differential equation.
This is not a coincidence. Considering the Taylor series
of the solution to a linear differential equation:
it can be seen that the coefficients of the series are given by the ''n''th
derivative of ''f''(''x'') evaluated at the point ''a''. The differential equation provides a linear difference equation relating these coefficients.
This equivalence can be used to quickly solve for the recurrence relationship for the coefficients in the power series solution of a linear differential equation.
The rule of thumb (for equations in which the polynomial multiplying the first term is non-zero at zero) is that: