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(\frac{n}{2}) + n & \text{if $n=2^k$ for $k>1$} \\ \end{cases}\]

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

In the base case, \(k = 1\), and so \(n = 2^1\). \(T(n) = n \lg n = 2 \lg(2^1) = 2\).

Next we suppose this holds for any \(k > 1\), and will show that it also holds for any \(k + 1\):

\[\begin{equation} \label{eq1} \begin{split} T(\frac{n}{2}) + n & = n \lg n \\ 2\frac{2^{k+1}}{2} \lg\frac{2^{k+1}}{2} + 2^{k+1} & = 2^{k+1} \lg 2^{k+1} \\ 2\frac{2^{k+1}}{2} (\lg 2^{k+1} - \lg 2) + 2^{k+1} & = 2^{k+1}(k+1) \\ 2\frac{2^{k+1}}{2} (k + 1 - 1) + 2^{k+1} & = 2^{k+1}(k+1) \\ 2^{k+1}k +2^{k+1} & = 2^{k+1}(k+1) \\ 2^{k+1}(k+1) & = 2^{k+1}(k+1) \\ \end{split} \end{equation}\]