MHB Show that $S(m)=\Theta(m^2)$ with Recurrence Relation

AI Thread Summary
The discussion focuses on proving that the recurrence relation \( S(m) = S(m-1) + m \) results in \( S(m) = \Theta(m^2) \). The user demonstrates the proof by assuming \( S(m-1) = \Theta((m-1)^2) \) and deriving bounds for \( S(m) \). They successfully establish both upper and lower bounds, concluding that \( S(m) = O(m^2) \) and \( S(m) = \Omega(m^2) \), thus confirming \( S(m) = \Theta(m^2) \). Additionally, there is a query about finding the exact solution of the recurrence and the need for an initial condition, which remains unresolved in the discussion. The proof method and reasoning presented appear correct.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Smile)

Let $S(m)=S(m-1)+m$.
I want to show that $S(m)=\Theta(m^2)$.

That's what I have tried:

We suppose a positive integer $m>0$. We suppose that $S(m-1)=\Theta((m-1)^2)$, so it holds that $\exists c_1, c_2>0$ such that :
$$c_1 (m-1)^2 \leq S(m-1) \leq c_2(m-1)^2$$

We will show that $c_1 m^2 \leq S(m) \leq c_2 m^2$.

$$S(m)=S(m-1)+m \leq c_2(m-1)^2+m=c_2 m^2-2c_2 m +c_2+m=c_2m^2-(2c_2m-c_2-m) \leq c_2 m^2, \text{ if } 2c_2m-c_2-m \geq 0 \Rightarrow c_2(2m-1) \geq m \Rightarrow c_2 \geq \frac{m}{2m-1} \to \frac{1}{2} \Rightarrow c_2 \geq \frac{1}{2}$$

So, we have that $S(m)=O(m^2)$.

$$S(m)=S(m-1)+m \geq c_1(m-1)^2+m=c_1 m^2-2c_1 m +c_1+m=c_1m^2-(2c_1m-c_1-m) \geq c_1 m^2, \text{ if } 2c_1m-c_1-m \leq 0 \Rightarrow c_1(2m-1) \geq m \Rightarrow c_1 \geq \frac{m}{2m-1} \to \frac{1}{2} \Rightarrow c_1 \geq \frac{1}{2}$$

So, we have that $S(m)=\Omega(m^2)$.

Therefore, $S(m)=\Theta(m^2)$.

Could you tell me if it is right or if I have done something wrong? (Thinking)

Also, can we find from the above the exact solution of the recurrence relation, or do we have to do it in an other way, like using the substitution method? If so, how can we know when the recursion ends, without having an initial condition? :confused:
 
Physics news on Phys.org
evinda said:
Hello! (Smile)

Let $S(m)=S(m-1)+m$.
I want to show that $S(m)=\Theta(m^2)$.

That's what I have tried:

We suppose a positive integer $m>0$. We suppose that $S(m-1)=\Theta((m-1)^2)$, so it holds that $\exists c_1, c_2>0$ such that :
$$c_1 (m-1)^2 \leq S(m-1) \leq c_2(m-1)^2$$

We will show that $c_1 m^2 \leq S(m) \leq c_2 m^2$.

$$S(m)=S(m-1)+m \leq c_2(m-1)^2+m=c_2 m^2-2c_2 m +c_2+m=c_2m^2-(2c_2m-c_2-m) \leq c_2 m^2, \text{ if } 2c_2m-c_2-m \geq 0 \Rightarrow c_2(2m-1) \geq m \Rightarrow c_2 \geq \frac{m}{2m-1} \to \frac{1}{2} \Rightarrow c_2 \geq \frac{1}{2}$$

So, we have that $S(m)=O(m^2)$.

$$S(m)=S(m-1)+m \geq c_1(m-1)^2+m=c_1 m^2-2c_1 m +c_1+m=c_1m^2-(2c_1m-c_1-m) \geq c_1 m^2, \text{ if } 2c_1m-c_1-m \leq 0 \Rightarrow c_1(2m-1) \geq m \Rightarrow c_1 \geq \frac{m}{2m-1} \to \frac{1}{2} \Rightarrow c_1 \geq \frac{1}{2}$$

So, we have that $S(m)=\Omega(m^2)$.

Therefore, $S(m)=\Theta(m^2)$.

Could you tell me if it is right or if I have done something wrong? (Thinking)

Also, can we find from the above the exact solution of the recurrence relation, or do we have to do it in an other way, like using the substitution method? If so, how can we know when the recursion ends, without having an initial condition? :confused:

Writing the equation in slightly different form You have...

$\displaystyle s_{n+1} = s_{n} + n + 1\ (1)$

Setting $s_{0}$ the value of the $s_{n}$ for n=0, the solution of (1) is...

$\displaystyle s_{n} = s_{0} + \sum_{k=1}^{n} k = s_{0} + \frac{n\ (n+1)}{2}\ (2)$

... so that is $\displaystyle s_{n} = \mathcal{O} (n^{2})$...

Kind regards

$\chi$ $\sigma$
 
chisigma said:
Writing the equation in slightly different form You have...

$\displaystyle s_{n+1} = s_{n} + n + 1\ (1)$

Setting $s_{0}$ the value of the $s_{n}$ for n=0, the solution of (1) is...

$\displaystyle s_{n} = s_{0} + \sum_{k=1}^{n} k = s_{0} + \frac{n\ (n+1)}{2}\ (2)$

... so that is $\displaystyle s_{n} = \mathcal{O} (n^{2})$...

Kind regards

$\chi$ $\sigma$

I see.. But is the way I showed that $S(m)=\Theta(m^2)$ also right?
Or have I done something wrong? :confused:
 
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...
Back
Top