Consider the following recurrence relation:
$T(1) = 1$
$T(n) = 2T(\frac{n}{2}) + n$
I suspect that $T(n) = n + n\log_2 n$. Using mathematical induction, the base case holds since $T(1) = 1$. The inductive step seems a little complicated: how to prove $T(k+1)$ holds assuming $T(k)$ is true for $k\geq1$?
Any help is appreciated.
Best Answer
Another way to write your suspected formula is $T\left(2^k\right) = 2^k(k+1)$.
When $k=0$, we have $T(1) = 1$ so that's okay.
Now, assuming the formula holds for $k$, we would have by the recurrence relationship that
\begin{align} T\left(2^{k+1}\right) &= 2T\left(2^k\right) + 2^{k+1} \\&= 2\left(2^k(k+1)\right)+2^{k+1} \\&= 2^{k+1}(k+1)+2^{k+1} \\&= 2^{k+1}(k+2) \end{align}
which agrees with the suspected formula. So by induction, the suspected formula is correct.
Notice, however, that it is only defined for powers of $2$. This is because the recurrence relation itself is not defined for other integers.