Limit behaviour of Fibonacci sequence

[PeroK]

TL;DR

Ratio of terms in the Fibonacci sequence.

I thought this might be quite interesting to anyone who hasn't seen it before.

Consider any Fibonacci sequence, where $F_1 > F_0 \ge 0$ and $F_{n+1} = F_n + F_{n-1} \ (n > 1)$. We want to show that the ratio of consecutive terms, $a_n = \dfrac{F_{n+1}}{F_n}$ tends to the Golden Ratio: $\varphi = \dfrac{1 + \sqrt 5}{2}$.

First, note that $1 \le a_n \le 2 \ (n \ge 1)$. The sequence is increasing and no term can be more than twice the previous term.

Note that:
$$a_{n + 1} = \frac{F_{n+2}}{F_{n+1}} = \frac{F_{n+1} + F_n}{F_{n+1}} = \frac{(a_n + 1)F_n}{a_nF_n} = \frac{a_n + 1}{a_n} = 1 + \frac 1 {a_n}$$Hence:
$$a_{n+1 } > \varphi \ \Leftrightarrow \ 1 + \frac 1 {a_n} > \varphi \ \Leftrightarrow \ a_n < \frac 1{\varphi - 1}= \varphi$$This last equality follows from the characteristic quadratic equation that defines $\varphi$:
$$\varphi^2 - \varphi -1 = 0 \ \implies \ \varphi(\varphi-1) = 1 \ \implies \ \varphi = \frac 1 {\varphi - 1}$$So:

If $a_n < \varphi$, then $a_{n+1} > \varphi$; and, if $a_n > \varphi$, then $a_{n+1} < \varphi$.

This means that $a_n$ is composed of two subsequences, alternating between above and below the Golden Ratio.

Note also that if $a_n = \varphi$, then $a_{n+1} = \varphi$ and the sequence is constant thereafter. This can only happen, however, when $F_1 = \varphi F_0$.

If you know a bit of real analysis, you see that it is enough to show that the subsequence less than $\varphi$ is strictly increasing; and, the subsequence above $\varphi$ is strictly decreasing. This guarantees that both subsequences converge to $\varphi$ - as that is the only possible limit.

To see this, we need to compare $a_{n+2}$ with $a_n$:
$$a_{n+2} = \frac{F_{n+3}}{F_{n+2}} = \frac{F_{n+2} + F_{n+1}}{F_{n+1} + F_n} = \frac{(2a_n + 1)F_n}{(a_n+1)F_n} = \frac{2a_n + 1}{a_n +1}$$Hence:
$$a_n - a_{n+2} = \frac{a_n^2 + a_n - 2a_n - 1}{a_n + 1} = \frac{a_n^2 - a_n - 1}{a_n + 1}$$And we see that:

If $1 < a_n < \varphi$, then $a_n^2 - a_n - 1 < 0$ and $1 < a_n < a_{n+2} < \varphi$; and

if $\varphi < a_n$, then $a_n^2 - a_n - 1 > 0$ and $\varphi < a_{n+2} < a_n$.

And, as required, we have two monotonic subsequences that must both converge to $\varphi$.

Note that to prove this last bit rigorously, you need some work, which may not add very much here.

 

[pasmith]

There is a much easier way to arrive at these results.

From $a_{n+1} = 1 + a_n^{-1}$ and the definition of $\varphi$ we can obtain $$
a_{n+1} - \varphi = (-1)\frac{a_n - \varphi}{a_n\varphi}.$$ Assuming $a_n \geq 1$ we have $a_n \varphi \geq \varphi > 1$ so that $$
|a_{n+1} - \varphi| < |a_n - \varphi|.$$ This is sufficient to conclude that $a_n \to \varphi$. The factor of $-1$ on the right means that if $a_n < \varphi$ then $a_{n+1} > \varphi$ etc.

 

[PeroK]

There is a much easier way to arrive at these results.

From $a_{n+1} = 1 + a_n^{-1}$ and the definition of $\varphi$ we can obtain $$
a_{n+1} - \varphi = (-1)\frac{a_n - \varphi}{a_n\varphi}.$$ Assuming $a_n \geq 1$ we have $a_n \varphi \geq \varphi > 1$ so that $$

That is useful.

|a_{n+1} - \varphi| < |a_n - \varphi|.$$ This is sufficient to conclude that $a_n \to \varphi$.

I didn't think this was sufficient, as we could have the odd terms and even terms both converging to different limits less than and greater than $\varphi$.

The additional equation that I thought was needed was:
$$a_n - a_{n+2} = \frac{a_n^2 - a_n - 1}{a_n + 1}$$This ties the odd or even sequence to the function values. Because $x^2 - x - 1$ has only one zero on $(1, 2)$, the only way that $a_n^2 - a_n - 1$ can tend to zero is if $a_n$ tends to $\varphi$.

 

[pasmith]

A slight correction is indeed required.

From $a_n \geq 1$ we have $a_n \varphi \geq \varphi$ so that $$
|a_{n+1} - \varphi| \leq \frac{1}{\varphi} |a_n - \varphi|$$ which together with $\varphi > 1$ is sufficient for $a_n \to \varphi$.

 

[pasmith]

Alternatively, we can also consider that the general solution of $F_{n+2} = F_{n+1} + F_n$ is $$\begin{split}
F_n &= A \left( \frac{1 + \sqrt{5}}{2}\right)^n + B\left( \frac{1 - \sqrt{5}}{2}\right)^n \\
&= A \varphi^n + B (-\varphi^{-1})^n \\
&= \varphi^n \left(A + B (-\varphi^{-2})^{n}\right)
\end{split}
$$ for some constants $A$ and $B$. For an integer sequence, $B$ must be the conjugate of $A$ in $\mathbb{Q}[\sqrt{5}]$ so that if $A = a + b\sqrt{5}$ then $B = a - b\sqrt{5}$ for rational $a$ and $b$. For the case $F_0 = 0, F_1 = 1$ we in fact have $a = 0$ and $b = \frac15$.

From the last expression for $F_n$ we have $$
\frac{F_{n+1}}{F_n} = \varphi \frac{ A +B \left( - \varphi^{-2} \right)^{n+1} }
{ A + B \left( - \varphi^{-2} \right)^{n} }$$ and some basic analysis shows that as $n \to \infty$ for $A \neq 0$ the fraction tends to 1. It is also easy to see that $(F_n)$ alternates between terms which are greater than and less than $A\varphi^n$, with $(F_{n+1}/F_n)$ therefore alternatiing between terms which are greater than and less than $\varphi$.