Recurrence relation |
Recurrent redirects here; for the meaning of recurrent in CHR, see Recurrent rotation.
In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms.
For example (the logistic map):
:x_{n+1} = r x_n (1 - x_n) ,
Some simply defined recurrence relations can have very complex (chaotic) behaviours and are sometimes studied by physicists and mathematicians in a field of mathematics known as nonlinear analysis.
Solving a recurrence relation means obtaining a non-recursive function of n .
=Linear homogeneous recurrence relations with constant coefficients=
The term linear means that each term of the sequence is defined as a linear function of the preceding terms. The coefficients and the constants may depend on n, even non-linearly.
A special case is when the coefficients do not depend on n.
Homogeneous (mathematics) means that the constant term of the relation is zero.
In order to obtain a unique solution to the linear recurrence there must be some initial conditions, as the first number in the sequence can not depend on other numbers in the sequence and must be set to some value.
=Solving linear recurrence relations=
Solutions to recurrence relations are found by systematic means, often by using generating functions (formal power series) or by noticing the fact that r n is a solution for particular values of r .
Consider, for example, a recurrence relation of the form
:a_{n}=Aa_{n-1}+Ba_{n-2}. ,
Suppose that it has a solution of the form a_n = r^n. Substituting this guess in the recurrence relation, we find:
:r^{n}=Ar^{n-1}+Br^{n-2}. ,
Dividing through by r^{n-2} we get:
:r^2=Ar+B , :r^2-Ar-B=0 ,
This is known as the characteristic equation of the recurrence relation. Solve for r to obtain the two roots lambda_1, lambda_2 , and if these roots are distinct, we have the solution
:a_n = Clambda_1^n+Dlambda_2^n ,
while if they are identical (when A 2+4 B =0), we have
:a_n = Clambda^n+Dnlambda^n ,
where constants C and D can be found from the side conditions that are often given as a_0=a, a_1=b.
Different solutions are obtained depending on the nature of the roots of the characteristic equation.
Interestingly, the method for solving linear differential equations is similar to the method above — the intelligent guess for linear differential equations with constant coefficients is e^{lambda x} where lambda is a complex number that is determined by substituting the guess into the differential equation.
This is not a coincidence. If you consider the Taylor series of the solution to a linear differential equation:
: sum_{n=0}^{infin} frac{f^{(n)}(a)}{n!} (x-a)^{n}
you see 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:
: y^{[k]} -> f[n+k]
and more generally : x^m*y^{[k]} -> n(n-1)(n-m+1)f[n+k-m]
EXAMPLE: The recurrence relationship for the Taylor series coefficients of the equation: (x^2 + 3x -4)y^{[3]} -(3x+1)y^{[2]} + 2y = 0 is given by n(n-1)f[n+1] + 3nf[n+2] -4f[n+3] -3nf[n+1] -f[n+2]+ 2f[n] = 0 or -4f[n+3] +2nf[n+2] + n(n-4)f[n+1] +2f[n] = 0
This example shows how problems generally solved using the power series solution method taught in normal differential equation classes can be solved in a much easier way.
EXAMPLE: The differential equation ay + by +cy = 0 has solution e^{ax} .
The conversion of the differential equation to a difference equation of the Taylor coefficients is af[n+2] + bf[n+1] + cf[n] = 0.
It is easy to see that the n -th derivative of e^{ax} evaluated at 0 is a^n .
==Solving inhomogeneous recurrence relations==
If the recurrence is inhomogeneous, a particular solution can be found by the method of undetermined coefficients and the solution is the sum of the solution of the homogeneous and the particular solutions. Another method to solve an inhomogeneous recurrence is the method of symbolic differentiation . For example, consider the following recurrence:
:a_{n+1} = a_{n} + 1,
This is an inhomogeneous recurrence. If we substitute n mapsto n + 1, we obtain the recurrence
:a_{n+2} = a_{n+1} + 1,
Subtracting the original recurrence from this equation yields
:a_{n+2} - a_{n+1} = a_{n+1} - a_{n},
or equivalently
:a_{n+2} = 2 * a_{n+1} - a_{n},
This is a homogenous recurrence which can be solved by the methods explained above. In general, if a linear recurrence has the form
: a_{n+k} = lambda_{k-1}*a_{n+k-1} + lambda_{k-2}*a_{n+k-2} + cdots + lambda_1*a_{n+1} + lambda_0*a_{n} + p(n)
where lambda_0, lambda_1, cdots, lambda_{k-1} are constant coefficients and p(n) is the inhomogeneity, then if p(n) is a polynomial with degree r, then this inhomogeneous recurrence can be reduced to a homogenous recurrence by applying the method of symbolic differentiation r times.
= Example: Fibonacci numbers =
The Fibonacci numbers are defined using a linear recurrence relation:
:F_{n} = F_{n-1}+F_{n-2} , :F_{0} = 0 , :F_{1} = 1 ,
and has solution (letting Phi = {1+sqrt{5} over 2} be the golden ratio)
:F_n = {Phi^n over sqrt{5}} - {(1-Phi)^n over sqrt{5}}
The initial conditions are:
:F_{0} = 0 , :F_{1} = 1 ,
Therefore, the sequence of Fibonacci numbers is: :0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...
= Relationship to differential equations =
When solving an ordinary differential equation numerical ordinary differential equations, one typically encounters a recurrence relation. For example, when solving the initial value problem
:y (t) = f(t,y(t)), qquad y(t_0)=y_0, qquadqquad
with Euler s method and a step size h , one calculates the values y_0=y(t_0), y_1=y(t_0+h), y_2=y(t_0+2h),... by the recurrence : y_{n+1} = y_n + hf(t_n,y_n).
Systems of linear first order differential equations can be discretized exactly analytically using the methods shown in the discretization article.
=See also=
*Recursion *Lagged Fibonacci generator *Master theorem *Circle points segments proof
= External links=
|
|