This is a question from CLRS book, I have to prove that the following recurrence -:
$T(n) = 2T(n/2) + n$
is $nlog(n)$ when $n = 2^k$ and $k \gt 1$
What I have tried-:
Putting n = $2^k$
I get the following expression:
$T(2^k) = 2T(2^k/2) + 2^k$
further simplified into
$T(2^k) = 2T(2^{k-1}) + 2^k$
but then I am stuck.
I have seen proofs for this question but they all involve $k+1$ instead of using $k$, why do they do that?
I would appreciate it if I could be told what mathematical concept is used so that I can study it further.
Since you do not know, how to use mathematical induction, this proof will be made with a bit of hand waving. By using the recurrence relation for $T(n)$, $T(n/2)$ ... we obtain
$$ \begin{eqnarray} T(n) &=& n + 2T(n/2) \qquad (=\color{red}{1}\cdot n + 2^{\color{red}{1}}T(n/2^{\color{red}{1}})) \\ &=& n + 2(n/2 + 2T(n/4)) \\ &=& 2n + 4T(n/4) \qquad (=\color{red}{2}\cdot n + 2^{\color{red}{2}}T(n/2^{\color{red}{2}}))\\ &=& 2n + 4(n/4 + 2T(n/8)) \\ &=& 3n + 8T(n/8) \qquad (=\color{red}{3}\cdot n + 2^{\color{red}{3}}T(n/2^{\color{red}{3}}))\\ &=& \cdots \\ &=& \color{red}{k}\cdot n + 2^{\color{red}{k}}T(n/2^{\color{red}{k}})) \end{eqnarray} $$ When do we finish? Well, in addition to the recurrence relation, one typically specifies the initial condition that defines $T(1)$, so we will assume that we also know what is $T(1)$.
Hence, at the end $k$ has the value, such that $n/2^k = 1\Leftrightarrow n = 2^k \Leftrightarrow k =\log_2 n$. Then, the last line reads as $\log_2 n \cdot n + n \cdot T(1) = n(\log_2 n + T(1))$.
Typically, $n\in\mathbb{N}$, so this proof does not work for all numbers (what is $T(3)$?). This is the point when the induction should be used and that is why all the other proves of the similar problems use $k + 1$.
You should really learn how to use it!