Proving convergence of recursive sequence.

Darth Frodo
Messages
211
Reaction score
1

Homework Statement



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


The Attempt at a Solution



This is proving difficult, I have never dealt with recursive sequences before. Any help would be appreciated. Thanks.
 
Physics news on Phys.org
So, I have an idea, but I'm not sure if it proves convergence.

If x_{n} = g(x_{n-1}) then all I have to do it let x = g(x).EDIT: Upon further thought, it does not as convergence => x_{n} = g(x_{n-1}). It is not a iff situation. Back at square one.
 
Last edited:
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?
 
Darth Frodo said:
So, I have an idea, but I'm not sure if it proves convergence.

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

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

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

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

x_0 = r r is a non-zero real number

x_{n+1} = x_n(\frac{1}{2} + \frac{c}{2x_n^2})Case 1: ##r^2 < c~ \Rightarrow## sequence is increasing

Case 2: ##r^2 > c ~\Rightarrow## sequence is decreasing
 
Last edited:
Darth Frodo said:
So this is what I have so far.

x_0 = r r is a non-zero real number

x_{n+1} = x_n(\frac{1}{2} + \frac{c}{2x_n^2})


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.
 
Darth Frodo said:

Homework Statement



Prove for c>0 the sequence {x_n} = \frac{1}{2}(x_{n-1} + \frac{c}{x_{n-1}}) 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
y = f(x), \text{ where } f(x) = \frac{1}{2} \left( x + \frac{c}{x} \right)
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.
 
Back
Top