MHB Proving by Induction: Solving Recurrence Relation

AI Thread Summary
The discussion revolves around proving the solution to the recurrence relation T(n) = 2T(n/2) + n^2, with T(1) = 1, which is proposed to be T(n) = n(2n - 1). Participants debate whether to use mathematical induction with respect to n or k, ultimately suggesting that k is more appropriate since n is not defined for all natural numbers. It is noted that verifying the proposed solution directly satisfies the recurrence relation and boundary condition may eliminate the need for induction altogether. The conversation concludes that confirming the solution fits the original equation is sufficient.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Physics news on Phys.org
evinda said:
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)
 
I like Serena said:
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)$$
 
evinda said:
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)
 
Or do I have to suppose maybe, at the second step, that the relation stands for any $k \geq 0$ ? (Thinking)
 
evinda said:
Or do I have to suppose maybe, at the second step, that the relation stands for any $k \geq 0$ ? (Thinking)

Oh yes. (Blush)
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Replies
3
Views
2K
Replies
2
Views
1K
Replies
13
Views
1K
Replies
18
Views
3K
Replies
4
Views
1K
Replies
1
Views
3K
Replies
1
Views
2K
Back
Top