# Proving convergence of recursive sequence.

1. Mar 23, 2014

### Darth Frodo

1. The problem statement, all variables and given/known data

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

3. The attempt at a solution

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

2. Mar 23, 2014

### Darth Frodo

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: Mar 23, 2014
3. Mar 23, 2014

### micromass

Staff Emeritus
You have the following handy theorem:

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. Mar 23, 2014

### micromass

Staff Emeritus
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!)

5. Mar 23, 2014

### Darth Frodo

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: Mar 23, 2014
6. Mar 23, 2014

### PeroK

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. Mar 23, 2014

### Ray Vickson

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.