Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence
Basis: When , . So, the solution holds for the initial step.
Inductive Step: Let’s assume that there exists a , greater than 1, such that . We must prove that the formula holds for too, i.e. .
From our recurrence formula,
This completes the inductive step.
Since both the basis and the inductive step have been performed, by mathematical induction, the statement holds for all that are exact power of 2.