Recurrence relation

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

For example:

Recurrence relations can be solved in order to obtain a nonrecursive function of n. The Fibonacci numbers are defined using a recurrence relation:

and has solution (letting )

Solutions to recurrence relations are found by systematic means.

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

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

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

See also: recursion

This article is a stub. You can help Wikipedia by fixing it.