Proving by Induction: Solving Recurrence Relation

[evinda]

Hello! (Wave)

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(2n-1)$.

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$ ? (Thinking)

 

[I like Serena]

Hello! (Wave)

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(2n-1)$.

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$ ? (Thinking)

Hi! (Blush)

I'd pick $k$, since $T(n)$ is not defined for all $n \in \Bbb N$. (Thinking)

Btw, do you really have to use induction? (Wondering)

 

[evinda]

I'd pick $k$, since $T(n)$ is not defined for all $n \in \Bbb N$. (Thinking)

Btw, do you really have to use induction? (Wondering)

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 1-1) \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)$$

 

[I like Serena]

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 1-1) \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! (Happy)Alternatively, note that $T(n)=n(2n-1)$ fits in the original equation, including the boundary condition that $T(1)=1$.
Therefore it is a solution.

$$T(1)=1(2\cdot 1 - 1)=1$$

$$n(2n-1)=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(n-1) + n^2 = n(2n-1)$$

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. (Nerd)

 

[evinda]

Or do I have to suppose maybe, at the second step, that the relation stands for any $k \geq 0$ ? (Thinking)

 

[I like Serena]

Or do I have to suppose maybe, at the second step, that the relation stands for any $k \geq 0$ ? (Thinking)

Oh yes. (Blush)