Show that $a_{n+1}= 1 + \frac{1}{a_n}$ converges. [duplicate]

Solution 1:

Hint. Let $f(x)=1+1/x$ then $f:[3/2,2]\to [3/2,2]$ and for $x\in [3/2,2]$, $$|f(x)-f(y)|= \left|\frac{1}{x}-\frac{1}{y}\right|\leq \frac{4}{9}|x-y|.$$ That is $f$ is a contraction.

Now $a_{n+1}=f(a_n)$ and $a_2=f(a_1)=2$ and by the Banach fixed-point theorem, $(a_n)_n$ tends to the unique fixed point of $f$ in the interval $[3/2,2]$.

Solution 2:

After so many good answers, this one is just for knowledge sharing $$a_1=1, a_2=2, a_3=\frac{3}{2}, a_4=\frac{5}{3}, ...$$ and by induction $$a_n=\frac{F_{n+1}}{F_n}$$ where $\{F_n\}$ are Fibonacci numbers, since $$a_{n+1}=1+\frac{1}{a_n}=1+\frac{F_n}{F_{n+1}}=\frac{F_{n+1}+F_{n}}{F_{n+1}}=\frac{F_{n+2}}{F_{n+1}}$$ and $$\lim\limits_{n\rightarrow \infty}\frac{F_{n+1}}{F_{n}}=\varphi=\frac{1+\sqrt{5}}{2}$$

Solution 3:

Hint: Show that if $a_n < \frac{1 + \sqrt{5}}{2}$ then $a_n < a_{n+2}$. Similarly, show that if $a_n > \frac{1+\sqrt{5}}{2}$, then $a_n > a_{n+2}$.

Solution 4:

So let the limit - assuming there is one - be $a$ and note that $2\gt a\gt 1$ and that $a=1+\frac 1a$ whence $a^2=a+1$.

Now write $a_n=a+e_n$ so that $$a+e_{n+1}=1+\frac 1{a+e_n}$$

On clearing fractions we get $$a^2+ae_{n+1}+ae_n+e_ne_{n+1}=a+e_n+1$$ so that $$e_{n+1}=e_n\cdot\frac {1-a}{a+e_n}=-e_n\cdot\frac {a-1}{a+e_n}$$

Use this to show that the error term alternates in sign and decreases in absolute value - you should be able to show that the error reduces geometrically in magnitude, and therefore tends to zero. If the error tends to zero, you have convergence.

This technique of isolating the error may not be the most efficient, but if you are stuck, it can help to show what is going on. Note that all the terms equivalent to the original equation conveniently drop out - this is quite a general phenomenon, and if it doesn't happen, it's an indication either that there is no limit, or that there has been a mistake in calculation.