|
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:
-
These simply defined recurrence relations can have very complex (chaotic) behaviours and are often studied by physicists and
mathematicians in a field of mathematics known as nonlinear analysis.
Linear homogeneous recurrence relations
Recurrence relations, particular linear recurrence relations, can be solved in order to obtain a non-recursive
function of n. The Fibonacci numbers are defined using a
linear recurrence relation:
-
-
-
and has solution (letting be the golden ratio)
-
The term linear simply means the coefficients of the recursively
defined variables (e.g. xn) is a constant, not another variable and hence do not depend on
x. Linear recurrence relations must have 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.
In the above example of Fibonacci numbers, the initial conditions are:
-
-
Therefore, the sequence of Fibonacci numbers is:
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...
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 rn
is a solution for particular values of r.
For recurrence relations in the form:
-
we have the solution rn:
-
Dividing through by rn - 2 we get:
-
-
This is known as the characteristic equation of the recurrence relation. Solve for r to obtain the two roots
λ1,λ2, and if these roots are distinct, we have the solution
-
while if they are identical (when A2+4B=0), we have
-
where C and D are constants.
Additionally, if the equation is of the form an = Aan
- 1 + B you can substitute 2 for n and get r2 =
Ar + B as above. The constants C and D can be found from the "side conditions" that
are often given as a0 = a,a1 = b
Different solutions are obtained depending on the nature of the roots of the characteristic equation.
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.
Interestingly, the method for solving linear differential equations is similar to the method above - the "intelligent guess" for linear
differential equations is ex.
This is not a coincidence. If you consider the Taylor series of the
solution to a linear differential equation:
-
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.
See also:
|