Proof of existence of a limit for the sequence recursively-defined with $a_1=1$, $a_2=1$ and $a_n=\frac{1}{a_{n-1}}+\frac{1}{a_{n-2}}$ for $n\ge2$

Question

I have a sequence defined by $$ a_1=1,\quad a_2=1,\quad a_n=\frac{1}{a_{n-1}}+\frac{1}{a_{n-2}}\text{ for } n\ge2\text. $$ Now, if $\lim\limits_{n\to \infty}a_n=g$ then $\lim\limits_{n\to \infty}a_n=\lim\limits_{n\to \infty}\Bigl(\frac{1}{a_{n-1}}+\frac{1}{a_{n-2}}\Bigr)=\frac{2}{g}$, so $g=\sqrt{2}$ or $g=-\sqrt{2}$, but $a_n>0$, so $g=\sqrt{2}$.

Now, how do I prove that it has an actual limit? Also, it can be proven that $1\le a_n\le2$, and it's not monotonic because $a_4 \gt a_5 \lt a_6$. Also, it's not monotonic after any $N\in\mathbb N$.

Answer 1

As you mention, it is straightforward to prove by induction that $1 \le a_n \le 2$, for all $n \ge 1$.

Let $L = \limsup_{n\to\infty} a_n$, $l = \liminf_{n\to\infty} a_n$, we have $1 \le l, L\le 2$. For any $\varepsilon>0$, we know that $l - \varepsilon \le a_n \le L + \varepsilon$, if $n$ is sufficiently large. Thus, for $n$ large enough $$ \frac{2}{L+\varepsilon} \le a_n \le \frac{2}{l-\varepsilon}. $$ Since $\varepsilon$ can be chosen to be arbitrarily small, we get $$ L = \limsup_{n\to\infty} a_n \le \frac{2}{l}, \,\, l = \liminf_{n\to\infty} a_n \ge \frac{2}{L},$$ hence $L \cdot l =2$.

Now, we may choose a subsequence $\{n_k\}$ such that, as $k\to\infty$, $$ a_{n_k + 1} \to L,\, a_{n_k} \to l_1,\, a_{n_k - 1} \to l_2,\, a_{n_k - 2} \to l_3, $$ for some $l_1, l_2, l_3 \in [l,L]$. By the definition of the sequence $a_n$, we have $$ \frac{2}{l} = L = \frac{1}{l_1} + \frac{1}{l_2},\quad l_1 = \frac{1}{l_2} + \frac{1}{l_3}. $$ The left equality implies $l_1 = l_2 = l$, and then, using $\frac{2}{L} = l = l_1$, the right equality gives $l_2 = l_3 = L.$ Therefore, $l = L$, and since $L \cdot l = 2$, we find that the limit is $\sqrt{2}$.

Answer 2

To be able to do $$g=\lim_{n\to\infty}a_n=\lim_{n\to\infty}\frac{1}{a_{n-1}}+\frac{1}{a_{n-2}}=\frac{2}{g}$$ you should prove first that the sequence is bounded and some how it gets arbitrarily close to the candidate for limit, and therefore convergent. For example, let $c_n$ be a sequence of positive real numbers, if for all $n\in\mathbb{N}$ $c_n\leq M$ for some $M\geq 0$ and for all $N\in\mathbb{N}$ exists $n_0\in\mathbb{N}$ such that $c_n\geq c_{N}$ for all $n\geq n_0$, then $c_n$ is convergent, not necessarily to $M$. Only then you're able to manipulate limits as you wish to find the actual limit.

Otherwise you may end up with stuff like this: Take $b_1=1$ and $b_n=1+b_{n-1}^{2}$, if $\lim_{n\to\infty}b_n=g$ then $$g=\lim_{n\to\infty}b_n=\lim_{n\to\infty}1+b_{n-1}^{2}=1+g^{2}$$ so $g=1\pm i\sqrt{3}$ which clearly doesn't make sense.

Answer 3

I don't really have a good idea, but just to say something moderately meaningful instead of my original totally incorrect answer: We can in principle at least establish this by a brute force approach (assuming the statement is correct), as follows:

Consider the map $f(x,y)=(1/x+1/y,x)$. Note that $(a_{n+1},a_n)$ is obtained by iterating $f$, starting from $(1,1)$. It is now easy to show that $(\sqrt{2},\sqrt{2})$ is an attracting fixed point of $f$, by a calculation: $$ Df(\sqrt{2},\sqrt{2}) = \begin{pmatrix} -1/2 & -1/2 \\ 1 & 0 \end{pmatrix}, $$ and this matrix has two eigenvalues of absolute value $1/\sqrt{2}<1$.

So once we get close enough to $(\sqrt{2},\sqrt{2})$, we will get sucked in. We could now (in principle) iterate by hand sufficiently many times to confirm that we do get sufficiently close to the fixed point (and we would also need precise estimates on what exactly that means, which could be done by estimating the second derivative of $f$ also).

Answer 4

New revised answer, using only elementary properties of sequences: In order to avoid scattering too many $\sqrt{2}$'s in the text I will normalize differently and write $a_n=\sqrt{2} x_n$. The $x_n$'s then verify:

$$ x_{n+2}=\frac12 \left( \frac{1}{x_{n+1}} + \frac{1}{x_n} \right).$$ We will show the following:

Theorem: For any $x_0,x_1>0$ the sequence $x_n$ converges to 1. Moreover, if $\delta_0= \max\{x_0,x_1,\frac{1}{x_0},\frac{1}{x_1}\} -1$ (which is $\geq 0$) then for all $n\geq 0$: $$ |x_n-1| \leq 2 \left(\frac{3}{4}\right)^{\lfloor n/3 \rfloor} \delta_0 .$$

[This implies that the original sequence $a_n$ converges to $\sqrt{2}$ at the same exponential rate, whence solving the stated problem.]

Proof of the Theorem:
We will use a couple of times that for $b,c>0$ we have the straightforward bound (which is easily seen to be equivalent to $(b-c)^2\geq 0$): $$ \frac{1}{2} \left(\frac{1}{b} + \frac{1}{c}\right) \geq \frac{2}{b+c} \ \ \ (*)$$

Define for $\delta>0$ the interval: $$ I_\delta = \left[\frac{1}{1+\delta}, 1+\delta \right].$$ If $\delta>0$ and $x_n,x_{n+1}\in I_\delta$ then clearly $$\frac{1}{1+\delta}\leq x_{n+2}=\frac{1}{2} \left( \frac{1}{x_{n+1}}+\frac{1}{x_n}\right)\leq 1+\delta$$ so by induction $x_{n+k}\in I_\delta$ for every $k\geq 0$.

Let us say that the pair $(x_{n},x_{n+1})$ is 'well-separated' if $x_{n}\leq 1\leq x_{n+1}$ or $x_n\geq 1\geq x_{n+1}$. If $(x_{n},x_{n+1})$ is not well-separated then the pair $(x_{n+1},x_{n+2})$ is going to be well-separated (e.g. if $x_n,x_{n+1}\leq 1$ then $x_{n+2}=1/2(1/x_{n}+1/x_{n+1})\geq 1$) so at least every second consecutive pair is necessarily well-separated.

When $(x_n,x_{n+1})$ is a well-separated pair then $$ x_{n+2} \leq \frac{1}{2} \left( 1 + (1+\delta) \right) =1 + \delta/2$$ and $$ x_{n+2} \geq \frac{1}{2} \left( \frac{1}{1+\delta} + \frac{1}{1} \right) \geq \frac{2}{2+\delta} = \frac{1}{1+\delta/2}$$ where I used the bound $(*)$. So $x_{n+2}\in I_{\delta/2}$. But then we also have: $$ x_{n+3} \leq \frac{1}{2} \left( (1+\delta/2) + (1+\delta) \right) =1 + \frac34\delta$$ and (again using the bound $(*)$): $$ x_{n+3} \geq \frac{1}{2} \left( \frac{1}{1+\delta/2} + \frac{1}{1+\delta} \right) \geq \frac{2}{2+\frac32 \delta} = \frac{1}{1+\frac34 \delta}$$ So $x_{n+3}\in I_{\frac34 \delta}$. If the pair $(x_{n},x_{n+1})$ was not well-separated then $(x_{n+1},x_{n+2})$ is well-separated and we obtain the same inclusions after one more iteration. Combining the two cases we find that whenever
$x_{n+k}\in I_\delta$ for $k\geq 0$ then $x_{n+3+k} \in I_{\frac 34 \delta}$ for $k\geq 0$. In particular when $x_{k}\in I_{\delta_0}$ for all $k\geq 0$ we obtain through induction that $$x_{3n +k} \in I_{(\frac{3}{4})^n \delta_0}, \ \ n,k\geq 0$$ and from this $$|x_{3n +k}-1| \leq 2 (\frac{3}{4})^n \delta_0, \ \ \ n,k\geq 0$$ which translates into the stated estimate whence proving the theorem.

Answer 5

Let us prove that $\lim_{n\to\infty}a_n=\sqrt2.$ There is sufficiently to prove that $$\lim_{n\to\infty}b_n=\dfrac{\sqrt2}2,$$ for $$b_n=\dfrac1{a_n},$$ wherein $$b_1=b_2=1,\quad b_{n}=\dfrac1{b_{n-1}+b_{n-2}}, n=3,4\dots.$$ The first eleven values of difference, calculated in Mathcad package, are there: ,

so $$b_6-\dfrac{\sqrt2}2=\varepsilon_6,\quad b_7-\dfrac{\sqrt2}2=\varepsilon_7,\quad \varepsilon_6<\varepsilon,\quad \varepsilon_7<\varepsilon,\quad \varepsilon=0.06.$$ Note that $$b_8=\dfrac1{b_6+b_7}=\dfrac1{\dfrac{\sqrt2}2+\varepsilon_6+\dfrac{\sqrt2}2+\varepsilon_7}=\dfrac1{\sqrt2+\varepsilon_6+\varepsilon_7},$$ then $$\varepsilon_9=\dfrac1{b_7+b_8}-\dfrac{\sqrt2}2=\dfrac1{\dfrac{\sqrt2}2+\varepsilon_7+\dfrac1{\sqrt2+\varepsilon_6+\varepsilon_7}}-\dfrac{\sqrt2}2$$ $$ = \dfrac{\varepsilon_6-\varepsilon_7-\varepsilon_7\sqrt2(\varepsilon_6+\varepsilon_7)}{4+\sqrt2(3\varepsilon_7+\varepsilon_6)+2\varepsilon_7(\varepsilon_6+\varepsilon_7)}.$$ This means that

$$|\varepsilon_9|<\dfrac{2\varepsilon(1+\varepsilon\sqrt2)}{4(1-\varepsilon\sqrt2-\varepsilon^2)}<\dfrac{\sqrt2}2\varepsilon.$$

Similarly $$|\varepsilon_{7+2k}|<\left(\dfrac{\sqrt2}2\right)^k\varepsilon,$$ thus, we can garantee that for any given value $\varepsilon^*\in(0,\varepsilon)$ $$|\varepsilon_{7+2k^*}|<\varepsilon^*,$$ where $$k^*=2\left[\log_2{\dfrac{\varepsilon}{\varepsilon^*}}+1\right].$$

For any $\varepsilon^*>0$ exists $k^*(\varepsilon^*)$ such that for any $n>k^*$ $$\left|b_n-\dfrac{\sqrt2}2\right|<\varepsilon^*.$$ That means that $$\lim_{n\to\infty}b_n=\dfrac1{\sqrt2},$$ $$\boxed{\lim_{n\to\infty}a_n=\sqrt2.}$$