Prove that the sequence of Fibonacci quotients is Cauchy

Question

Consider the sequence defined by $a_1 = 1$ and $a_n =\frac{1}{1 + a_{n−1}}$ for all $n ≥ 2$. In general, this sequence can also be described as the sequence of quotients of succesive terms in the Fibonacci sequence. Prove that $(a_n)_{n\in \Bbb N}$ is a Cauchy sequence.

Answer 1

Do you know that the ratios of terms in the Fibonacci sequence converge to the Golden ratio? And of course, convergent sequences are always Cauchy.

Answer 2

Given the Fibonacci sequence where $a_{n+1} = a_n + a_{n-1}$, we have with $b_n = a_n/a_{n-1},$

$$\begin{align} |b_{n+1} - b_{n}| &= \left|\frac{a_{n+1}}{a_n}- \frac{a_{n}}{a_{n-1}} \right| \\ &= \left|\frac{a_{n+1}a_{n-1} - a_n^2}{a_n a_{n-1}} \right| \\ &= \left|\frac{a_na_{n-1} + a_{n-1.}^2 - a_n a_{n-1} - a_n a_{n-2}}{a_{n-1}^2 + a_{n-1}a_{n-2}} \right|. \end{align}$$

Note that the sequence is increasing and $a_{n-1}^2 + a_{n-1}a_{n-2} > 2 a_{n-1}a_{n-2}.$

Hence,

$$\begin{align} |b_{n+1} - b_{n}| &< \left|\frac{a_{n-1}^2 - a_{n}a_{n-2}}{2 a_{n-1}a_{n-2}}\right| \\ &= \frac{1}{2}\left|\frac{a_n}{a_{n-1}} - \frac{a_{n-1}}{a_{n-2}}\right| \end{align}.$$

By induction we can show that

$$|b_{n+1} - b_{n}| < \left(\frac{1}{2} \right)^{n-2}\left|\frac{a_2}{a_1} - \frac{a_1}{a_0} \right| = \left(\frac{1}{2} \right)^{n-2},$$

and

$$|b_{n+k} - b_{n}| < \sum_{j=0}^{k-1} (1/2)^{n-2 +j} = (1/2)^{n-2} \frac{1 - (1/2)^k}{1 - 1/2} < (1/2)^{n-3}.$$

Since the RHS converges to $0$ as $n \to \infty$ the sequence is Cauchy.