Show that $S(m)=\Theta(m^2)$ by Induction

[evinda]

Hello again! (Wave)

How can I show by induction that $S(m)=\Theta(m^2)$, where
$ \displaystyle{ S(m)=2 S\left ( \frac{m}{5}+6 \right )+3 S\left ( \frac{m}{5} \right)+m^2 }$ ?

We suppose that $c_1 k^2 \leq S(k) \leq c_2 k^2, \forall k<m$.

We want to show that $c_1 m^2 \leq S(m) \leq c_2 m^2$, right? (Thinking)

But.. how can we do this? (Thinking)

 

[evinda]

I tried to do it like that:

$$S(m) \leq 2c_2 \left ( \frac{m}{5}+6\right )^2+3c_2 \left ( \frac{m}{5}\right)^2+m^2$$

but I couldn't show, in this way, that $S(m) \leq c_2 m^2$.. (Worried)

How else could I do this? (Thinking)

 

[I like Serena]

Hello again! (Wave)

How can I show by induction that $S(m)=\Theta(m^2)$, where
$ \displaystyle{ S(m)=2 S\left ( \frac{m}{5}+6 \right )+3 S\left ( \frac{m}{5} \right)+m^2 }$ ?

We suppose that $c_1 k^2 \leq S(k) \leq c_2 k^2, \forall k<m$.

We want to show that $c_1 m^2 \leq S(m) \leq c_2 m^2$, right? (Thinking)

But.. how can we do this? (Thinking)

Hi hi! (Smile)

I do not think this is the right approach.
Suppose that S(0)=1.
Then $S(k) \leq c_2 k^2, \forall k<m$ cannot be satisified for any $c_2$.
Instead I propose that we start with an $n_0, c_1>0, c_2>0$ and some $k_0$ such that $\forall k$ with $n_0 \ge k \ge k_0$ we have that $c_1 k^2 \le S(k) \le c_2 k^2$.
Furthermore, we need that $n_0 \ge 8$ and $k_0 \ge 5n_0$, so that our recurrence relation is properly defined for $m \ge k_0$.
And I think we also need to make the assumption that $S(m) > 0$ for all $m$.

Since we are talking about a finite sequence of numbers, we can always find such constants as an initial condition.

Now I think we are ready for the induction step... (Thinking)

I tried to do it like that:

$$S(m) \leq 2c_2 \left ( \frac{m}{5}+6\right )^2+3c_2 \left ( \frac{m}{5}\right)^2+m^2$$

but I couldn't show, in this way, that $S(m) \leq c_2 m^2$.. (Worried)

How else could I do this? (Thinking)

Well, actually I think you can.
What condition can you find for $c_2$ that will ensure this is true? (Wondering)

 

[evinda]

Hi hi! (Smile)

I do not think this is the right approach.
Suppose that S(0)=1.
Then $S(k) \leq c_2 k^2, \forall k<m$ cannot be satisified for any $c_2$.
Instead I propose that we start with an $n_0, c_1>0, c_2>0$ and some $k_0$ such that $\forall k$ with $n_0 \ge k \ge k_0$ we have that $c_1 k^2 \le S(k) \le c_2 k^2$.
Furthermore, we need that $n_0 \ge 8$ and $k_0 \ge 5n_0$, so that our recurrence relation is properly defined for $m \ge k_0$.
And I think we also need to make the assumption that $S(m) > 0$ for all $m$.

Since we are talking about a finite sequence of numbers, we can always find such constants as an initial condition.

Could you explain me how you found the restrictions $n_0 \geq 8$ and $k_0 \geq 5n_0$ ? (Thinking)

 

[I like Serena]

Could you explain me how you found the restrictions $n_0 \geq 8$? (Thinking)

Suppose you try to evaluate $S(7)$.
What do you get after one iteration? (Wondering)

and $k_0 \geq 5n_0$

Suppose you try to evaluate $S(k_0)$.
What do you get after one iteration? (Wondering)

 

[evinda]

Suppose you try to evaluate $S(7)$.
What do you get after one iteration? (Wondering)

We get: $S(7)=2S(7.4)+3S(1.4)+7^2$... (Worried)

Suppose you try to evaluate $S(k_0)$.
What do you get after one iteration? (Wondering)

I haven't understood why we take two constants, $n_0$ and $k_0$, when we suppose that $c_1 k^2 \leq S(k) \leq c_2 k^2$.. (Sweating)

Could you explain it further to me? (Thinking)

 

[I like Serena]

We get: $S(7)=2S(7.4)+3S(1.4)+7^2$... (Worried)

That is unfortunate. (Worried)
The formula refers to values of $m$ that are higher than the one we want to evaluate!
What is the lowest value of $m$ that we will only refer to lower values? (Wondering)

I haven't understood why we take two constants, $n_0$ and $k_0$, when we suppose that $c_1 k^2 \leq S(k) \leq c_2 k^2$.. (Sweating)

Could you explain it further to me? (Thinking)

So that all values, that are referred to by the recurrence relation, are within the induction assumption. (Wasntme)

We cannot refer to all values lower than $k_0$, since we cannot be sure that for instance S(0) will fall within the induction assumption. (Wasntme)

 

[evinda]

That is unfortunate. (Worried)
The formula refers to values of $m$ that are higher than the one we want to evaluate!
What is the lowest value of $m$ that we will only refer to lower values? (Wondering)

In order the recurrence relation to be well-defined, it must be:

$$\frac{m}{5}+6<m \Rightarrow \frac{4m}{5}>6 \Rightarrow 4m>30 \Rightarrow m \geq 8$$

Therefore, the lowest value that $m$ can take is $8$, right? (Thinking)

So that all values, that are referred to by the recurrence relation, are within the induction assumption. (Wasntme)

We cannot refer to all values lower than $k_0$, since we cannot be sure that for instance S(0) will fall within the induction assumption. (Wasntme)

Could you explain me how we pick $n_0$ and $k_0$ ? I haven't understood it... (Worried)

 

[I like Serena]

In order the recurrence relation to be well-defined, it must be:

$$\frac{m}{5}+6<m \Rightarrow \frac{4m}{5}>6 \Rightarrow 4m>30 \Rightarrow m \geq 8$$

Therefore, the lowest value that $m$ can take is $8$, right? (Thinking)

For our proof we will only look at $n_0 \ge 8$ so that we can be sure we only refer to lower values.

Could you explain me how we pick $n_0$ and $k_0$ ? I haven't understood it... (Worried)

We pick $n_0$ up to $k_0$ as a range in which holds for any $m$ between them:
$$S(m)=2 S\left ( \frac{m}{5}+6 \right )+3 S\left ( \frac{m}{5} \right)+m^2$$
When we look at $S(k_0)$, we want that $S\left ( \frac{k_0}{5}+6 \right )$ and $S\left ( \frac{k_0}{5} \right)$ are within the range of our initial assumption.
We can guarantee that if $\frac{k_0}{5} \ge n_0 \Rightarrow k_0 \ge 5n_0$. (Nerd)

When looking at the induction step with $k_0+1$, we know that all S values referred to, are guaranteed to be within the range. (Wasntme)

 

[evinda]

For our proof we will only look at $n_0 \ge 8$ so that we can be sure we only refer to lower values. We pick $n_0$ up to $k_0$ as a range in which holds for any $m$ between them:
$$S(m)=2 S\left ( \frac{m}{5}+6 \right )+3 S\left ( \frac{m}{5} \right)+m^2$$
When we look at $S(k_0)$, we want that $S\left ( \frac{k_0}{5}+6 \right )$ and $S\left ( \frac{k_0}{5} \right)$ are within the range of our initial assumption.
We can guarantee that if $\frac{k_0}{5} \ge n_0 \Rightarrow k_0 \ge 5n_0$. (Nerd)

But.. how can it be that $n_0 \geq k \geq k_0$, knowing that $k_0 \geq 5n_0$ ? (Worried)

 

[I like Serena]

But.. how can it be that $n_0 \geq k \geq k_0$, knowing that $k_0 \geq 5n_0$ ? (Worried)

By inverting the inequalities: $n_0 \le k \le k_0$. (Blush)

 

[evinda]

By inverting the inequalities: $n_0 \le k \le k_0$. (Blush)

A ok.. And why is $k_0$ the largest value that $k$ can take? (Worried)

Why do we find the largest value that $k$ can take from the inequality $\frac{m}{5} \geq n_0$ ? (Thinking)

 

[I like Serena]

A ok.. And why is $k_0$ the largest value that $k$ can take? (Worried)

Why do we find the largest value that $k$ can take from the inequality $\frac{m}{5} \geq n_0$ ? (Thinking)

That is because we pick as induction hypothesis:
$$\forall k \text{ such that } n_0\le k \le k_0 \text{ we have that }: c_1 k^2 \le S(k) \le c_2 k^2$$

To complete the induction step, we need to prove that:
$$c_1 (k_0+1)^2 \le S(k_0+1) \le c_2 (k_0+1)^2$$
Can you prove that? (Wondering)
If we also have a suitable initial condition, we will have proven with full induction that:
$$\forall n\ge n_0: c_1 n^2 \le S(n) \le c_2 n^2$$
In turn this implies that:
$$S(n) = \Theta(n^2)$$
(Mmm)

 

[evinda]

That is because we pick as induction hypothesis:
$$\forall k \text{ such that } n_0\le k \le k_0 \text{ we have that }: c_1 k^2 \le S(k) \le c_2 k^2$$

So, we suppose that $\exists n_0 \in \mathbb{N}, c_1>0,c_2>0, k_0 \in \mathbb{N}$ such that $\forall n_0 \geq k \geq k_0$ we have:

$$c_1k^2 \leq S(k) \leq c_2k^2$$

In order, the recurrence relation $S(k)=2S \left ( \frac{k}{5}+6\right )+3S \left ( \frac{k}{5} \right )+k^2$ to be well-defined, it must stand:

$$ \frac{k}{5}+6 <k \Rightarrow k \geq 8$$

and

$$\frac{k}{5}<k, \text{ that is true } \forall k>0$$

Therefore, the lowest value that $k$ can take is $8$, so we pick $n_0=8$.

In order to find an inequality for $k_0$, do we have to solve the following inequalities:

$$\frac{k}{5}+6 \geq n_0$$

and

$$\frac{k}{5} \leq n_0$$

? (Thinking)

Could we also assume that $c_1 k^2 \leq S(k) \leq c_2 k^2, \forall n_0 \leq k \leq m$? Also,do we have to make the assumption that $S(m)>0, \forall m$, so that the recurrence relation is well-defined? (Thinking)

 

[I like Serena]

So, we suppose that $\exists n_0 \in \mathbb{N}, c_1>0,c_2>0, k_0 \in \mathbb{N}$ such that $\forall n_0 \geq k \geq k_0$ we have:

$$c_1k^2 \leq S(k) \leq c_2k^2$$

Yes, but with $\forall n_0 {\color{red}\leq} k {\color{red}\leq} k_0$.

In order, the recurrence relation $S(k)=2S \left ( \frac{k}{5}+6\right )+3S \left ( \frac{k}{5} \right )+k^2$ to be well-defined, it must stand:

$$ \frac{k}{5}+6 <k \Rightarrow k \geq 8$$

and

$$\frac{k}{5}<k, \text{ that is true } \forall k>0$$

Therefore, the lowest value that $k$ can take is $8$, so we pick $n_0=8$.

In order to find an inequality for $k_0$, do we have to solve the following inequalities:

$$\frac{k}{5}+6 \geq n_0$$

and

$$\frac{k}{5} \leq n_0$$

? (Thinking)

Yep! (Nod)

Also,do we have to make the assumption that $S(m)>0, \forall m$, so that the recurrence relation is well-defined? (Thinking)

But yes, this is essential for the proof to work. (Nod)
Actually, it would suffice if $S(m)>0$ for sufficiently large $m$.

I think it should have been part of the problem statement.
Since this is presumably about something like the cost of an algorithm, it makes sense that it is always positive. (Nerd)

Could we also assume that $c_1 k^2 \leq S(k) \leq c_2 k^2, \forall n_0 \leq k \leq m$?

I'm not sure what you want to assume here exactly.

Anyway, we can pick:
$$n_0=8$$
$$c_1 = \min\{S(k)/k^2 : n_0 \leq k \leq 5n_0\}$$
$$c_2 = \max\{S(k)/k^2 : n_0 \leq k \leq 5n_0\}$$

This makes our base case for induction:
$$\forall n_0 \leq k \leq 5n_0: c_1 k^2 \leq S(k) \leq c_2 k^2, $$
(Mmm)

 

[evinda]

Yes, but with $\forall n_0 {\color{red}\leq} k {\color{red}\leq} k_0$. Yep! (Nod)

But, why do we pick $k_0$ such that $\frac{k_0}{5}+6 \geq n_0$ and $\frac{k_0}{5} \geq n_0$, but we took $n_0$ such that $\frac{m}{5}+6<m$? I am confused now... (Sweating)

But yes, this is essential for the proof to work. (Nod)
Actually, it would suffice if $S(m)>0$ for sufficiently large $m$.

I think it should have been part of the problem statement.
Since this is presumably about something like the cost of an algorithm, it makes sense that it is always positive. (Nerd)

I see... (Smile)

I'm not sure what you want to assume here exactly.

I thought that we could say, that $\exists n_0 \in \mathbb{N}, c_1,c_2>0$ such that $c_1 k^2 \leq S(k) \leq c_2 k^2, \forall n_0 {\color{red}\leq} k {\color{red}<} m$. And then, we would show that the relation stands also for $m$, can't we? (Thinking)

Anyway, we can pick:
$$n_0=8$$
$$c_1 = \min\{S(k)/k^2 : n_0 \leq k \leq 5n_0\}$$
$$c_2 = \max\{S(k)/k^2 : n_0 \leq k \leq 5n_0\}$$

This makes our base case for induction:
$$\forall n_0 \leq k \leq 5n_0: c_1 k^2 \leq S(k) \leq c_2 k^2, $$
(Mmm)

So, you took the smallest values that $c_1$ and $c_2$ can take, right?

So, do we have to choose also $c_1$ and $c_2$, at the induction hypothesis?

If so, will the same $c_1$, $c_2$ work at the induction step? (Thinking)

 

[I like Serena]

But, why do we pick $k_0$ such that $\frac{k_0}{5}+6 \geq n_0$ and $\frac{k_0}{5} \geq n_0$, but we took $n_0$ such that $\frac{m}{5}+6<m$? I am confused now... (Sweating)

We pick $n_0$ large enough so that S(n) is well defined and refers only to smaller values.
From here on, we will only look at values for S where n is bigger.We pick $k_0$ large enough, and bigger than $n_0$, such we have a range in which we can set our base case.
When we refer to $k_0+1$ for the inductive step, we want to be able to fall back to this range that should contain all values that $S(k_0+1)$ could possibly refer to. (Nerd)

I thought that we could say, that $\exists n_0 \in \mathbb{N}, c_1,c_2>0$ such that $c_1 k^2 \leq S(k) \leq c_2 k^2, \forall n_0 {\color{red}\leq} k {\color{red}<} m$. And then, we would show that the relation stands also for $m$, can't we? (Thinking)

Yes. (Nod)
This is the same as what I am getting at, except that you use $m$ where I used $k_0+1$.

Under the assumption that $S(k)>0$, the constants are guaranteed to exist, and we can pick/calculate them. (Happy)

So, you took the smallest values that $c_1$ and $c_2$ can take, right?

Yes, I picked $c_1$ as small as it needs to be, and $c_2$ as large as it needs to be, given the choice $n_0=8$.

So, do we have to choose also $c_1$ and $c_2$, at the induction hypothesis?

If so, will the same $c_1$, $c_2$ work at the induction step? (Thinking)

No. (Shake)
We only make 1 choice for $n_0, c_1, c_2$ and we'll stick with them.
The choice is based on the base case, and we will prove that the same constants are applicable for any $n \ge n_0$.

 

[evinda]

We pick $n_0$ large enough so that S(n) is well defined and refers only to smaller values.
From here on, we will only look at values for S where n is bigger.We pick $k_0$ large enough, and bigger than $n_0$, such we have a range in which we can set our base case.
When we refer to $k_0+1$ for the inductive step, we want to be able to fall back to this range that should contain all values that $S(k_0+1)$ could possibly refer to. (Nerd)

I still haven't understood why we have to find a restriction for $k_0$... (Sweating) (Worried)Could you explain it to me with an example? (Worried)

Yes. (Nod)
This is the same as what I am getting at, except that you use $m$ where I used $k_0+1$.

Under the assumption that $S(k)>0$, the constants are guaranteed to exist, and we can pick/calculate them. (Happy)

Yes, I picked $c_1$ as small as it needs to be, and $c_2$ as large as it needs to be, given the choice $n_0=8$.
No. (Shake)
We only make 1 choice for $n_0, c_1, c_2$ and we'll stick with them.
The choice is based on the base case, and we will prove that the same constants are applicable for any $n \ge n_0$.

So, we say that $\exists c_1,c_2>0$ and $n_0, k_0 \in \mathbb{N}, k_0 \geq 5n_0 $ such that:

$$c_1 k^2 \leq S(k) \leq c_2 k^2, \forall n_0 \leq k \leq k_0$$

$$S(k_0+1)=2S \left ( \frac{k_0+1}{5}+6\right)+3S \left ( \frac{k_0+1}{5} \right )+ (k_0+1)^2 \leq 2c_2 \left ( \frac{k_0+1}{5}+6\right)^2+3c_2 \left ( \frac{k_0+1}{5} \right )^2+(k_0+1)^2=2c_2 \frac{k_0^2+62k_0+961}{25}+3c_2 \frac{k_0^2+2k_0+1}{25}+k_0^2+2k_0+1=\frac{c_2k_0^2}{5}+\frac{26c_2 k_0}{5}+77c_2+k_0^2+2k_0+1 $$

Is it right so far? How could we continue? (Thinking)

- - - Updated - - -

What would we have to do, in order to find $k_0$, if we had for example the recurrence relation $S(m)=2S \left( \frac{m}{5}+3\right)+3S\left ( \frac{m}{5}\right)+m^2$ (Thinking)

 

[I like Serena]

I still haven't understood why we have to find a restriction for $k_0$... (Sweating) (Worried)Could you explain it to me with an example? (Worried)

Thinking about it, I guess it is not really necessary. (Thinking)
We do need to take care with S(0), since if it is different from 0, it won't satisfy the condition. (Worried)

But I guess we can also pick:
$$n_0=8$$
$$c_1=\min\{S(k)/k^2:1 \le k \le n_0\}$$
$$c_2=\max\{S(k)/k^2:1 \le k \le n_0\}$$
and then prove with induction as follows.

Lemma
$$\exists n_0 \in \mathbb N, \exists c_1>0, \exists c_2>0 \text{ such that }\forall n \ge n_0: c_1 n^2 \le S(n) \le c_2 n^2$$

Proof

Base case
With the given choices, we have implicitly:
$$\forall k \in \mathbb N_{>0}, k \le n_0: c_1 k^2 \le S(k) \le c_2 k^2$$

Inductive step
If we assume that given $m > n_0$:
$$\forall k \in \mathbb N_{>0}, k < m: c_1 k^2 \le S(k) \le c_2 k^2$$
then we need to prove that
$$c_1 m^2 \le S(m) \le c_2 m^2$$
(Thinking)

So, we say that $\exists c_1,c_2>0$ and $n_0, k_0 \in \mathbb{N}, k_0 \geq 5n_0 $ such that:

$$c_1 k^2 \leq S(k) \leq c_2 k^2, \forall n_0 \leq k \leq k_0$$

$$S(k_0+1)=2S \left ( \frac{k_0+1}{5}+6\right)+3S \left ( \frac{k_0+1}{5} \right )+ (k_0+1)^2 \leq 2c_2 \left ( \frac{k_0+1}{5}+6\right)^2+3c_2 \left ( \frac{k_0+1}{5} \right )^2+(k_0+1)^2=2c_2 \frac{k_0^2+62k_0+961}{25}+3c_2 \frac{k_0^2+2k_0+1}{25}+k_0^2+2k_0+1=\frac{c_2k_0^2}{5}+\frac{26c_2 k_0}{5}+77c_2+k_0^2+2k_0+1 $$

Is it right so far? How could we continue? (Thinking)

What did you need to prove again? (Wondering)

 

[evinda]

Thinking about it, I guess it is not really necessary. (Thinking)
We do need to take care with S(0), since if it is different from 0, it won't satisfy the condition. (Worried)

Isn't the recurrence relation satisfied only for $n \geq n_0$ ? (Worried)

But I guess we can also pick:
$$n_0=8$$
$$c_1=\min\{S(k)/k^2:1 \le k \le n_0\}$$
$$c_2=\max\{S(k)/k^2:1 \le k \le n_0\}$$
and then prove with induction as follows.

Lemma
$$\exists n_0 \in \mathbb N, \exists c_1>0, \exists c_2>0 \text{ such that }\forall n \ge n_0: c_1 n^2 \le S(n) \le c_2 n^2$$

Proof

Base case
With the given choices, we have implicitly:
$$\forall k \in \mathbb N_{>0}, k \le n_0: c_1 k^2 \le S(k) \le c_2 k^2$$

(Wondering)

I thought that we could only take $k$, such that $k \geq n_0$, am I wrong? (Sweating) (Worried)

 

[evinda]

In order to show for example that $S(m)=\Theta(m^2)$, where $S(m)=3S\left( \frac{m}{5} \right)+2S\left( \frac{m}{5}+3\right)+m^2$ couldn't we do it like that?

The recurrence relation is well-defined if $\frac{m}{5}+3<m \Rightarrow m \geq 4$.

We will show that $S(m)=\Theta(m^2)$.

We suppose that $\exists c_1,c_2, n_0 \geq 4$, such that $\forall n_0 \leq k<m$:
$$c_1 k^2 \leq S(k) \leq c_2 k^2$$

$$S(m)=3S\left( \frac{m}{5} \right)+2S\left( \frac{m}{5}+3\right)+m^2 \leq 3c_2 \frac{m^2}{25}+2 \left(\frac{m}{5}+6 \right)^2+m^2=\frac{5c_2n^2}{25}+\frac{12c_2n}{5}+18c_2+n^2 \leq c_2 n^2$$

if $c_2 n^2-\frac{5c_2n^2}{25}-\frac{12c_2n}{5}-18c_2+n^2 \geq 0 \Rightarrow \frac{2c_2}{5}(2n^2-6n-45) \geq n^2 \Rightarrow \frac{2c_2}{5} \geq \frac{n^2}{2n^2-6n-45} \to \frac{1}{2} \Rightarrow 2c_2 \geq \frac{5}{2} \Rightarrow c_2 \geq \frac{5}{4}$

And then, we will find that $S(m) \geq c_1 m^2$, if $c_1 \leq \frac{5}{4}$.
Or am I wrong? (Thinking)

 

[I like Serena]

Isn't the recurrence relation satisfied only for $n \geq n_0$ ? (Worried)

I thought that we could only take $k$, such that $k \geq n_0$, am I wrong? (Sweating) (Worried)

I'm assuming that the recurrence relation is also satisfied for lower $n$.

It's only that for a proof with induction that we prefer to only look at $n$ that are big enough so we do not have to deal with "weird" issues. (Thinking)

 

[evinda]

I'm assuming that the recurrence relation is also satisfied for lower $n$.

It's only that for a proof with induction that we prefer to only look at $n$ that are big enough so we do not have to deal with "weird" issues. (Thinking)

But, for lower $n$, it isn't a recurrence relation...Or am I wrong? (Worried)

 

[I like Serena]

In order to show for example that $S(m)=\Theta(m^2)$, where $S(m)=3S\left( \frac{m}{5} \right)+2S\left( \frac{m}{5}+3\right)+m^2$ couldn't we do it like that?

The recurrence relation is well-defined if $\frac{m}{5}+3<m \Rightarrow m \geq 4$.

We will show that $S(m)=\Theta(m^2)$.

We suppose that $\exists c_1,c_2, n_0 \geq 4$, such that $\forall n_0 \leq k<m$:
$$c_1 k^2 \leq S(k) \leq c_2 k^2$$

$$S(m)=3S\left( \frac{m}{5} \right)+2S\left( \frac{m}{5}+3\right)+m^2 \leq 3c_2 \frac{m^2}{25}+2 \left(\frac{m}{5}+6 \right)^2+m^2=\frac{5c_2n^2}{25}+\frac{12c_2n}{5}+18c_2+n^2 \leq c_2 n^2$$

if $c_2 n^2-\frac{5c_2n^2}{25}-\frac{12c_2n}{5}-18c_2+n^2 \geq 0 \Rightarrow \frac{2c_2}{5}(2n^2-6n-45) \geq n^2 \Rightarrow \frac{2c_2}{5} \geq \frac{n^2}{2n^2-6n-45} \to \frac{1}{2} \Rightarrow 2c_2 \geq \frac{5}{2} \Rightarrow c_2 \geq \frac{5}{4}$

And then, we will find that $S(m) \geq c_1 m^2$, if $c_1 \leq \frac{5}{4}$.
Or am I wrong? (Thinking)

That's about it, yes! (Nod)

Still, it doesn't suffice that $c_2 \ge \frac{5}{4}$.
We require that the base case is satisifed for some $c_2$, and then additionally $c_2$ has to be greater than or equal to $\frac{5}{4}$.

And it appears you left out the base case. (Worried)

 

[I like Serena]

But, for lower $n$, it isn't a recurrence relation...Or am I wrong? (Worried)

I looked it up in wiki:

In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms.​

It appears that it shouldn't be the case that the recurrence relation refers to later items in the sequence. (Nod)

 

[evinda]

Still, it doesn't suffice that $c_2 \ge \frac{5}{4}$.
We require that the base case is satisifed for some $c_2$, and then additionally $c_2$ has to be greater than or equal to $\frac{5}{4}$.

How can we find a $c_2$, wenn we suppose that $c_1 k^2 \leq S(k) \leq c_2k^2, \forall n_0 \leq k < m$?

And it appears you left out the base case. (Worried)

So, do we have to prove also the base case, althought we do not have an initial condition? How can we do this? (Thinking)

 

[I like Serena]

But, for lower $n$, it isn't a recurrence relation...Or am I wrong? (Worried)

For the lower $n$, $S(n)$ should still be defined, but as fixed given values. (Thinking)

How can we find a $c_2$, wenn we suppose that $c_1 k^2 \leq S(k) \leq c_2k^2, \forall n_0 \leq k < m$?

So, do we have to prove also the base case, althought we do not have an initial condition? How can we do this? (Thinking)

The values for S(0) to S(8) should be given to properly define a recurrence relation for the higher $n$.
Whatever they are, from those we can calculate the values for $c_1$ and $c_2$.

The base case would then be as I described in post http://mathhelpboards.com/computer-science-58/show-s-m-920-m-2-a-12861-post62325.html#post62325. (Nerd)

 

[evinda]

For the lower $n$, $S(n)$ should still be defined, but as fixed given values. (Thinking)The values for S(0) to S(8) should be given to properly define a recurrence relation for the higher $n$.
Whatever they are, from those we can calculate the values for $c_1$ and $c_2$.

The base case would then be as I described in post http://mathhelpboards.com/computer-science-58/show-s-m-920-m-2-a-12861-post62325.html#post62325. (Nerd)

How can we conclude that $c_1k^2 \leq S(k) \leq c_2k^2, \forall 0<k \leq n_0$, without having initial conditions? (Thinking) (Worried)

 

[I like Serena]

How can we conclude that $c_1k^2 \leq S(k) \leq c_2k^2, \forall 0<k \leq n_0$, without having initial conditions? (Thinking) (Worried)

Suppose we are given $S(1)$ up to $S(8)$.
Let's say: $S(k)=k+1$ for $1 \le k \le 8$. (Thinking)Then we can pick $c_1=\min\{S(k)/k^2 : 1 \le k \le 8\} = \min\{2/1^2, ..., 9/8^2\} = \frac{9}{64}$.
This satisfies the part of the base case that $c_1 k^2 \le S(k)$ for $1 \le k \le 8$.
In this case $c_1$ is also smaller than $\frac 5 4$, which we need to satisfy the inductive step. (Thinking)Whatever $S(1)$ to $S(8)$ are, we can always find such a $c_1$ (assuming they are positive). (Wasntme)