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

$T(n)=\{\begin{array}{cc}2,& n=2\\ 2T(\frac{n}{2})+n,& n=2^k,\text{f}\text{o}\text{r}& k>1\end{array}$

is $T(n)=nlg(n).$ Note that $lg(n)=lo{g}_2(n).$