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.