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

is $T(n) = n\lg n$

Basis: When $n = 2$, $T(2) = 2 \times \lg 2 = 2$. So, the solution holds for the initial step.

Inductive Step: Let’s assume that there exists a $k$, greater than 1, such that $T(2^k) = 2^k \lg 2^k$. We must prove that the formula holds for $k + 1$ too, i.e. $T(2^{k + 1}) = 2^{k + 1} \lg 2^{k + 1}$.

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 $T(n) = n\lg n$ holds for all $n$ that are exact power of 2.