In Lecture $6,$ we guessed that the recurrence equation

$T(n)=\{\begin{array}{ccc}0& if& n=0\\ 3T(n2)+n& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}& \end{array}$

has a solution $T(2^k)=3^{k+1}-2^{k+1},$ when $n=2^k$ and $n>1$ However, we still need to verify this. Use

mathematical induction to verify that the solution $T(2^k)=3^{k+1}-2^{k+1}$ holds for all $k.[25$ points$]$