Show that the sequence $\{a_{n+1}\}$ converges to $\sqrt{2}$

Question

Define $a_1=1$. If $n$ is an index such that $a_n$ has been defined, then define $$a_{n+1}=\begin{cases}a_n+1/n, & \text{if $a^2_n\leq 2$}\\a_n-1/n,&\text{if $a^2_n>2$} \end{cases}$$ Show that the sequece converges to $\sqrt{2}$.

---

Proof:

Let $\epsilon>0$. By the Archinmedean Property there exists an index $N$ such that $1/N<\epsilon$. For all $n\geq N$, we can get $1/n\leq1/N$. If $a_n^2\leq 2$, we have $$\left\vert a_n+1/n-\sqrt{2}\right\vert<2/n<2/N<\epsilon\tag1$$ If $a_n^2>2$, we have $$\left\vert a_n-1/n-\sqrt{2}\right\vert<2/n<2/N<\epsilon\tag2$$$

Add $(1)$ and $(2)$, we get $$\left\vert 2a_n-2\sqrt{2}\right\vert<4/n<4/N<2\epsilon\Longrightarrow\left\vert a_n-\sqrt{2}\right\vert<2/n<2/N<\epsilon$$

Thus the sequence converges to $\sqrt{2}$

---

In $(1)$ and $(2)$, I didn't say anything about why I need minus $\sqrt{2}$, cause I didn't find out any good reason. Without assuming $(1)$ and $(2)$ are incorrect, I don't the proof I have right or not. Can anyone give me a hit or suggestion to write a better proof? Thanks in advanced.

Answer 1

Oops. I did make a fundamental error

==============

Where you say "If $a_n^2\leq 2$, we have"

I'd add "$a_{n}^2 \leq \sqrt 2$ so

$a_{n+1} - \sqrt 2 = a_{n} + 1/n -\sqrt 2\leq \sqrt 2+ 1/n - \sqrt 2 \leq 1/n$ and

===== error =======

its possible that $a_{n+1} - \sqrt 2$ < - 1/n. Thus $|a_{n+1} - \sqrt 2| > 1/n$

==================

$ \sqrt 2- a_{n+1} = \sqrt 2 - a_{n} - 1/n \geq \sqrt 2 - \sqrt 2- 1/n \geq -1/n$ so

======= ditto =========

$ \sqrt 2- a_{n+1}$ could be > 1/n.

I think it turns that these errors are never the case, but we have to show that.

=====================

$|a_{n + 1} - \sqrt 2 | \leq 1/{n} < 1/N < \epsilon$

And then again for $a_{n}^2\geq 2$

... same stuff....

so for all n+1 > N+1 , $|a_{n +1 } - \sqrt 2 | < \epsilon$, so we are done.

I couldn't quite follow in yours how we were getting $|a_{n } - \sqrt 2 | < \epsilon$, although you were clearly going in that direction. (But you put in the expression directly, and your indexing was therefore off by $1$)

Answer 2

Hint: your argument must use the fact that $\sum_{n=1}^{\infty} \frac{1}{n}$ diverges.

In more detail, the problem is that your inequality (1) need not hold. To see this, define $b_1 = 1$ and then $$b_{n+1}=\begin{cases}b_n+1/4^n, & \text{if $b^2_n\leq 2$}\\b_n-1/4^n,&\text{if $b^2_n>2$} \end{cases}$$

Now $\sum_{n=1}^{\infty}1/4^n$ converges to $1/3$, consequently as $(4/3)^2 < 2$, we will always add and never subtract and the $b_n$ will tend to $4/3 < \sqrt{2}$.

Returning to your sequence $a_n$, because $\sum_{n=1}^{\infty} 1/n$ diverges, for any $k$, there will be a $K \ge k$ such that $a_{K+1}^2 - 2$ has the opposite sign to $a_k^2 - 2$ (you never get $a_n^2 - 2 = 0$ because the $a_n$ are rational). So given $\epsilon > 0$, pick $k$ such that $1/k < \epsilon$ and then pick the smallest $K \ge k$ such that $a_{K+1}^2 - 2$ has the opposite sign to $a_k^2 - 2$. Then for any $n > K$ we will have $|\sqrt{2} - a_n| < 1/K \le 1/k < \epsilon$.