# Given $x_1=2$ and $x_{n+1}=2-\sqrt{ x}$, prove that $(x_n)$ converges and find the limit

I am given the following problem:

Given $x_1=2$ and $x_{n+1}=2-\sqrt{x}$, prove that $(x_n)$ converges and find the limit.

I realize there are two subsequences involved. The value they converge to is the value the sequence converges to. If $n$ is odd, the sequence is decreasing and if $n$ is even it's increasing. I am just having a problem showing this. I believe the limit to be $1$ by observation.

I have started with odd $n$, $1 < x_{n_{k}+1} < x_{n_k} < 2$

even $n$, $0.586 < x_{n_k} < x_{n_k+1} < 1$.

Any help on this would be most appreciated!

• do you mean $x_{n+1} = 2 - \sqrt{x_n}$ ? Oct 14 '13 at 15:15
• Maybe write $x_n$ in terms of $x_{n+1}$, and show that $x_n$ is further from your limit than $x_{n+1}$ is Oct 14 '13 at 15:25

First, look at the range of ${x_n}$. Should be pretty obvious that it's $0 \le x_n \le 2$ if you work out a few examples by hand. But this can be proven with induction:

$$0 \le x_{n+1} \le 2$$ $$0 \le 2 - \sqrt {x_n} \le 2$$ $$-2 \le - \sqrt {x_n} \le 0$$ $$0 \le \sqrt {x_n} \le 2$$

Which is true by the inductive assumption that $0 \le x_n \le 2$.

Second, if the sequence converges, then it converges to $1$. That's because for $2 - x = x$, you get $x = 1$. This isn't a proof, it's just a way of figuring out what it is that we need to prove.

That tells us that what is sufficient to prove is $|x_{n+1} - limit| < |x_n - limit|$ for a limit of 1.

Let's see here $$|x_{n+1} - 1| < |x_n - 1|$$ $$|2 - \sqrt{x_n} - 1| < |x_n - 1|$$ $$|1 - \sqrt{x_n}| < |x_n - 1|$$

If we consider the case that $0 \le x_n \le 1$ then the right hand side is negative inside the absolute value: $$1 - \sqrt{x_n} < 1 - x_n$$ $$x_n < \sqrt{x_n}$$ which is true in this range.

One the other hand if we consider the other case that $1 \le x_n$ then the left hand side gets flipped: $$\sqrt{x_n} - 1 < x_n - 1$$ $$\sqrt{x_n} < x_n$$ which is also true in this range.

• Thank you so much! This is very helpful!
– Jill
Oct 14 '13 at 16:58
• I disagree that it is sufficient to prove $|x_{n+1}-L| < |x_n-L|$. For example, we have $|(1/2)^{n+1} - (-1)| < |(1/2)^n - (-1)|$. Oct 14 '13 at 20:27
• Another counter example would be $x_n = 1 + (-1)^n (1 + e^{-n})$, a function which doesn't converge but it keeps getting closer to 1. Maybe I should have been more formal and used the actual definition of a limit, then shown constructively how it would be satisfied. I was mainly trying to show how to look at the problem and know what the answer is. Do you think I should delete this answer? Oct 14 '13 at 20:39
• Sorry if I came off as harsh. I think your answer has some merit (so don't delete), particularly in the first two paragraphs where you nail down what the limit is, assuming convergence. As you surely know, the odd-indexed terms form a decreasing sequence and the even-indexed terms form an increasing sequence; now one just has to show they come together. My own answer gives a way of looking at this, using a kind of Lipschitz condition to show the sequences zero in on the fixed point. How helpful my own answer is to OP isn't entirely clear to me. Oct 15 '13 at 0:34

Unfortunately, I don't think DanielV's answer demonstrates convergence.

However, let's see if we can prove that there exists $N$ and $r \in (0, 1)$ such that $|x_{n+1} - 1| \leq r|x_n - 1|$ for $n \geq N$. It would follow that $|x_{N+m} - 1| \leq cr^m$ where $c = |x_N - 1|$; since the right side of this inequality tends to $0$ as $m \to \infty$, it would follow that $\lim_{n \to \infty} x_n = 1$.

We have $x_{n+1} - 1 = 2-\sqrt{x_n} -1 = 1 - \sqrt{x_n}$, so

$$\frac{|x_{n+1}-1|}{|x_n-1|} = |\frac{\sqrt{x_n}-1}{x_n-1}|$$

where the right side is of the form $(1/2)c_n^{-1/2}$ for some $c_n$ strictly between $1$ and $x_n$, by the mean value theorem (applied to the square root function).

The first few $x_n$ are $x_1 = 2$, $x_2 = .586$, $x_3 = 1.2346$, $x_4 = .88886$. Once we get past the point $N$ where $x_n \geq .81$ for all $n \geq N$, we are guaranteed that $(1/2)c_n^{-1/2} \leq 5/9$, so we can take $r = 5/9$ and be assured that $|x_{n+1}-1| \leq (5/9)|x_n - 1|$. And indeed we may take $N = 4$, since now we can prove in induction fashion that if $x_n$ is in the range $(.81, 1.19)$, then so is $x_{n+1}$:

$$|1-x_{n+1}| \leq (5/9)|1-x_n| < |1-x_n| \leq .19$$

so that certainly $x_{n+1} \geq .81$, which is what we needed.