# Convergence of $a_{n+1}=\sqrt{2-a_n}$

I'm attempting to prove the convergence (or divergence, though I strongly suspect it converges) of a sequence defined as $a_{n+1}=\sqrt{2-a_n}$ with $a_1=\sqrt{2}$.

I cannot use the monotonic sequence theorem as the sequence is not monotonically increasing. In fact, the first few values of the sequence are:

$a_1 =\sqrt{2}\approx 1.4142$

$a_2 =\sqrt{2-\sqrt{2}}\approx .7653$

$a_3 =\sqrt{2-\sqrt{2-\sqrt{2}}}\approx 1.1111$

Thus, it seems that $a_{n \to \infty} \to 1$

It seems that the sequence is behaving similarly to $\frac{\sin x}{x}$, leading me to think that the squeeze theorem may be useful. Still, I cannot seem to make any progress besides numerical computation of successive terms.

• If a limit exists, it must satisfy $L=\sqrt{2-L}$ – YoTengoUnLCD Feb 4 '16 at 14:38
• @YoTengoUnLCD That's true, but for sequences defined using recurrence sequences it's usually harder to prove that a limit exists than to determine its possible values. – Wojowu Feb 4 '16 at 14:40
• Have you tried bounding alternating terms? – abiessu Feb 4 '16 at 14:53
• @abiessu no, what do you mean by that? – zz20s Feb 4 '16 at 14:53
• Proceed using $a_{n+1}=\sqrt{2-a_n}=\sqrt{2-\sqrt{2-a_{n-1}}}$, and show that the sequence in $2n$ and the sequence in $2n-1$ are each monotonic and lead to the same result... – abiessu Feb 4 '16 at 14:57

Hint: write $a_n=1+b_n$ or $a_n=1-b_n$, whichever makes $b_n$ positive. How does $b_n$ behave?

Elaboration: we have $a_n=1+b_n$ for odd $n$ and $a_n=1-b_n$ for even $n$ (why so?). So, for example, for even $n$ we can write $a_{n+1}=\sqrt{2-a_n}$ as $1+b_{n+1}=\sqrt{2-(1-b_n)}=\sqrt{1+b_n}$. Now you can compare $b_{n+1}$ and $b_n$. Proceed similarly for odd $n$.

• How are you defining $b_n$? – zz20s Feb 4 '16 at 14:40
• @zz20s We are defining it so that equality $a_n=1\pm b_n$ works and $b_n$ is positive. So if you want a precise definition, it's $b_n=|1-a_n|$. – Wojowu Feb 4 '16 at 14:41
• I'm sorry, I'm not understanding. Can you further elaborate on your hint? – zz20s Feb 4 '16 at 14:46
• So are you saying that by defining another sequence $b_n$, we can look at seperate cases for odd and even $n$ and show that, in both those cases, the new sequence is monotonic? (this is my understanding, if misguided, please tell me) – zz20s Feb 4 '16 at 15:02
• Yes, that's precisely the idea of my answer. – Wojowu Feb 4 '16 at 15:03

Show that $$a_2\le a_4\le \cdots\le a_{2n}\le a_{2n-1}\cdots\le a_3\le a_1,$$ i.e., show that $\{a_{2n}\}$ is increasing, while $\{a_{2n-1}\}$ is decreasing. And also $a_{2n}\le a_{2n-1}$. This can be done inductively: $$a_{2k} \le a_{2k+2}\,\,\Rightarrow\,\, \sqrt{2-a_{2k}} \ge \sqrt{2-a_{2k+2}} \,\,\Rightarrow\,\, \sqrt{2-\sqrt{2-a_{2k}}} \le \sqrt{2-\sqrt{2-a_{2k+2}}}.$$ So $\{a_{2n}\}$, $\{a_{2n-1}\}$ converge.

Hint: near the fixed point $x = 1$ the function $x\to\sqrt{2-x}$ is contractive.

• I think this is the easiest way if you know Banach fixed point Th. – Svetoslav Feb 4 '16 at 15:45
• @Svetoslav : I'm not sure there are other ways to prove it, just a matter of vocabulary and of generality, but the arguments stay the same : once you are in the attractive region, you get closer and closer to the attractive point $p_0$, because the function maps any neighborhood of $p_0$ to a strictly smaller neighborhood – reuns Feb 4 '16 at 16:14

This iteration $x_{n+1} = f(x_n)$ with $f(x) = \sqrt{2-x}$ has a nice attractive fixed point at $(1,1)$

You can fiddle with the starting value here: GeoGebra interactive worksheet.

We have $$f'(x) = -\frac{1}{2\sqrt{2-x}}$$ and $$\lvert f'(1) \rvert = 1/2 < 1$$ so $x^* = 1$ is attractive in a neighbourhood.

• For all $x<7/4$, $|f'(x)|<1$. The first iterates contract $[-2,2]\to[0,2]\to[0,\sqrt2]$, hence the sequence converges for all starting $x$ in the domain. – Yves Daoust Feb 5 '16 at 7:29

You have surely proved that $a_n\le 2$ for all $n$.

Consider the sequences $b_n=a_{2n-1}$ and $c_n=a_{2n}$. The recursions are $$b_{n+1}=a_{2n+1}=\sqrt{2-a_{2n}}=\sqrt{2-\sqrt{2-a_{2n-1}}}= \sqrt{2-\sqrt{2-b_n}}$$ Let's show $(b_n)$ is decreasing: \begin{gather} b_{n+1}\le b_n\\ \sqrt{2-\sqrt{2-b_n}}\le b_n\\ 2-\sqrt{2-b_n}\le b_n^2\\ 2-b_n^2\le \sqrt{2-b_n}\\ 4-4b_n^2+b_n^4\le 2-b_n\\ (b_n+2)(b_n-1)\Bigl(b_n-\frac{1+\sqrt{5}}{2}\Bigr)\Bigl(b_n-\frac{1-\sqrt{5}}{2}\Bigr)\le0 \end{gather} and we just need to show $1\le b_n\le\sqrt{2}$ (work out why).

The basis of the induction is obvious, as $b_1=\sqrt{2}$. Suppose $1\le b_n\le \sqrt{2}$; then \begin{gather} 1\le b_{n+1}\le\sqrt{2}\\ 1\le 2-\sqrt{2-b_n}\le 2\\ 0\le\sqrt{2-b_n}\le 1\\ 0\le 2-b_n\le 1\\ 1\le b_n\le 2 \end{gather} Since this is true, we are done.

Therefore $(b_n)$ is a decreasing and bounded sequence, so it converges to $L$ such that $$L=\sqrt{L-\sqrt{2-L}}$$ The only nonnegative values for $L$ are $1$ and $(1+\sqrt{5})/2$, which however is greater than $b_1$, so we see $L=1$.

Now do the same in order to prove $(c_n)$ is increasing; actually you have to see that $0<c_n\le 1$, so $$(c_n+2)(c_n-1)\Bigl(c_n-\frac{1+\sqrt{5}}{2}\Bigr)\Bigl(c_n-\frac{1-\sqrt{5}}{2}\Bigr)\ge0$$

Convergence speed:

For $x=1+t$ close to $1$,

$$1+t_{n+1}=\sqrt{1-t_n}\approx1-\frac{t_n}2$$

and

$$t_{n+k}\approx t_n\left(-\frac12\right)^k.$$

The convergence is linear (one more exact bit per iteration). This is well illustrated by a logarithmic plot of the residue:

Potentially interesting alternative approach: if $a_{n+1}=\sqrt{2-a_n}$, let's take $a_n=2\cos\theta_n$ and hammer through some algebra to see that $2\cos\theta_{n+1}=2\sin\frac{\theta_n}{2}=2\cos\frac{\pi-\theta_n}{2}\implies\theta_{n+1}=\frac{\pi-\theta_n}{2}$.

Noting that $\frac{\pi}{3}=\frac{\pi-\frac{\pi}{3}}{2}$, we can see that $(\theta_{n+1}-\frac{\pi}{3})=\frac{-1}{2}(\theta_n-\frac{\pi}{3})$, showing that

• $\theta_n-\frac{\pi}{3}\to0$
• $\theta_n\to\frac{\pi}{3}$
• $a_n\to 2\cos\frac{\pi}{3}=1$

With a bit more work, you can push this a bit further to find an exact form for $a_n$, but that is arguably overkill for your question.

Here is a relatively simple argument that shows the convergence of the sequence $(a_n)_{n\geq 1}$.

First, we show by induction that $1/3<a_n<5/3$ for $n\geq 1$. This is clearly the case for $n=1$, since $a_1=\sqrt{2}$. Assuming the inductive hypothesis, we have: \begin{eqnarray*} 1/3&<&a_n<5/3 \\ 5/3&>&2-a_n>1/3 \\ 5/3>\sqrt{5/3}&>&a_{n+1}>\sqrt{1/3}>1/3\,. \end{eqnarray*} QED

Next, use the recurrence to get $$a_{n+1}^2-1=(2-a_n)-1=-(a_n-1)\,.$$ Hence $|a_{n}-1|=|a_{n+1}+1|\,|a_{n+1}-1|>4/3\,|a_{n+1}-1|$ and $|a_{n+1}-1|<3/4 \, |a_{n}-1|$ (for $n\geq 0$). Consequently, $$|a_{n}-1|<(3/4)^n$$ (for $n\geq 1$). It follows that $\lim_{n\to \infty}a_n=1$.