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

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$

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.