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

$T(n) = \begin{cases} 2 & \text{if } n = 2, \\ 2T(n/2) + n & \text{if } n = 2^k, \text{for } k > 1. \end{cases}$

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

#### Base Case

When $$n = 2$$, $$T(2) = 2 = 2 \lg 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,

\begin{aligned} T(2^{k + 1}) & = 2T(2^{k + 1}/2) + 2^{k + 1} \\ & = 2T(2^k) + 2 \cdot 2^k \\ & = 2 \cdot 2^k \lg 2^k + 2 \cdot 2^k \\ & = 2 \cdot 2^k (\lg 2^k + 1) \\ & = 2^{k + 1} (\lg 2^k + \lg 2) \\ & = 2^{k + 1} \lg 2^{k + 1} \end{aligned}

This completes the inductive step.

Since both the base case 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.