Proving convergence of recursive sequence.

[Darth Frodo]

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.

 

[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.

 

[micromass]

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?

 

[micromass]

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

 

[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

 

[PeroK]

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.

 

[Ray Vickson]

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.