Showing convergence of recursive sequence $A_{n+1}=\frac 1 {1+A_n}$

Question

Given : $\forall n\in\Bbb N,\quad A_{n+1} = \frac 1 {1+A_n}$ and $A_1 = 0$

Show the sequence converges and find its limit.

Briefly what I did was to create two sub-sequences with an index difference of 2. Doing that I got two recursive formulas that depend on the initial A1, be it 0 for the odds or 1 for the evens. After showing the sequences are bounded, I got stuck showing the sequence is monotonic. Thanks,

Answer 1

Let $\phi=(1+\sqrt{5})/2$ and consider $B_n=|A_n-(\phi-1)|$. Then, $$ B_{n+1} = |A_{n+1}-(\phi-1)| = \left|\frac{1}{1+A_n}-\frac{1}{\phi}\right| = \left|\frac{A_n-(\phi-1)}{(1+A_n)\phi}\right| = \frac{B_n}{(1+A_n)\phi}. $$ Since $0<A_n<1$ for $n>1$ (shown readily by induction: $A_2=1/2$, and $0<\frac{1}{1+1} < \frac{1}{1+A_n} = A_{n+1} < \frac{1}{1+0} = 1$), we have $B_{n+1}<B_n$, which establishes ${B_n}$ as a decreasing sequence. Since $B_n \geq 0$ by construction, it must converge.

Answer 2

It seems that, for $n\ge 2$, $A_n=f_{n-1}/f_{n}$, where $f_n$ is the $n$-th Fibonacci number, so $\{A_n\}$ converges to $\frac {\sqrt{5}-1}2.$

Answer 3

The sequences $(A_{2n})$ and $(A_{2n+1})$ are obtained by iterating the function $$u:x\mapsto\frac{1+x}{2+x}=1-\frac{1}{2+x},$$ starting from $A_2=1$ and from $A_1=0$ respectively.

• The function $u$ is increasing and $u(1)=\frac23\lt1$ hence $(A_{2n})$ is decreasing.
• The function $u$ is increasing and $u(0)=\frac12\gt0$ hence $(A_{2n+1})$ is increasing.

Since both sequences are bounded (every $A_n$ is in $[0,1]$), both converge to a fixed point of $u$. The function $u$ has a unique fixed point $\ell$ in $[0,1]$ hence both sequences converge to $\ell$, which implies that $(A_n)$ itself converges to $\ell$.

Finally, $u(\ell)=\ell$ implies that $\ell^2+\ell=1$, that is, $\ell=\frac12(\sqrt5-1)$, which is (related to) the golden ratio.

Answer 4

The recurrence is of the form $$x_{n+1} = \phi(x_n)$$ where $\phi(x) = \frac{1}{1+x}$. The map $\phi$ has two fixed points $x_{1,2}$, roots of the equation $x^2 + x -1=0$, that is $\frac{-1\pm \sqrt{5}}{2}$. Now, we can write $\phi(x)$ in the form $$\frac{\phi(x) -x_1}{\phi(x) - x_2} = k \cdot \frac{x-x_1}{x-x_2}$$ $k$ can be determined by givind a particular value for $x$, say $x=0$. We get $$\frac{1-x_1}{1-x_2} = k \frac{x_1}{x_2}$$ and so $$k = \frac{x_2(1-x_1)}{x_1(1-x_2)} = \frac{x_2 + 1}{x_1 + 1}=\frac{1-\sqrt{5}}{1+\sqrt{5}}$$

We get $$\frac{\phi(x) -x_1}{\phi(x) - x_2} = \frac{1-\sqrt{5}}{1+\sqrt{5}} \cdot \frac{x-x_1}{x-x_2}$$

In other words, $\phi$ is conjugate to the map $t \mapsto \frac{1-\sqrt{5}}{1+ \sqrt{5}}\cdot t$. The monotony and convergence should be easy now.