Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 4

In this chapter, the author defines recurrence and provides three methods namely, substitution method, recursion-tree method and and master method to solve recurrences.

The substitution method relies on guessing the solution and then proving it with mathematical induction. The author provides following hints to prove the solution if the mathematical induction doesn't work out:

1. Subtracting a lower order term
2. Change of variables

In a recursion tree, each node represents the cost of a single sub-problem somewhere in the set of recursive function invocations. The sum of costs within each level gives a per-level cost and the sum of all the per-level costs will give the total cost of all levels of the recursion. Recursion tree is used to get the best guess which is then verified by the substitution method. The authors then provide an example of a recurrence relation and derive the solution and prove it using substitution method.

The master method depends on the master theorem which is defined as follows:
Let and be constants, let be a function, and let be defined on the non-negative integers by the recurrence
,
where is either or . Then can be bounded asymptotically as follows:

1. If for some constant , then .
2. If , then .
3. If for some constant , and if for some constant and all sufficiently large , then . The three cases do not cover all the possibilities of . In case 1, must be polynomially smaller than and in case 3, must be polynomially larger than . Thus if is smaller than but not polynomially or if is larger than but not polynomially or if the conditions in case 3 does not get satisfied, master method cannot be used to solve the recurrence. The authors then provide examples for each type of case and find solutions. The authors then prove master theorem.