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

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

• There doesn't even seem to be any kind of pattern like every other one is smaller and every other one larger than the limit. It's like if you get two sufficiently large ones next to each other than you get smaller one and vice versa. Apr 8, 2015 at 22:15
• I can show $|a_{n+2}-a_{n+1}|\leq \frac23|a_{n+1}-a_{n-1}|,$ but I don't see that being useful. Apr 8, 2015 at 22:26
• The numerical calculation of the sequence suggests that it indeed converges to $\sqrt{2}$. Apr 9, 2015 at 1:10
• @AlexRavsky: Hint: $x^2~=~2~\iff~x~=~\dfrac2x~=~\dfrac1x+\dfrac1x$ Apr 9, 2015 at 1:24
• It seems that we can easily prove by induction that $Ca^k>a_{3k}-\sqrt{2}>0$, $Ca^k>\sqrt{2}-a_{3k+1}>0$, $Ca^k>\sqrt{2}-a_{3k+2}>0$ for some $C>0$ and $a<1$ for each not very small $k$. Apr 9, 2015 at 2:51

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

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