Recurrence by substitution

Question

I do not really get how we get from $2T(2^k) + (2^{k+1})$ to $2T(2^k \log 2^k) + (2^{k+1})$

Answer 1

By hypothesis, we know that $T(n)=n\log n$ for $n=2^k$ i.e., $T(2^k)=2^k\log 2^k$

So, substituting this value of $T(2^k)$ on the equation

$2T(2^k) + (2^{k+1})$

gives

$2(2^k log 2^k) + (2^{k+1})$

Answer 2

By the inductive hypothesis, if $n = 2^k$ then $T(n) = n\log n$ hence $T(2^k) = 2^k \log 2^k$.