2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Induction works here as everywhere else. $\endgroup$ – Raphael Oct 20 '16 at 9:09
2
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.