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

Let $\{a_n\}$ be defined by $a_1 =1$ and $a_{n+1} = 1 + {\dfrac{1}{a_n}}$ with $n \in N$.

Show that $a_{n+1}= 1 + {\dfrac{1}{a_n}}$ converges.

I know the limit but how can I show that is a Cauchy sequence or that this sequence converges.

## marked as duplicate by Michael Lee, Rolf Hoyer, Misha Lavrov, Krish, JonMark PerryNov 23 '17 at 8:33

• Golden ratio in disguise :) – Math Lover Nov 14 '17 at 18:23
• @MathLover, Yes, they said that they know the limit, but you still need to show convergence before you can just find the fixed point. – Marcus M Nov 14 '17 at 18:25
• This is the continued fraction of the Golden Ratio $$\phi=\frac{1+\sqrt 5}{2}$$ – Raffaele Nov 14 '17 at 18:31
• – Sil Nov 17 '17 at 7:28

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

• ¸Nice one +1.... – Aqua Nov 15 '17 at 16:30

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

• Nice one +1......... – Aqua Nov 15 '17 at 16:30

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

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.

• Thank you very much! I showed that $|e_n| \geq |e_{n+1}|$, hence $|e_n|$ is falling monotonously and limited so |e_n| is converged, but why $\rightarrow e_n$ is converged ? – Anna Saabel Nov 14 '17 at 20:14
• @AnnaSaabel So if, for example, you have a situation where $1.5\lt a \lt 1.7$ and $|e_n|\lt 0.1$ then $|e_{n+1}|\lt \frac {0.7}{1.4} |e_n|$ and the error halves in magnitude each time. So once you are close you get closer very quickly, and the error tends to zero. – Mark Bennet Nov 14 '17 at 21:14
• okay, but how can i prove that the error tends to zero ? – Anna Saabel Nov 14 '17 at 21:22
• @AnnaSaabel So the series goes $1, \frac 32, \frac 53, \frac 85 =1.6$. The errors alternate in sign, so $\frac 53 -\frac 85=\frac 1{15}$ is bigger than the error ar $\frac 85$ (we added the previous error to it). So the error is already less than $\frac 1{10}$ and the value is in the range I suggested, so the error is halving after that. So $|e_{n+4}|\lt 2^{-n}|e_4|$ which is a constant multiple of $2^{-n}$ and $2^{-n}\to 0$ – Mark Bennet Nov 14 '17 at 21:50

Here is yet another answer: Observe that $a_n \geq 1$ for all $n \in \{1, 2, 3, ...\}$. Let $b=\frac{1}{2}(1+\sqrt{5})$, which satisfies $b = 1+\frac{1}{b}$ and $b>1$. Then for all $n \in \{1, 2, 3, ...\}$: $$|a_{n+1}-b| = |(1+\frac{1}{a_n}) - (1 + \frac{1}{b})| = \frac{|a_n-b|}{a_nb} \leq \frac{|a_n-b|}{b}$$ where the last inequality uses $a_n\geq 1$. The error decreases exponentially fast.

• It seems this is similar to the Robert Z answer, except I am comparing directly with the limiting point $b$ rather than proving a general contraction property for a function $f(x)$ over a certain interval. – Michael Nov 14 '17 at 20:17

As Marcus M said, first $a_{n+2}=\frac{2a_n+1}{a_n+1}$ showing those properties. Then show $\{a_{2n}\}$ and $\{a_{2n+1}\}$ really convergent to that value.

E.g. for $\{a_{2n}\}$, because of the fact that $f(x)=\frac{2x+1}{x+1}$ is strictly increasing and $x>f(x)$ when $x>\frac{\sqrt{5}+1}{2}:=g$. Assume the limit (infimum) is $x^*>g$, for all $x\geqslant x^*$. If There are always points from $[x^*,x^*+\delta)$. If $\exists\hat{x}, f(\hat{x})\leq x^*$, then $f(f(\hat{x}))=f(x^*)<x^*$ contradict to

Let $f(x) = 1+{1\over x}$. We have $f([1,2]) \subset [1,2]$. Since $f(1) = 2 > 1$ and $f(2) = {3 \over 2} < 2$ we see that $f$ has a fixed point in $[1,2]$.

Note that $\phi(x) = f(f(x)) = {2x+1 \over x+1}$ satisfies $0 \le \phi'(x) \le {1 \over 4}$ for $x \in [1,2]$ hence has a unique (in $[1,2]$) fixed point $x^*$ and hence $x_{2n+1} \to x^*$ for some $x^* \in [1,2]$. Note that any fixed point of $f$ is a fixed point of $\phi$, hence $x^*$ is the fixed point of $f$ and it follows that $x_{2n+2} = f(x_{2n+1})$ converges to $x^*$ as well.