University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions and Graphs: Decision Trees and Recursion"

Read from example 27 to the end of the chapter on pages DT-46 - DT-50

A solution to a recursive equation is a formula that computes A(n) without having to compute A(k), for k < n. Review the section on "Recursive Equations," on page DT-44 up to example 26 on page DT-46.

1. A solution to a recursive equation can be found by inspection of the terms of a given sequence (example 27); OR
2. Apply theorem 8 if A(n) depends on A(n - 1) and theorem 9, if A(n) depends on A(n - 1) and A(n - 2).

Regarding Theorem 8 on page DT-48, if an = ban - 1 +c , then iterating, an = b( ban - 2+c) + c = b(b (b an - 3+ c ) + c ) + c= ....= a0 bn + c bn-1 + c bn-2 + .... + c. This is an example of using the method of iteration for finding a formula for a recurrence relation for an arithmetic sequence.

Click https://s3.amazonaws.com/saylordotorg-resources/wwwresources/site/wp-content/uploads/2011/09/CS202-Decision-Trees-and-Recursion-DT-Edward-Bender.pdf link to open resource.