1. 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(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$ ?

2.

3. 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(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$ ?
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?

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?

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

5. Originally Posted by evinda

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!

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.

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

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

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

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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•