previous terms of the sequence appear in the equation, for a parameter
Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of
A recurrence relation is an equation that expresses each element of a sequence as a function of the preceding ones.
[1] It is easy to modify the definition for getting sequences starting from the term of index 1 or higher.
In this case, k initial values are needed for defining a sequence.
The factorial 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 (in n) as its only coefficient.
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
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 factorials, multiplication and division, not just additions: The binomial coefficients can also be computed with a uni-dimensional recurrence: with the initial value
and is defined, in functional notation, as It is thus a special case of finite difference.
A simple computation shows that More generally: the kth difference is defined recursively as
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.
[2] Moreover, for the general first-order non-homogeneous linear recurrence relation with variable coefficients: there is also a nice method to solve it:[3] Let Then If we apply the formula to
Many homogeneous linear recurrence relations may be solved by means of the generalized hypergeometric series.
For example, the solution to is given by the Bessel function, while is solved by the confluent hypergeometric series.
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, rational or hypergeometric solutions.
, has the characteristic equation The recurrence is stable, meaning that the iterates converge asymptotically to a fixed value, if and only if the eigenvalues (i.e., the roots of the characteristic equation), whether real or complex, are all less than unity in absolute value.
is smaller than unity in absolute value: that is, A nonlinear recurrence could have multiple fixed points, in which case some fixed points may be locally stable and others locally unstable; for continuous f two adjacent fixed points cannot both be locally stable.
Such a cycle is stable, meaning that it attracts a set of initial conditions of positive measure, if the composite function with
When solving an ordinary differential equation numerically, one typically encounters a recurrence relation.
For example, when solving the initial value problem with Euler's method and a step size
Some of the best-known difference equations have their origins in the attempt to model population dynamics.
In this context, coupled difference equations are often used to model the interaction of two or more populations.
Integrodifference equations are a form of recurrence relation important to spatial ecology.
[4][5] If an algorithm is designed so that it will break a problem into smaller subproblems (divide and conquer), its running time is described by a recurrence relation.
A simple example is the time an algorithm takes to find an element in an ordered vector with
They thus arise in infinite impulse response (IIR) digital filters.
controls how much of the delayed signal is fed back into the output.
The model would then be solved for current values of key variables (interest rate, real GDP, etc.)