
MHB Master
#1
October 8th, 2014,
15:28
Hello!!!!
I want to prove by induction, that the solution of the recurrence relation $T(n)=2T \left ( \frac{n}{2} \right )+n^2, n>1 \text{ and } T(1)=1$ is $n(2n1)$.
We have to suppose that $n=2^k, k \geq 0$, right?
Do I have to prove the solution by induction with respect to $n$ or to $k$ ?

October 8th, 2014 15:28
# ADS
Circuit advertisement

MHB Seeker
#2
October 8th, 2014,
15:39
Originally Posted by
evinda
Hello!!!!
I want to prove by induction, that the solution of the recurrence relation $T(n)=2T \left ( \frac{n}{2} \right )+n^2, n>1 \text{ and } T(1)=1$ is $n(2n1)$.
We have to suppose that $n=2^k, k \geq 0$, right?
Do I have to prove the solution by induction with respect to $n$ or to $k$ ?
Hi!!
I'd pick $k$, since $T(n)$ is not defined for all $n \in \Bbb N$.
Btw, do you really have to use induction?

MHB Master
#3
October 8th, 2014,
17:47
Thread Author
Originally Posted by
I like Serena
I'd pick $k$, since $T(n)$ is not defined for all $n \in \Bbb N$.
Btw, do you really have to use induction?
The exercise asks the following:
Solve the recurrence relation $ \displaystyle{T(n)=\left\{\begin{matrix}
1 &,n=1 \\
2T \left(\frac{n}{2} \right )+n^2 &, n>1
\end{matrix}\right.}$
and then, prove that the solution you found is right, using mathematical induction.
So, do we have to do it like that?
We suppose that $n=2^k, k \geq 0$.
 $k=0 \Rightarrow n=1: T(1)=1=1\cdot (2 \cdot 11) \checkmark$
$$$$  We suppose that the relation stands for any $k>1$, so $T(2^k)=2^k(2^{k+1}1)$
$$$$  We will show that the relation stands for $k+1$.
$$T(2^{k+1})=2T \left (\frac{2^{k+1}}{2} \right )+(2^{k+1})^2=2T(2^k)+2^{2k+2}=2 (2^k(2^{k+1}1))+2^{2k+2}\\ =2^{2k+2}2^{k+1}+2^{2k+2}=2^{k+1}(2 \cdot 2^{k+1}1)$$

MHB Seeker
#4
October 8th, 2014,
17:58
Originally Posted by
evinda
The exercise asks the following:
Solve the recurrence relation $ \displaystyle{T(n)=\left\{\begin{matrix}
1 &,n=1 \\
2T \left(\frac{n}{2} \right )+n^2 &, n>1
\end{matrix}\right.}$
and then, prove that the solution you found is right, using mathematical induction.
So, do we have to do it like that?
We suppose that $n=2^k, k \geq 0$.
 $k=0 \Rightarrow n=1: T(1)=1=1\cdot (2 \cdot 11) \checkmark$
$$$$  We suppose that the relation stands for any $k>1$, so $T(2^k)=2^k(2^{k+1}1)$
$$$$  We will show that the relation stands for $k+1$.
$$T(2^{k+1})=2T \left (\frac{2^{k+1}}{2} \right )+(2^{k+1})^2=2T(2^k)+2^{2k+2}=2 (2^k(2^{k+1}1))+2^{2k+2}\\ =2^{2k+2}2^{k+1}+2^{2k+2}=2^{k+1}(2 \cdot 2^{k+1}1)$$
Perfect!
Alternatively, note that $T(n)=n(2n1)$ fits in the original equation, including the boundary condition that $T(1)=1$.
Therefore it is a solution.
$ \displaystyle T(1)=1(2\cdot 1  1)=1$
$ \displaystyle n(2n1)=T(n)=2T\left(\frac n2\right)+n^2 = 2\cdot \frac n 2 \left(2\cdot \frac n 2  1\right) + n^2 = n(n1) + n^2 = n(2n1)$
In other words, there is no real need for a proof by induction.
Just verifying that the proposed solution satisfies the problem statement is enough.

MHB Master
#5
October 9th, 2014,
13:09
Thread Author
Or do I have to suppose maybe, at the second step, that the relation stands for any $k \geq 0$ ?

MHB Seeker
#6
October 9th, 2014,
15:30
Originally Posted by
evinda
Or do I have to suppose maybe, at the second step, that the relation stands for any $k \geq 0$ ?
Oh yes.