5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ If a limit exists, it must satisfy $L=\sqrt{2-L}$ $\endgroup$ – YoTengoUnLCD Feb 4 '16 at 14:38
  • 1
    $\begingroup$ @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. $\endgroup$ – Wojowu Feb 4 '16 at 14:40
  • $\begingroup$ Have you tried bounding alternating terms? $\endgroup$ – abiessu Feb 4 '16 at 14:53
  • $\begingroup$ @abiessu no, what do you mean by that? $\endgroup$ – zz20s Feb 4 '16 at 14:53
  • 1
    $\begingroup$ 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... $\endgroup$ – abiessu Feb 4 '16 at 14:57
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How are you defining $b_n$? $\endgroup$ – zz20s Feb 4 '16 at 14:40
  • $\begingroup$ @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|$. $\endgroup$ – Wojowu Feb 4 '16 at 14:41
  • $\begingroup$ I'm sorry, I'm not understanding. Can you further elaborate on your hint? $\endgroup$ – zz20s Feb 4 '16 at 14:46
  • $\begingroup$ 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) $\endgroup$ – zz20s Feb 4 '16 at 15:02
  • $\begingroup$ Yes, that's precisely the idea of my answer. $\endgroup$ – Wojowu Feb 4 '16 at 15:03
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I think this is the easiest way if you know Banach fixed point Th. $\endgroup$ – Svetoslav Feb 4 '16 at 15:45
  • $\begingroup$ @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 $\endgroup$ – reuns Feb 4 '16 at 16:14
4
$\begingroup$

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.

square root iteration

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yves Daoust Feb 5 '16 at 7:29
3
$\begingroup$

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 $$

$\endgroup$
2
$\begingroup$

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:

enter image description here

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $|a_{n}-1|=|a_{n+1}+1|\,|a_{n+1}-1| > 4/3\,|a_{n+1}-1|$ $\endgroup$ – lhf Dec 29 '16 at 10:29
  • $\begingroup$ @Ihf : Correction completed. My thanks ! $\endgroup$ – P. Lalonde Jan 4 '17 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.