problem with mathematical induction problem

[xytor]

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

T(n)=
{2 if n=2
{2T(n/2)+n if n=2^k, for k>1

is T(n)=nlg(n)

Well, obviously the base case is T(2) = 2
and we can also say that:
T(2^k) = 2T(2^(k-1))+2^k
T(2^(k-1)) = 2T(2^(k-2))+2^(k-1)
T(2^k)=2*(2T(2^(k-2))+2^(k-1))+2^k
So, we can make a general statement:
T(2^k)=2*(2*(2...(2)+2^2)+2^3)...+2^k
or
T(2^k) = 2^k(2)+SUM(i=2,k,2^k)

And that's where I'm stumped. None of that looks like a nlg(n). Have I taken a wrong turn somewhere?

[MXP]

When you use induction you assume it is true for 2^k and then you then verify using 2^(k + 1). That is work like this:

T(2) = 2 = 2 * lg(2), so it works with the base case
Assume T(2^k) = (2^k) * lg(2^k) = k(2^k)

T(2^(k + 1)) = 2 * T(2^k) + 2^(k + 1)
... show that this is (2^(k + 1)) * lg(2^(k + 1)) = (k + 1) * 2^(k + 1)

When you look at induction this way you'll see the answer comes almost immediately from the expression.

[xytor]

Ah yes, I see.
Thanks, Colin!