I am trying to solve a recurrence relation using summation method. I'm following along some lecture notes and I don't understand this one part below.
Given that $T(n) = 2T(n/2) + n\lg n$
setting $n = 2^k$, the above relation becomes
$$T(2^k) = 2T(2^{k-1}) + k2^k$$
I get all that except the part where $2T(2^k/2)$ became $2T(2^{k-1})$. How does that occur exactly?
Recall the quotient rule of exponents: $a^m/a^n = a^{m-n}$.
In this case, $2^k/2 = 2^k/2^1 = 2^{k-1}$.
That is: Dividing $2^k$ by $2$ cancels out one of the $k$ factors, and now you only have $k-1$ left.