# Proving a recurrence relation with induction

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.

-
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}$
Thank you, that makes complete sense. Did not think about taking 2n, I was instead messing around with the $2^{k+1}$. Just a slight note: My question was tagged with homework, which would mean that you are not supposed to give the answer but instead give hints/tips. –  Ruddie Feb 12 '12 at 11:45
No problem, the answer did help. And once I saw you took 2n instead of $2^{k+1}$ I figured it out myself. –  Ruddie Feb 12 '12 at 11:51