# Prove that the sequence $(a_n)$ defined by $a_0 = 1$, $a_{n+1} = 1 + \frac 1{a_n}$ is convergent in $\mathbb{R}$

I will post the exercise below:

Prove that the sequence $(a_n)$ defined by $a_0 = 1$, $a_{n+1} = 1 + \frac 1{a_n}$ for $n \in \mathbb N$ is convergent in $\mathbb R$ with the Euclidean metric, and determine afterwards is limit. Can you intepret the limit geometrically (hint: Golden ratio)?

So I need to prove that the sequence is convergent in $\mathbb{R}$ with the Euclidean metric, and how do I prove that? The limit must be $1$, but how to interpret it geometrically?

• All I am willing to say is that "hint: Golden ratio" is a very strong hint. Oct 8, 2013 at 9:43
• The limit is not 1. @Duronman, the series is not monotonically increasing either. Oct 8, 2013 at 9:47
• @AdrianRatnapala true! I wrote too fast, sorry, I thought of $a_n + \frac{1}{a_n}$ because of the $1$. I will delete the comment to avoid confusion. Oct 8, 2013 at 9:54

Hint: If the limit $L$ exists, it must satisfy $L = 1 + \frac{1}{L}$, and so it cannot be 1. The solutions are the roots of the equation $L^2 - L - 1 = 0$, and so $L \in \{\frac{1+\sqrt{5}}{2}, \frac{1-\sqrt{5}}{2} \}$. That's where the golden ratio comes into play. Note also that the limit cannot be $\frac{1-\sqrt{5}}{2}$ since $a_n > 0$ for all $n$.

Let $\phi$ be the golden ratio, which is the only positive real such that $\phi = 1 + 1/\phi$. Now consider the sequence $\epsilon_n = a_n - \phi$. We seek to prove the invariant:

$$|\epsilon_n/\epsilon_0| \le \phi^{-n}.$$

For $n=0$, this is clear by inspection. With some algebra we see that:

$$\epsilon_{n+1} = 1 + {1\over a_n} - \phi = -{\epsilon_n\over a_n\phi}.$$

Now our invariant already implies that $a_n = \phi + \epsilon_n \ge \phi - \phi^{-n}\epsilon_0 \ge 1.$ Therefore

$$|\epsilon_{n+1}| \le \left|{\epsilon_n\over \phi}\right| \le \phi^{-(n+1)}.$$

So our invariant remains after $n \rightarrow n+1$. And therefore for all nonnegative integers $n$ by induction. But since $\phi > 1$, that invariant means that $\epsilon_n$ approaches zero or $a_n$ approaches $\phi$ as $n$ goes to infinity.

Writing out the first few terms will yield a very interesting pattern:

$a_0 = \frac{1}{1}, a_1 =\frac{2}{1}, a_2=\frac{3}{2}, a_3=\frac{5}{3} ...$

Do u see it now. Every term is a ratio of fibonacci nos. i.e. if $T_n$ is the nth fibonacci number starting from 1, then $a_n = \frac{T_{n+2}}{T_{n+1}}$. The limit of this is indeed the golden ratio. Try solving the difference equation to see it in case you are unaware of this result.

As for the proof that the observation is correct and not a coincidence, use induction. We verified the base cases above, so assume $$a_n = \frac{T_{n+2}}{T_{n+1}}$$

Now $$a_{n+1} = 1+ \frac{1}{a_n} = 1 + \frac{T_{n+1}}{T_{n+2}}= \frac{T_{n+2} + T_{n+1}}{T_{n+2}} = \frac{T_{n+3}}{T_{n+2}}$$

Hence proved. $\blacksquare$

• But you still need to prove that the ratios of consecutive Fibonnaci numbers actually converge to anything at all. Oct 10, 2013 at 8:44
• I told OP to solve the difference equation for $a_n = a_{n-1} + a_{n-2}$. From that you can evaluate the limit. Oct 10, 2013 at 8:48
• I am missing some knowledge about difference equations. The easiest method to find that limit (if it exists) I know is to find the roots of the iteration rule translated into a polynomial. But I did not know the limit was guaranteed to exist. Oct 14, 2013 at 18:07
• You are referring to the Z Transform method for solving difference equations. With it, you will get the solution for all n. Then you can proceed by my method. Oct 14, 2013 at 18:45
• Adrian, another way is to get the general solution to the recurrence relation and then just take limits. There will invariably be a dominating term which determines the limit. Dec 22, 2013 at 3:30

We will consider decreasing function $f:(0, \infty)\rightarrow(0,\infty), f(x)=1+\frac{1}{x}$. Function $fof:(0, \infty ) \rightarrow(0, \infty)$ is increasing and therefore subsequence $a_{2n},n\geq0$ is increasing, and subsequence $a_{2n +1},n\geq0$ is decreasing. Because $1\leq a_{2n}<a_{2n +1}\leq2$, it follows that both are converging subsequences with common limit the golden ratio, which is the limit sequence in question.