# Proving that this recursively defined sequence converges.

The sequence is defined as such, with $a_1=1$, $$a_{n+1} = \begin{cases} a_n + 1/n, & \mbox{if } a_n^2 \leq 2 \\ a_n - 1/n, & \mbox{if } a_n^2 > 2 \\ \end{cases}.$$

In the book, P.M. Fitzpatrick's Advanced Calculus, the exercises wants me to show that for all indices $n$, $|a_n-\sqrt{2}|<2/n$. Of course after that it's easy to prove that the sequence converges by the Comparison Lemma, since $\{ 1/n\}$ converges. My problem is with proving that inequality. The only way I can think of is by induction. This is my incomplete attempt:

Since $1<\sqrt{2}<2$, we have $-1<1-\sqrt{2}<0$ and so $|a_1 - \sqrt{2}|<1<2$.

Suppose that $|a_k-\sqrt{2}|<2/k$. If $a_k^2 \leq 2$ then $a_{k+1}=a_k+1/k$.

Now this is where I get stuck. Of course I would also have to do it for the case when $a_k^2>2$, but that comes after. I have tried different ways of manipulating the last two inequalities but to no avail. Any suggestions?

• Two almost correct answers had been given and deleted. Each one can be made correct by dividing into cases. For $a_k^2\lt 2$, there are two cases, $a_{k+1}\lt \sqrt{2}$ and $a_{k+1}\gt \sqrt{2}$. – André Nicolas Jul 22 '16 at 0:04
• @AndréNicolas I cannot see those answers so I can't comment on that, but I will try the cases approach and see where I get. Thank you! – Jean Jul 22 '16 at 0:18
• You are welcome. It is just a matter of drawing a picture (well, a couple of pictures) before worrying about absolute values or inequality manipulation. Let's suppose first that $a_k\lt \sqrt{2}$. There are two possibilities (i) $a_{k+1}$ is still less than $\sqrt{2}$. The distance from $\sqrt{2}$ has shrunk by $\frac{1}{k}$, so is less than $\frac{2}{k}-\frac{1}{k}$, nice and small. (ii) $a_{k+1}\gt \sqrt{2}$. Then it must be less than $\frac{1}{k}$ bigger. This forces $\lt \frac{2}{k+1}$. The argument when $a_{k+1}\gt \sqrt{2}$ is similar, again two cases. – André Nicolas Jul 22 '16 at 0:24
• By the way, I would prefer not to mention a Comparison Lemma. If you know that $|a_n-\sqrt{2}|\lt \frac{2}{n}$, then the sequence converges to $\sqrt{2}$ by the definition of convergence. – André Nicolas Jul 22 '16 at 0:35
• You can post it. Other people had posted and deleted things that were not quite right but could easily be fixed. I thought one or more might do so. And yes, once we come to concrete grips with the problem, by minor fiddling with a number line, drawn in the head or on paper, the problem collapses. – André Nicolas Jul 22 '16 at 0:40