Proving convergence of recursive sequence.

  • #1
210
1

Homework Statement



Prove for c>0 the sequence [itex]{x_n} = \frac{1}{2}(x_{n-1} + \frac{c}{x_{n-1}})[/itex] converges.


The Attempt at a Solution



This is proving difficult, I have never dealt with recursive sequences before. Any help would be appreciated. Thanks.
 

Answers and Replies

  • #2
210
1
So, I have an idea, but i'm not sure if it proves convergence.

If [itex]x_{n} = g(x_{n-1})[/itex] then all I have to do it let [itex]x = g(x)[/itex].





EDIT: Upon further thought, it does not as convergence => [itex]x_{n} = g(x_{n-1})[/itex]. It is not a iff situation. Back at square one.
 
Last edited:
  • #3
22,089
3,286
You have the following handy theorem:

If ##(x_n)_n## is a monotone increasing/decreasing sequence and if the ##(x_n)_n## are bounded, then the ##(x_n)_n## converge.
I would start by trying to apply this one. Can you show the sequence is increasing/decreasing? Can you find a lower/upper bound?
 
  • #4
22,089
3,286
So, I have an idea, but i'm not sure if it proves convergence.

If [itex]x_{n} = g(x_{n-1})[/itex] then all I have to do it let [itex]x = g(x)[/itex].
This is a nice remark, because if the sequence converges, you can find out the limit point this way. Indeed, you have ##x_n = g(x_{n-1})##. Thus

[tex]x = \lim_{n\rightarrow +\infty} x_n = \lim_{n\rightarrow +\infty} g(x_{n-1}) = g(x)[/tex]

So can you figure out what the limit point ##x## is? (of course you still have to prove it actually converges!)
 
  • #5
210
1
So this is what I have so far.

[itex] x_0 = r [/itex] r is a non-zero real number

[itex] x_{n+1} = x_n(\frac{1}{2} + \frac{c}{2x_n^2}) [/itex]


Case 1: ##r^2 < c~ \Rightarrow## sequence is increasing

Case 2: ##r^2 > c ~\Rightarrow## sequence is decreasing
 
Last edited:
  • #6
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
14,684
6,944
So this is what I have so far.

[itex] x_0 = r [/itex] r is a non-zero real number

[itex] x_{n+1} = x_n(\frac{1}{2} + \frac{c}{2x_n^2}) [/itex]


Case 1: ##r^2 < c~ \Rightarrow## sequence is increasing

Case 2: ##r^2 > c ~\Rightarrow## sequence is decreasing
Not quite:

Suppose c = 4 and x_0 = 1, then x_1 = 5/2 and x_2 = 89/40, so neither increasing nor decreasing!

You're on the right track, though.
 
  • #7
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

Homework Statement



Prove for c>0 the sequence [itex]{x_n} = \frac{1}{2}(x_{n-1} + \frac{c}{x_{n-1}})[/itex] converges.


The Attempt at a Solution



This is proving difficult, I have never dealt with recursive sequences before. Any help would be appreciated. Thanks.
To see what is happening, look at the graph of
[tex] y = f(x), \text{ where } f(x) = \frac{1}{2} \left( x + \frac{c}{x} \right)[/tex]
Look up material about "cobweb plots"; see, eg., http://en.wikipedia.org/wiki/Cobweb_plot . This will give you some intuition about what is happening; it is not yet a 'proof', but may help get you started.
 

Related Threads on Proving convergence of recursive sequence.

Replies
3
Views
3K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
3
Views
326
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
5
Views
9K
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
1
Views
1K
Replies
4
Views
1K
Replies
6
Views
4K
Replies
5
Views
737
Top