In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a recurrence relation is an
equation
In mathematics, an equation is a formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for example, in F ...
according to which the
th term of a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
of numbers is equal to some combination of the previous terms. Often, only
previous terms of the sequence appear in the equation, for a parameter
that is independent of
; this number
is called the ''order'' of the relation. If the values of the first
numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation.
In ''linear recurrences'', the th term is equated to a
linear function of the
previous terms. A famous example is the recurrence for the
Fibonacci numbers,
where the order
is two and the linear function merely adds the two previous terms. This example is a
linear recurrence with constant coefficients
In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is linear ...
, because the coefficients of the linear function (1 and 1) are constants that do not depend on
. For these recurrences, one can express the general term of the sequence as a
closed-form expression
In mathematics, a closed-form expression is a mathematical expression that uses a finite number of standard operations. It may contain constants, variables, certain well-known operations (e.g., + − × ÷), and functions (e.g., ''n''th r ...
of
. As well,
linear recurrences with polynomial coefficients depending on
are also important, because many common elementary and
special functions have a
Taylor series
In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor ser ...
whose coefficients satisfy such a recurrence relation (see
holonomic function).
Solving a recurrence relation means obtaining a
closed-form solution: a non-recursive function of
.
The concept of a recurrence relation can be extended to
multidimensional arrays, that is,
indexed families
In mathematics, a family, or indexed family, is informally a collection of objects, each associated with an index from some index set. For example, a ''family of real numbers, indexed by the set of integers'' is a collection of real numbers, whe ...
that are indexed by
tuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
s.
Definition
A ''recurrence relation'' is an equation that expresses each element of a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
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
:
where
:
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
:
where
is a function that involves consecutive elements of the sequence.
In this case, initial values are needed for defining a sequence.
Examples
Factorial
The
factorial
In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times (n-1) \times (n-2) \ ...
is defined by the recurrence relation
:
and the initial condition
:
This is an example of a ''linear recurrence with polynomial coefficients'' of order 1, with the simple polynomial
:
as its only coefficient.
Logistic map
An example of a recurrence relation is the
logistic map
The logistic map is a polynomial mapping (equivalently, recurrence relation) of degree 2, often referred to as an archetypal example of how complex, chaotic behaviour can arise from very simple non-linear dynamical equations. The map was popula ...
:
:
with a given constant
; given the initial term
each subsequent term is determined by this relation.
Fibonacci numbers
The recurrence of order two satisfied by the
Fibonacci numbers is the canonical example of a homogeneous
linear recurrence relation with constant coefficients (see below). The Fibonacci sequence is defined using the recurrence
:
with
initial condition
In mathematics and particularly in dynamic systems, an initial condition, in some contexts called a seed value, is a value of an evolving variable at some point in time designated as the initial time (typically denoted ''t'' = 0). Fo ...
s
:
:
Explicitly, the recurrence yields the equations
:
:
:
etc.
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
; the
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary serie ...
of the sequence is the
rational function
In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be ...
:
Binomial coefficients
A simple example of a multidimensional recurrence relation is given by the
binomial coefficient
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s
, which count the ways of selecting
elements out of a set of
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 uses
factorial
In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times (n-1) \times (n-2) \ ...
s, multiplication and division, not just additions:
:
The binomial coefficients can also be computed with a uni-dimensional recurrence:
:
with the initial value
(The division is not displayed as a fraction for emphasizing that it must be computed after the multiplication, for not introducing fractional numbers).
This recurrence is widely used in computers because it does not require to build a table as does the bi-dimensional recurrence, and does involve very large integers as does the formula with factorials (if one uses
all involved integers are smaller than the final result).
Difference operator and difference equations
The is an
operator that maps
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
s to sequences, and, more generally,
functions to functions. It is commonly denoted
and is defined, in
functional notation, as
:
It is thus a special case of
finite difference.
When using the index notation for sequences, the definition becomes
:
The parentheses around
and
are generally omitted, and
must be understood as the term of index in the sequence
and not
applied to the element
Given
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
the of is
The is
A simple computation shows that
:
More generally: the ''th difference'' is defined recursively as
and one has
:
This relation can be inverted, giving
:
A of order is an equation that involves the first differences of a sequence or a function, in the same way as a
differential equation
In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, ...
of order relates the first
derivative
In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. ...
s of a function.
The two above relations allow transforming a recurrence relation of order into a difference equation of order , and, conversely, a difference equation of order into recurrence relation of order . Each transformation is the
inverse
Inverse or invert may refer to:
Science and mathematics
* Inverse (logic), a type of conditional sentence which is an immediate inference made from another conditional sentence
* Additive inverse (negation), the inverse of a number that, when a ...
of the other, and the sequences that are solution of the difference equation are exactly those that satisfies the recurrence relation.
For example, the difference equation
:
is equivalent to the recurrence relation
:
in the sense that the two equations are satisfied by the same sequences.
As it is equivalent for a sequence to satisfy a recurrence relation or to be the solution of a difference equation, the two terms "recurrence relation" and "difference equation" are sometimes used interchangeably. See
Rational difference equation and
Matrix difference equation for example of uses of "difference equation" instead of "recurrence relation"
Difference equations resemble to differential equations, and this resemblance is often used to mimic methods for solving differentiable equations to apply to solving difference equations, and therefore recurrence relations.
Summation equations relate to difference equations as
integral equations relate to differential equations. See
time scale calculus for a unification of the theory of difference equations with that of 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
-dimensional grids. Functions defined on
-grids can also be studied with partial difference equations.
Solving
Solving linear recurrence relations with constant coefficients
Solving first-order non-homogeneous recurrence relations with variable coefficients
Moreover, for the general first-order non-homogeneous linear recurrence relation with variable coefficients:
:
there is also a nice method to solve it:
:
:
:
Let
:
Then
:
:
:
:
If we apply the formula to
and take the limit
, we get the formula for first order
linear differential equation
In mathematics, a linear differential equation is a differential equation that is defined by a linear polynomial in the unknown function and its derivatives, that is an equation of the form
:a_0(x)y + a_1(x)y' + a_2(x)y'' \cdots + a_n(x)y^ = b ...
s with variable coefficients; the sum becomes an integral, and the product becomes the exponential function of an integral.
Solving general homogeneous linear recurrence relations
Many homogeneous linear recurrence relations may be solved by means of the
generalized hypergeometric series
In mathematics, a generalized hypergeometric series is a power series in which the ratio of successive coefficients indexed by ''n'' is a rational function of ''n''. The series, if convergent, defines a generalized hypergeometric function, wh ...
. Special cases of these lead to recurrence relations for the
orthogonal polynomials, and many
special function
Special functions are particular mathematical functions that have more or less established names and notations due to their importance in mathematical analysis, functional analysis, geometry, physics, or other applications.
The term is defined b ...
s. For example, the solution to
:
is given by
:
the
Bessel function
Bessel functions, first defined by the mathematician Daniel Bernoulli and then generalized by Friedrich Bessel, are canonical solutions of Bessel's differential equation
x^2 \frac + x \frac + \left(x^2 - \alpha^2 \right)y = 0
for an arbitrar ...
, while
:
is solved by
:
the
confluent hypergeometric series
In mathematics, a confluent hypergeometric function is a solution of a confluent hypergeometric equation, which is a degenerate form of a hypergeometric differential equation where two of the three regular singularities merge into an irregula ...
. Sequences which are the solutions of
linear difference equations with polynomial coefficients are called
P-recursive. For these specific recurrence equations algorithms are known which find
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
,
rational or
hypergeometric solutions.
Solving first-order rational difference equations
A first order rational difference equation has the form
. Such an equation can be solved by writing
as a nonlinear transformation of another variable
which itself evolves linearly. Then standard methods can be used to solve the linear difference equation in
.
Stability
Stability of linear higher-order recurrences
The linear recurrence of order
,
:
has the
characteristic equation
:
The recurrence is
stable
A stable is a building in which livestock, especially horses, are kept. It most commonly means a building that is divided into separate stalls for individual animals and livestock. There are many different types of stables in use today; the ...
, meaning that the iterates converge asymptotically to a fixed value, if and only if the
eigenvalues
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denote ...
(i.e., the roots of the characteristic equation), whether real or complex, are all less than
unity
Unity may refer to:
Buildings
* Unity Building, Oregon, Illinois, US; a historic building
* Unity Building (Chicago), Illinois, US; a skyscraper
* Unity Buildings, Liverpool, UK; two buildings in England
* Unity Chapel, Wyoming, Wisconsin, US; a ...
in absolute value.
Stability of linear first-order matrix recurrences
In the first-order matrix difference equation
: