Convergence of a recursively defined sequence

  • #1
1,462
44
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?
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,928
1,492
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.
 
  • #3
1,462
44
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?
 
  • #4
15,431
13,476
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.
 
  • #5
1,462
44
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}##?
 
  • #6
15,431
13,476
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.
 
  • Like
Likes Mr Davis 97
  • #7
1,462
44
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##?
 
  • #8
15,431
13,476
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]##.
 
  • #9
1,462
44
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?
 
  • #10
15,431
13,476
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).
 
  • Like
Likes Mr Davis 97
  • #11
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,928
1,492
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.
 
Last edited:
  • #12
1,462
44
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##?
 
  • #13
15,431
13,476
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.
 
  • #14
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,928
1,492
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?
 
  • #15
1,462
44
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##?
 
  • #16
15,431
13,476
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.
 
  • #17
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,928
1,492
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.
 
  • #18
Svein
Science Advisor
Insights Author
2,188
726
As far as I can see, the formula is the recursive formula for solving the square root of 5...
 
  • #19
15,431
13,476
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.
 

Related Threads on Convergence of a recursively defined sequence

Replies
2
Views
4K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
6
Views
14K
Replies
4
Views
2K
  • Last Post
Replies
4
Views
1K
Replies
4
Views
1K
Top