# Homework Help: Prove sequence converges

1. Nov 1, 2009

### ak123456

1. The problem statement, all variablproves and given/known data
X0=1, Xn+1=1/4 (1+2/Xn) for n=0,1,2,3,4....
prove that this sequence converges ,and find the limit

2. Relevant equations

3. The attempt at a solution
I though that Squeeze law might be used ,and let L=1/4(1+2/L) L=0.8437
and the sequence is not monotonic
so , how can i prove it next ?

2. Nov 1, 2009

### Staff: Mentor

I would calculate a few terms in the series to see if I could come up with a non-recursive formula for xn.

3. Nov 1, 2009

### ak123456

but how can i apply Squeeze law.

4. Nov 1, 2009

### Staff: Mentor

First things first. Try to find a non-recursive formula for xn, and then worry about the technique to use to see if the sequence converges or not.

5. Nov 1, 2009

### jbunniii

 oops, made a mistake, deleting it so I can fix it

6. Nov 3, 2009

I'm interested how this is solved. Has anyone done it? If so, how.

7. Nov 3, 2009

I've just been having a pop at this and decided to turn it into two sequences, one increasing, one decreasing, where:

X_n+1 = 1/4 + 2/(1+2/X_n)
With X_0 = 1 or 3/4

Would it be sufficient to show that one or both of these are bounded and monotonic?

8. Nov 4, 2009

### jbunniii

I think I finally found a solution, but it's ugly and hopefully someone knows a much cleaner way.

Let $L$ be the positive solution to

$$L = \frac{1}{4}\left(1 + \frac{2}{L}\right)$$

or equivalently

$$4L^2 - L - 2 = 0$$

Thus, $$L \approx0.84307$$.

If $(x_n)$ has a limit, then it must be $L$ because it's easy to see that $x_n$ is never negative.

The hard part is proving that $(x_n)$ has a limit. I shall do this by proving that the sequence

$$y_n = x_n - L$$

has a limit of 0. To do this, I shall find a constant $C < 1$ such that

$$\left|\frac{y_{n+1}}{y_n}\right| < C$$

for all $n$.

First, I need a small lemma, namely:

$$|y_n| < 0.2$$ for all n

This will be proved inductively. Clearly it's true for $n = 0$, because

$$|y_0| = |x_0 - L| \approx |1 - 0.84307| \approx 0.15693$$

Now suppose that $|y_n| < 0.2$; we must show that this implies $|y_{n+1}| < 0.2$. Indeed, $|y_n| < 0.2$ implies that $L - 0.2 < x_n < L + 0.2$. Therefore,

$$\frac{2}{L+0.2} < \frac{2}{x_n} < \frac{2}{L-0.2}$$

and this means

$$\frac{1}{4}\left(1 + \frac{2}{L+0.2}\right) < \frac{1}{4}\left(1 + \frac{2}{x_n}\right) < \frac{1}{4}\left(1 + \frac{2}{L - 0.2}\right)$$

This is the same as

$$0.72935 < x_{n+1} < 1.0275$$

and we also have $L - 0.2 < 0.72935$ and $1.0275 < L + 0.2$, so

$$L - 0.2 < x_{n+1} < L + 0.2$$

or equivalently

$$|y_{n+1}| < 0.2$$, concluding the proof of the lemma.

For the rest of the proof, we substitute $x_n = y_n + L$ into the original recurrence relation, cross-multiply the denominator, and use the fact that $4L^2 - L - 2 = 0$ to simplify the result to

$$4y_{n+1}y_n + 4L(y_n + y_{n+1}) = y_n$$

and solving for $y_{n+1}$ we get

$$y_{n+1} = \frac{y_n(1 - 4L)}{4(y_n+L)}$$

Then, using the fact that

$$\frac{1}{|y_n+L|} = \frac{1}{|x_n|} = \frac{1}{x_n} < \frac{1}{L - 0.2}$$

we have

$$|y_{n+1}| = \frac{|y_n| \cdot |1 - 4L|}{4|y_n+L|} < \frac{|y_n| \cdot |1 - 4L|}{4|L - 0.2|} = |y_n| \cdot 0.92225$$

Thus

$$\frac{|y_{n+1}|}{|y_n|} < C$$

where $C = 0.92225$, concluding the proof.

It ain't pretty, but it gets the job done, unless I screwed up somewhere.

By the way, there is nothing magic about the number 0.2. At some point I concluded that I needed a number less than 0.25 but big enough to handle the variation of the sequence about its limit, and I chose 0.2 after "cheating" by plotting the sequence in Matlab.

Last edited: Nov 4, 2009