# Proving recurrence relation by mathematical induction

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.

• This recurrence relation doesn't seem to tell you what, say, $T(3)$ is. – Fimpellizieri Nov 8 at 4:58
• Perhaps induct on powers of $2$? I assume that's closer to what you're looking for since you have $\log_2(n)$ instead of a floor function there (since for $n \ne 2^a$ you'll definitely not get integers). – Eevee Trainer Nov 8 at 5:03

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.

• Things are clearer now, but could you explain the first line of the inductive step, please? How do you know that $T(2^{k+1})=2T(2^k)+2^{k+1}$? – Mauricio Mendes Nov 8 at 5:15
• This is the given recurrence relationship $T(n) = 2T(n/2) + n$. – Fimpellizieri Nov 8 at 5:16
• Right, so you can use the inductive hypothesis. Thanks! – Mauricio Mendes Nov 8 at 5:18
• You're welcome! Glad to have helped. – Fimpellizieri Nov 8 at 5:19