Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence

is

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.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.