Prove correctess of recurrence result by mathematical induction

Question

I have the following recurrence relation which I already solved using repeated substitution.

$T(n) = \begin{Bmatrix} 1 & if & n = 1\\ 4T(\frac{n}2) + n & if & n >= 2 \end{Bmatrix} where$ $n=2^k$

The result I get is $T(n) = 2n^2 - n$
Let´s suppose my result is correct. Now, I am asked to prove the correctness of the result using mathematical induction.

Base case is easy:
For $n = 1$ we have $T(1) = 2(1^2) - 1 = 2 - 1 = 1$
This result agrees with initial formulation of the problem above.

Now, comes the $Inductive$ $Hypothesis$ which I guess is as follows:
Assume this holds for $2 <= k <= n$
$4T(\frac{k+1}2) + (k+1) = 2(k+1)^2 - (k+1)$

Am I doing things correctly?
How would the $Induction$ $Step$ would be?
I will very much appreciate your feedback.

Answer 1

We prove by induction that for every $n\in\mathbb{N}$ it holds that $T(n)=2n^2-n$. The inductive hypothesis is that for all $1\le k<n$ we have:

$T(k)=2k^2-k$.

We proceed to show that $T(n)=2n^2-n$.

By definition, $T(n)=4T\left(\frac{n}{2}\right)+n$. Since $\frac{n}{2}<n$, we can use our inductive hypothesis and obtain $T\left(\frac{n}{2}\right)=2\left(\frac{n}{2}\right)^2-\frac{n}{2}$. After substituting this back into $T(n)$ we have:

$T(n)=4\left(\frac{n^2}{2}-\frac{n}{2}\right)+n=2n^2-n$.

Answer 2

In another "form". First we state an inductive hypothesis: $$\forall 1 \le k \quad T(k) = 2k^2 - k$$

So we have to prove that: $$T(k + 1) = 2(k+1)^2 - (k + 1) $$

So: $$\begin{align} T(k + 1) &= 4T\left(\frac{k+1}{2}\right) + (k + 1)\\ &\stackrel{by \, IH }{=} 4\left[2\left(\frac{k+1}{2}\right)^2 - \frac{k + 1}{2}\right] + (k + 1)\\ &= 4\left(\frac{k^2 +1 + 2k}{2} - \frac{k + 1}{2}\right) + (k + 1)\\ &= 2(k + 1)^2 -2k - 2 +k + 1\\ &= 2(k+1)^2 - (k + 1) \end{align}$$