Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
