5 Ways to Solve Recurrence Relations - wikiHow

5 Ways to Solve Recurrence Relations - wikiHow:

How to Solve Recurrence Relations

ArithmeticGeometricPolynomialLinearGenerating Functions

Edited by Peter, Molly, Jason, Teresa and 10 others

In trying to find a formula for some mathematical sequence, a common intermediate step is to find the n^th term, not as a function of n, but in terms of earlier terms of the sequence. For example, while it'd be nice to have a closed form function for the n^th term of the Fibonacci sequence, sometimes all you have is the recurrence relation, namely that each term of the Fibonacci sequence is the sum of the previous two terms. This article will present several methods for deducing a closed form formula from a recurrence.

Method 1 of 5: Arithmetic

1. 
   1
   Consider an arithmetic sequence such as 5, 8, 11, 14, 17, 20, ....
2. 
   2
   Since each term is 3 larger than the previous, it can be expressed as a recurrence as shown.
3. 
   3
   Recognize that any recurrence of the form a_n = a_n-1 + d is an arithmetic sequence.
4. 
   4
   Write the closed-form formula for an arithmetic sequence, possibly with unknowns as shown.
5. 
   5
   Solve for any unknowns depending on how the sequence was initialized. In this case, since 5 was the 0^th term, the formula is a_n = 5 + 3n. If instead, you wanted 5 to be the first term, you would get a_n = 2 + 3n.

'via Blog this'