I think I've proved this correctly, but I'm still a little fuzzy on some of the steps I've taken.
Base Case:
If $n = 2$,
$T(2) = 2 lg 2$
Inductive Hypothesis:
Assume that if $n = 2^k$ and $k > 1$, then $T(n) = n lg n$
Apply Axiom of Induction:
If $n = 2^{k+1}$ and $k > 1$, then:
$T(n) = 2T(\frac{2^{k+1}}{2}) + 2^{k+1}$
$= 2T(2^k) + 2^{k+1}$
$= 2(2^klg2^k) + 2^{k+1}$
$= 2^{k+1}((lg2^k) + 1)$
$= 2^{k+1}lg2^{k+1}$
How exactly does the following step work?
From:
$= 2T(2^k) + 2^{k+1}$
To:
$= 2(2^klg2^k) + 2^{k+1}$
I corrected your question so it now reads this:
How exactly does the following step work?
From:
$T(2^{k+1})= 2T(2^k) + 2^{k+1}$
To:
$= 2(2^klg2^k) + 2^{k+1}$
When written correctly like this, it should now be clear.
You are assuming that $T(2^k) = 2^k \lg(2^k)$ and this allow this to be shown for $T(2^{k+1})$.