I've been having trouble with an assignment I received with the course I am following. The assignment in question:
Use induction to prove that when $n \geq 2$ 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, k > 1 \\
\end{cases}
$$
is $T(n) = n\log(n)$
NOTE: the logarithms in the assignment have base $2$.
The base case here is obvious, when $n = 2$, we have that $2 = 2\log(2)$. However, I am stuck on the step here and I am not sure how to solve this.
Best Answer
Let $T(n)=n\log{n}$, here $n=2^k$ for some k. Then I guess we have to show that equality holds for $k+1$, that is $2n=2^{k+1}$. $T(2n)=2T(n)+2n=2n\log{n}+2n=2n(\log{n}+1)=2n\log{2n}$