A recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively.
For example:
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:
In the above example of Fibonacci numbers, the initial conditions are:
- 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 an intelligent guess based on intuition.For recurrence relations in the form:
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.
See also: recursion