Convergence of a recursively defined sequence

[Mr Davis 97]

I have the following sequence: $s_1 = 5$ and $\displaystyle s_n = \frac{s_{n-1}^2+5}{2 s_{n-1}}$. To prove that the sequence converges, my textbook proves that the following is true all $n$: $\sqrt{5} < s_{n+1} < s_n \le 5$. I know to prove that this recursively defined sequence converges, we have to show that it is decreasing and that it is bounded below. As such, I have a few questions: why does the author choose $\sqrt{5}$ to be the potential lower bound? Would it be just as valid to prove use 0 as the number we could prove to be a lower bound? Also, why is that 5 there? Is it at all necessary to the proof?

 

[andrewkirk]

Choosing 0 would satisfy the 'bounded below' bit, but that's only one of the two requirements. I suspect that those tighter limits of 5 and $\sqrt 5$ will be needed in proving the other requirement - that the series is decreasing.

 

[Mr Davis 97]

Choosing 0 would satisfy the 'bounded below' bit, but that's only one of the two requirements. I suspect that those tighter limits of 5 and $\sqrt 5$ will be needed in proving the other requirement - that the series is decreasing.

But, just say that I want to prove that the sequence is decreasing. How would I know beforehand that I must prove that $s_n > \sqrt{5}$ for all $n$? It seems to me that it is not immediately obvious that I must prove that $s_n > \sqrt{5}$. Where does the $\sqrt{5}$ come from?

 

[fresh_42]

But, just say that I want to prove that the sequence is decreasing. How would I know beforehand that I must prove that $s_n > \sqrt{5}$ for all $n$?

You won't and it is not necessary. Any finite lower bound as e.g. zero will do to prove convergence. If you want to prove what the limit is, you need a proposal. I haven't checked, but maybe $\sqrt{5}$ comes into play doing that.

It seems to me that it is not immediately obvious that I must prove that $s_n > \sqrt{5}$. Where does the $\sqrt{5}$ come from?

Probably from $s=\dfrac{s^2+5}{2s}\,.$ If $s_{n+1} < s_n$ and $s_0=5$, then the limit must be around $s$ and it can only approach from above.

 

[Mr Davis 97]

You won't and it is not necessary. Any finite lower bound as e.g. zero will do to prove convergence. If you want to prove what the limit is, you need a proposal. I haven't checked, but maybe $\sqrt{5}$ comes into play doing that.

Probably from $s=\dfrac{s^2+5}{2s}\,.$ If $s_{n+1} < s_n$ and $s_0=5$, then the limit must be around $s$ and it can only approach from above.

So instead of proving that $\sqrt{5} < s_{n+1} < s_n \le 5$ is true for all $n$, could I just as well prove that $0 < s_{n+1} < s_n \le 5$ to prove convergence?

If this is the case, why is it that author just goes ahead and uses $\sqrt{5}$?

 

[fresh_42]

So instead of proving that $\sqrt{5} < s_{n+1} < s_n \le 5$ is true for all $n$, could I just as well prove that $0 < s_{n+1} < s_n \le 5$ to prove convergence?

For convergence, yes.

If this is the case, why is it that author just goes ahead and uses $\sqrt{5}$?

Because this is the limit.

It's like saying: "I'm less than 20 ft tall." You would probably use a number which is closer to the truth, even if you only want to say that you're not infinitely tall.

 

[Mr Davis 97]

For convergence, yes.

Because this is the limit.

It's like saying: "I'm less than 20 ft tall." You would probably use a number which is closer to the truth, even if you only want to say that you're not infinitely tall.

Just to clarify though, since I don't technically know that $\sqrt{5}$ is the limit beforehand, in practice would I choose something more obvious as a lower bound, like $0$?

 

[fresh_42]

Just to clarify though, since I don't technically know that $\sqrt{5}$ is the limit beforehand, in practice would I choose something more obvious as a lower bound, like $0$?

I would do so. The crucial part is $s_{n+1} < s_n$. The rest of a convergence proof is more or less obvious, because of $(s_n)\subseteq [0,5]$.

 

[Mr Davis 97]

I would do so. The crucial part is $s_{n+1} < s_n$. The rest of a convergence proof is more or less obvious, because of $(s_n)\subseteq [0,5]$.

Is the fact that 5 is an upper bound at all necessary to show convergence? Don't we just have to know that the sequence is decreasing and that there is a lower bound?

 

[fresh_42]

Is the fact that 5 is an upper bound at all necessary to show convergence? Don't we just have to know that the sequence is decreasing and that there is a lower bound?

With monotony the first sequence element is automatically an upper bound, so necessary is a bit difficult to say, as it is as obvious. Personally, I like $(s_n) \subseteq [0,5]$ because one sees at once, that it is a compact set and thus the limits are within. This way it isn't necessary to think about the right end. It's more a matter of convenience to have a compact set than a necessity.

If you apply pure logic, then things are more complicated anyway. E.g. you need an argument why $s_n < 5$ and $s_{n+1}< s_n$ implies $s_{n+1} < 5$ (transitivity of the ordering plus induction, resp. Peano on the index set).

 

[andrewkirk]

Is the fact that 5 is an upper bound at all necessary to show convergence? Don't we just have to know that the sequence is decreasing and that there is a lower bound?

The upper bound of 5 is not used anywhere in the proof of convergence. It is not even used in proving that the actual limit is $\sqrt 5$.

The lower bound of $\sqrt 5$ is a key part of proving the sequence is decreasing, which is a necessary part of proving convergence. The proof of decreasingness is easy given that lower bound - three short steps. Using a lower bound of 0 instead would not work.

 

[Mr Davis 97]

With monotony the first sequence element is automatically an upper bound, so necessary is a bit difficult to say, as it is as obvious. Personally, I like $(s_n) \subseteq [0,5]$ because one sees at once, that it is a compact set and thus the limits are within. This way it isn't necessary to think about the right end. It's more a matter of convenience to have a compact set than a necessity.

If you apply pure logic, then things are more complicated anyway. E.g. you need an argument why $s_n < 5$ and $s_{n+1}< s_n$ implies $s_{n+1} < 5$ (transitivity of the ordering plus induction, resp. Peano on the index set).

Makes sense. Last thing. What would be the best way to prove that $s_{n+1} < s_n$ in this case? Should I start on the LHS and make an argument that looks something like $\displaystyle s_{n+1} = \frac{s_{n}^2+5}{2 s_{n}} < \cdots < s_n$, OR should I make an argument that starts with $s_{n+1} < s_n \implies \frac{s_{n}^2+5}{2 s_{n}} < s_n \implies s_n > \sqrt{5}$ and prove that $s_n > \sqrt{5}$ for all $n$?

 

[fresh_42]

Makes sense. Last thing. What would be the best way to prove that $s_{n+1} < s_n$ in this case? Should I start on the LHS and make an argument that looks something like $\displaystyle s_{n+1} = \frac{s_{n}^2+5}{2 s_{n}} < \cdots < s_n$, OR should I make an argument that starts with $s_{n+1} < s_n \implies \frac{s_{n}^2+5}{2 s_{n}} < s_n \implies s_n > \sqrt{5}$ and prove that $s_n > \sqrt{5}$ for all $n$?

It's equivalent - because we have only positive numbers - to $\sqrt{5} < s_n$ and that also answers your question, why the square root of five as lower bound comes into play. I would do it by induction. Whether it is the best way is a matter of taste. There's probably a more elegant way using calculus.

 

[andrewkirk]

OR should I make an argument that starts with $s_{n+1} < s_n \implies \frac{s_{n}^2+5}{2 s_{n}} < s_n \implies s_n > \sqrt{5}$ and prove that $s_n > \sqrt{5}$ for all $n$?

That would not lead anywhere. It is called 'affirming the consequent'. If $A\to B$ then proving $B$ tells us nothing about the truth or otherwise of $A$. In any case, that $s_n>\sqrt 5$ has already been proved by the text.

Look at the formula $s_{n+1}=\frac{s_n{}^2+5}{2s_n}$. If it wasn't for that 5 in the numerator we could cancel out the $s_n$ in the denominator and get a simpler expression that might give us a useful inequality. Using one of the inequalities proved in the text, can we replace the 5 by something greater than or equal to 5 that allows us to cancel out the $s_n$ in the denominator?

 

[Mr Davis 97]

That would not lead anywhere. It is called 'affirming the consequent'. If $A\to B$ then proving $B$ tells us nothing about the truth or otherwise of $A$. In any case, that $s_n>\sqrt 5$ has already been proved by the text.

Look at the formula $s_{n+1}=\frac{s_n{}^2+5}{2s_n}$. If it wasn't for that 5 in the numerator we could cancel out the $s_n$ in the denominator and get a simpler expression that might give us a useful inequality. Using one of the inequalities proved in the text, can we replace the 5 by something greater than or equal to 5 that allows us to cancel out the $s_n$ in the denominator?

If we know that $s_n^2 >5$, then $2 s_n^2 > s^2_n + 5$, so $s_{n+1} = \frac{s_n^2+5}{2s_n} < \frac{2s_n^2}{2s_n} = s_n$. I guess that makes sense... My question then is if I were to approach this problem on my own without the book, how would I know beforehand that $s^2_n > 5$?

 

[fresh_42]

My question then is if I were to approach this problem on my own without the book, how would I know beforehand that $s^2_n > 5$?

You would a) assume the sequence converges, b) therefore conclude that $s_{n+1}-s_n$ is narrowing down, so for big enough $n$ we c) get $s=\dfrac{s^2+5}{2s}$ with only a small error. But this means d) $s=\sqrt{5}$ which is e) our candidate for the limit. As we start with $5$ and $\sqrt{5}<5$ there must f) be a decrease somewhere. On the other hand, we g) don't have any hints that the sequence jumps back and forth, so h) $s_{n+1} < s_n$ is a natural assumption to be checked.

 

[andrewkirk]

Typically with a sequence, one calculates the first few values to look for patterns. After three steps the number is very close to $\sqrt 5$ and the presence of the numeral 5 in the formula suggests trying a simple function of 5, such as $\sqrt 5$ as the limit. We also notice that the sequence is decreasing in those first three steps, which suggests a downwards asymptotic approach.

By the way, once we know the sequence is decreasing, we can directly prove the sequence has a limit of $\sqrt 5$ as follows. The reduction from one sequence element to the next is
\begin{align*}
s_n-s_{n+1}
&=
s_n-\frac{s_n{}^2 + 5}{2s_n}\\
&=
\frac{s_n{}^2 - 5}{2s_n}\\
&=
\frac{(s_n - \sqrt 5)(s_n + \sqrt 5)}{2s_n}\\
&=
(s_n - \sqrt 5)\left(\frac12 +\frac{\sqrt 5}{2s_n}\right)\\
&>
\frac12 (s_n - \sqrt 5)
\end{align*}
From which we observe that:
\begin{align*}
s_{n+1}-\sqrt 5
&= (s_n-\sqrt 5) - (a - b)\\
&<
(s_n-\sqrt 5) -\frac12 (s_n-\sqrt 5)\\
&=
\frac12 (s_n-\sqrt 5)
\end{align*}
So the distance of $s_n$ from $\sqrt 5$ is more than halving at every step, so it must go to that limit.

 

[Svein]

As far as I can see, the formula is the recursive formula for solving the square root of 5...

 

[fresh_42]

As far as I can see, the formula is the recursive formula for solving the square root of 5...

Yes, looks like Newton's method to take roots by hand.