Recurrence relation

A recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively.

For example:

These simply defined recurrence relations can have very complex (chaotic) behaviours and are often studied by physicists and mathematician 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 )

The term linear simply means the coefficients of the recursively defined variables (e.g. x_n) is a constant, not another variable. 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:

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:

we make a intelligent guess, or Ansatz, that the solution is to be in the form rⁿ, and we obtain

Dividing through by we get:

This is known as the characteristic equation of the recurrence relation. Solve for r to obtain the two roots , and if these roots are distinct, we have the solution

where C and D are constants.

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 e^x.