Is the sequence defined by the recurrence $ a _ { n + 2 } = \frac 1 { a _ { n + 1 } } + \frac 1 { a _ n } $ convergent?

Question

Let $ a _ 0 = 1 $, $ a _ 1 = 1 $ and $ a _ { n + 2 } = \frac 1 { a _ { n + 1 } } + \frac 1 { a _ n } $ for every natural number $ n $. How can I prove that this sequence is convergent?

---

I know that if it's convergent, it converges to $ \sqrt 2 $ since if $ \lim \limits _ { n \to \infty } a _ n = a $ then: $$ \lim _ { n \to \infty } \left ( a _ { n + 2 } - \frac 1 { a _ { n + 1 } } - \frac 1 { a _ n } \right) = a - \frac 2 a = 0 \text ; $$ $$ \therefore \quad a ^ 2 = 2 \text . $$ Now it's easy to see that every $ a _ n $ is positive, so $ a \ge 0 $ and thus $ a = \sqrt 2 $.

---

Assuming the sequence is convergent, I can calculate an estimation of the rate of convergence too. Let $ \epsilon _ n := a _ n - \sqrt 2 $. We have: $$ \epsilon _ { n + 2 } = \frac 1 { a _ { n + 1 } } - \frac 1 { \sqrt 2 } + \frac 1 { a _ n } - \frac 1 { \sqrt 2 } = - \frac { a _ { n + 1 } - \sqrt 2 } { \sqrt 2 a _ { n + 1 } } - \frac { a _ n - \sqrt 2 } { \sqrt 2 a _ n } = - \frac { \epsilon _ { n + 1 } } { \sqrt 2 a _ { n + 1 } } - \frac { \epsilon _ n } { \sqrt 2 a _ n } \text . $$ Now because $ a _ n \sim \sqrt 2 + \epsilon _ n $ and $ \lim \limits _ { n \to \infty } \epsilon _ n = 0 $, therefore from the above equation: $$ \epsilon _ { n + 2 } \lesssim - \frac { \epsilon _ { n + 1 } + \epsilon _ n } 2 \text , $$ which yields $ \epsilon _ n \lesssim \alpha \left ( \frac { - 1 - \sqrt 7 i } 4 \right) ^ n + \beta \left( \frac { - 1 + \sqrt 7 i } 4 \right) ^ n $ for some complex constants $ \alpha $ and $ \beta $, using induction on $ n $. Equivalently, we have $ \epsilon _ n \lesssim \left( \frac 1 { \sqrt 2 } \right) ^ n \bigl( A \cos ( n \theta ) + B \sin ( n \theta ) \bigr) $ for $ \theta = \arctan \frac { \sqrt 7 } 4 $ and some real constants $ A $ and $ B $, since $ \left| \frac { - 1 \pm \sqrt 7 i } 4 \right| = \frac 1 { \sqrt 2 } $ and $ \arg \frac { - 1 \pm \sqrt 7 i } 4 = \pi \mp \theta $. Hence we get the rough estimation $ | \epsilon _ n | \lesssim C 2 ^ { - \frac n 2 } $ for some real constant $ C $, and $ \frac 1 { \sqrt 2 } $ is a good guess for the rate of convergence.

(Edit: Thanks to Alex Ravsky for the confirming graphs in his answer.)

---

Edit (some more of my thoughts):

Let $ b _ n := \min \left\{ a _ n , a _ { n + 1 } , \frac 2 { a _ n } , \frac 2 { a _ { n + 1 } } \right\} $. It's easy to see that $ b _ n \le a _ n \le \frac 2 { b _ n } $ and $ b _ n \le a _ { n + 1 } \le \frac 2 { b _ n } $. Now using induction we can prove that $ b _ n \le a _ { n + m } \le \frac 2 { b _ n } $. Especially, $ a _ { n + 2 } \ge b _ n $ and $ \frac 2 { a _ { n + 2 } } \ge b _ n $ which yields $ b _ { n + 1 } \ge b _ n $. The problem can be solved if I show that the sequence $ ( b _ n ) _ { n = 0 } ^ \infty $ increases to $ \sqrt 2 $.

Answer 1

The sequence converges. Define $b_n = \dfrac{a_n}{\sqrt{2}}$, then the recurrence for $(b_n)$ is

$$b_{n+2} = \frac{a_{n+2}}{\sqrt{2}} = \frac{1}{\sqrt{2}\,a_{n+1}} + \frac{1}{\sqrt{2}\,a_n} = \frac{1}{2}\biggl(\frac{\sqrt{2}}{a_{n+1}} + \frac{\sqrt{2}}{a_n}\biggr) = \frac{1}{2}\biggl(\frac{1}{b_{n+1}} + \frac{1}{b_n}\biggr).\tag{1}$$

We observe that for every $t\in [0,+\infty)$, if there is an $N$ such that $b_N$ and $b_{N+1}$ both lie in the interval $[e^{-t},e^t]$, then $e^{-t} \leqslant b_n \leqslant e^t$ for all $n \geqslant N$. Thus, for whatever starting values $b_0,b_1 \in (0,+\infty)$ are given, the sequence is bounded. Next we note that if there is an $N$ with $b_N = b_{N+1} = 1$, then the sequence must be the constant sequence $b_n = 1$ for all $n$. Further, if for some $n$ we have $b_n, b_{n+1} \geqslant 1$ then $b_{n+2} \leqslant 1$, and analogously if $b_n, b_{n+1} \leqslant 1$ then $b_{n+2} \geqslant 1$, and unless $b_n = b_{n+1} = 1$, the inequality for $b_{n+2}$ is in fact strict. So except for the constant sequence, the positive sequences with the recurrence $(1)$ never contain three successive terms such that $\log b_n$ has the same sign (where we say that $0 = \log 1$ has the same sign as $x$ for every $x\in \mathbb{R}$). We henceforth ignore the constant sequence, since its convergence is trivial.

Hence we have

$$e^{-\alpha} = \liminf_{n\to\infty} b_n \leqslant 1 \leqslant \limsup_{n\to \infty} b_n = e^{\beta}.\tag{2}$$

Let us show that we have $\alpha = \beta$. Suppose to the contrary that $\alpha < \beta$. Choose $\delta > 0$ such that $\alpha + 2\delta < \beta$, and $N \in \mathbb{N}\setminus \{0\}$ such that $b_n > e^{-\alpha-\delta}$ for all $n \geqslant N$. Pick an $n \geqslant N$ such that $b_n < \min \{1, e^{-\alpha +\delta}\}$. If $b_{n-1} \leqslant 1$, then $b_{n-1},b_n \in [e^{-\alpha - \delta}, e^{\alpha + \delta}]$, and by the first observation it follows that then $b_k \in [e^{-\alpha - \delta}, e^{\alpha + \delta}]$ for all $k \geqslant n$, whence $\limsup\limits_{n\to\infty} b_n \leqslant e^{\alpha + \delta} < e^{\beta}$, contradicting $(2)$. So we must have $b_{n-1} > 1$, and hence

$$b_{n+1} = \frac{1}{2}\biggl(\frac{1}{b_n} + \frac{1}{b_{n-1}}\biggr) < \frac{1}{2}\bigl(e^{\alpha + \delta} + 1\bigr) < e^{\alpha + \delta}.$$

But then we have $b_n, b_{n+1} \in [e^{-\alpha - \delta}, e^{\alpha + \delta}]$ and we obtain the same contradiction. The assumption that $\beta < \alpha$ leads to a contradiction in the analogous way, so we can refine $(2)$ to

$$e^{-\alpha} = \liminf_{n\to\infty} b_n \leqslant 1 \leqslant \limsup_{n\to\infty} b_n = e^{\alpha}.$$

It remains to show that $\alpha = 0$. For that, we first must show that $\alpha$ is "sufficiently small". For arbitrary starting values $b_0,b_1$ that might be a little tedious, so we now concentrate on the specific sequence with $b_0 = b_1 = \frac{1}{\sqrt{2}}$. A few iterations show that then $\alpha \leqslant \frac{1}{10}$.

Now assume that the sequence doesn't converge, i.e. $\alpha > 0$. Choose an $N$ such that $$-\frac{10}{9}\alpha < \log b_n < \frac{10}{9}\alpha$$ for all $n \geqslant N$. If there is an $n > N$ such that $-\frac{2}{3}\alpha \leqslant \log b_n \leqslant \frac{2}{3}\alpha$, then

$$\frac{1}{2}\bigl(e^{-2\alpha/3} + e^{-10\alpha/9}\bigr) < b_{n+1} < \frac{1}{2}\bigl(e^{2\alpha/3} + e^{10\alpha/9}\bigr).$$

But we have $1 - x \leqslant e^{-x} \leqslant 1 - \frac{11}{12}x$ and $1+x \leqslant e^x \leqslant 1 + \frac{13}{12}x$ for $0 \leqslant x \leqslant \frac{1}{9}$, so

$$\frac{1}{2} \bigl(e^{-2\alpha/3} + e^{-10\alpha/9}\bigr) \geqslant \frac{1}{2}\biggl( 1 - \frac{2}{3}\alpha + 1 - \frac{10}{9}\alpha\biggr) = 1 - \frac{8}{9}\alpha \geqslant \exp \biggl(-\frac{32}{33}\alpha\biggr)$$

and

$$\frac{1}{2}\bigl(e^{2\alpha/3} + e^{10\alpha/9}\bigr) \leqslant \frac{1}{2}\biggl( 1 + \frac{13}{18}\alpha + 1 + \frac{65}{54}\alpha\biggr) = 1 + \frac{26}{27}\alpha \leqslant \exp\biggl(\frac{26}{27}\alpha\biggr),$$

which by the first observation shows $-\frac{32}{33}\alpha \leqslant \log b_k \leqslant \frac{32}{33}\alpha$ for all $k \geqslant n$, which contradicts $(2)$.

Hence we must have $b_n < e^{-2\alpha/3}$ or $e^{2\alpha/3} < b_n$ for all $n > N$. But when we look at an $n > N$ with $b_n < e^{-2\alpha/3}$ and $b_{n+1} > e^{2\alpha/3}$, we find that

$$\frac{1}{2}\bigl(e^{-10\alpha/9} + e^{2\alpha/3}\bigr) < b_{n+2} < \frac{1}{2}\bigl(e^{10\alpha/9} + e^{-2\alpha/3}\bigr),$$

and similar to the above

$$\frac{1}{2}\bigl(e^{-10\alpha/9} + e^{2\alpha/3}\bigr) \geqslant \frac{1}{2}\biggl( 1 - \frac{10}{9}\alpha + 1 + \frac{2}{3}\alpha\biggr) = 1 - \frac{2}{9}\alpha \geqslant \exp\biggl(-\frac{8}{33}\alpha\biggr)$$

and

$$\frac{1}{2}\bigl(e^{10\alpha/9} + e^{-2\alpha/3}\bigr) \leqslant \frac{1}{2}\biggl(1 + \frac{65}{54}\alpha + 1 - \frac{11}{18}\alpha\biggr) = 1 + \frac{16}{27}\alpha \leqslant \exp\biggl(\frac{16}{27}\alpha\biggr),$$

which shows that $-\frac{2}{3}\alpha < \log b_{n+2} < \frac{2}{3}\alpha$ and thus again leads to a contradiction.

It follows that the assumption $\alpha > 0$ is untenable, i.e. $\alpha = 0$, or equivalently

$$\lim_{n\to\infty} b_n = 1.$$

This in turn is immediately equivalent to $\lim\limits_{n\to \infty} a_n = \sqrt{2}$.

Answer 2

Graphs, illustrating asymptotic behavior of the sequence $\{a_n\}$. The graphs suggest that $$(a_n-\sqrt{2})\sqrt{2}^n=O(1).$$

Added: