12

Let $a_0,a_1>0$ be given. Consider the recursive sequence $$a_{n+2}=\frac{1}{a_{n+1}}+\frac{1}{a_n}$$ Prove that $a_n\to\sqrt2$.

I attempted to find a bound for $a_n$ but so far I have only got $a_n>0$. Somebody hints that I might want to use limsup/liminf, but I want to at least put a bound on them first.

Aside from limsup/liminf (which I don't know how to make use of here yet), is there any other method? That, if possible, will be preferable for me since I'm not very used to limsup/liminf.

Or, can we prove that this second-order recursion is stable in some way?

Thanks in advance!

Vim
  • 13,640
  • 1
    @V.C. well, to be honest that's quite different – Vim Oct 23 '15 at 07:15
  • This might help: If $1 \leq a_n \leq 2$ and $1 \leq a_{n+1} \leq 2$, then $\frac{1}{2} \leq \frac{1}{a_{n+1}} \leq 1$ and $\frac{1}{2} \leq \frac{1}{a_n} \leq 1$ so that $1 \leq \frac{1}{a_{n+1}} + \frac{1}{a_n} \leq 2$. – Nex Oct 23 '15 at 07:43
  • @Nex But how to kick start? we have no information about $a_{0,1}$ except that they are positive. – Vim Oct 23 '15 at 07:48
  • 1
    Let $m = \min{a_0, a_1}$ and $M = \max{a_0, a_1}$. Then one can show by induction that $$a_n \in \left[ \min\left{\frac{1}{2M}, m\right} , \max\left{\frac{2}{m}, M\right}\right]$$ –  Oct 23 '15 at 07:49
  • But your sequence don't look to be monotone... –  Oct 23 '15 at 07:50
  • @JohnMa No genrrally it isn't. So the bounded monotone sequence theorem won't be of much help. – Vim Oct 23 '15 at 07:51
  • It seems also to me that the odd and even parts are not monotone too.. –  Oct 23 '15 at 07:52
  • $a_{n+3} = \frac{a_n a_{n+1}}{a_{n+1} + a_{n}} + \frac{a_{n-1}a_n}{a_n + a_{n-1}} \leq \frac{a_{n}a_{n+1}}{2\min{a_{n+1}, a_n}} + \frac{a_{n-1}a_{n}}{2\min{a_{n},a_{n-1}}} \leq \frac{1}{2}( \max{a_{n+1},a_{n}} + \max{a_{n},a_{n-1}})$, and similarly $a_{n+3} \geq \frac{1}{2}( \min{a_{n+1},a_{n}} + \min{a_{n},a_{n-1}})$ – Nex Oct 23 '15 at 07:57
  • Let $A={(x,y)\mid if a_0=x,a_1=y then a_n \to \sqrt 2 }$. can study of connecting of $A$ Help? – Hoseyn Heydari Oct 23 '15 at 08:04
  • 5
    With the substitution $a_n = \sqrt 2/b_n$, $(b_n)$ satisfies $b_{n+2} = 2/(b_n + b_{n+1})$. That sequence is investigated in http://math.stackexchange.com/questions/1475803/how-show-that-a-n-1-le-c-lambda-n-lambda-in-0-1 and converges to $1$. – Martin R Oct 23 '15 at 08:14

2 Answers2

5

For those who are interested, one can solve this using $\liminf$, $\limsup$ (So this does not quite meet the OP's requirement). The idea is described in another answer linked in the comment.

First of all one can show that $a_n$ is bounded. Let $$\ell = \liminf_{n\to \infty} a_n, \ \ L = \limsup_{n\to \infty} a_n.$$

By the definition of $\ell$, one can find a subsequence $\{a_{n_k}\}$ so that $a_{n_k} \to \ell$. By picking a subsequence, we also assume that

$$a_{n_k - 1} \to \ell_1,\ \ a_{n_k -2} \to \ell_2\ \ \ \text{as }k\to \infty.$$

Then taking $k\to \infty$ of

$$a_{n_k} = \frac{1}{a_{n_k-1}} + \frac{1}{a_{n_k-2}},$$

we have

$$\ell = \frac{1}{\ell_1 } + \frac{1}{\ell_2} \ge \frac{1}{L} + \frac{1}{L} = \frac{2}{L} \Rightarrow \ell L \ge 2$$

Similarly by taking a subsequence going to $L$, we have $\ell L \le 2$. Thus $\ell L = 2$.

Now we show that $\ell =L =\sqrt 2$. Then this implies $a_n \to \sqrt 2$ as $n\to \infty$.

Similarly, let $a_{n_k}$ converges to $L$ and $a_{n_k-1} \to \ell_1$, $a_{n_k -2} \to \ell_2$ and $a_{n_k - 3} \to \ell_3$. Then we have

$$\frac {2}{\ell} = L = \frac{1}{\ell_1} + \frac{1}{\ell_2}$$

and

$$\ell_1 = \frac{1}{\ell_2} + \frac{1}{\ell_3}.$$

The first equality actually forces $\ell_1 = \ell_2 = \ell$. Put this into the second equality gives

$$\frac{2}{L} = \ell = \frac{1}{\ell } + \frac{1}{\ell_3}.$$

This again forces $\ell = \ell_3 = L$. Thus $\ell = L = \sqrt 2$.

Community
  • 1
  • Thanks :). Well, I did not say I reject limsup/inf, they are accepatable, but not very attractive to me. – Vim Oct 23 '15 at 09:51
  • Another question yet. How to prove that $a_{n_k-1}$ or $a_{n_k-2}$ converges? I tried using Cauchy criterion but it doesn't seem to work. – Vim Oct 25 '15 at 14:21
  • 1
    I am using the fact that a bounded sequence must have a convergent subsequence. After choosing $a_{n_k}$, the sequence $a_{n_k-1}$ might not converge. But I can take a subsequence of ${a_{n_k -1}}$ (and still call it $a_{n_k-1}$) so that it converges. Same for $a_{n_k-2}$. @Vim –  Oct 25 '15 at 17:02
  • Thanks. Makes sense now. {} – Vim Oct 25 '15 at 17:40
2

Hint:

From experimental data, one sees that the difference with $\sqrt2$ decreases exponentially with a common ratio $0.70\cdots$, so that one is tempted to try $a_n=\sqrt2+ar^n$.

Then for large $n$,

$$\sqrt2+ar^{n+2}=\frac1{\sqrt2+ar^{n+1}}+\frac1{\sqrt2+ar^n}\approx \frac1{\sqrt2}-\frac {ar^{n+1}}2+\frac1{\sqrt2}-\frac {ar^{n}}2.$$

This is a linear recurrence and the characteristic equation yields

$$r=\frac{-1\pm i\sqrt7}{4}=\frac1{\sqrt2}e^{\pm i\arctan(\sqrt7)}.$$

It should be possible to show that the absolute error is bounded by $$\frac a{\sqrt2^n}$$ for some $a$ and $N\le n$ (function of the initial conditions).

  • 1
    I don't think you can treat $a$ as a constant.. – Vim Oct 23 '15 at 09:19
  • This is an approximation, but a good one. It explains both the exponential decay and the apparent irregularity of the values (sinusoid sampled out of sync). –  Oct 23 '15 at 09:24