Lower Bounds for Denominators of Simple Continued Fraction

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \N \cup \{\infty\}$ be an extended natural number.

Let $\left[{a_0, a_1, a_2, \ldots}\right]$ be a simple continued fraction in $\R$ of length $N$.

Let $q_0, q_1, q_2, \ldots$ be its denominators.


Denominator is larger than index

For all $k > 4 : q_k > k$.


Denominator is at least Fibonacci number

Let $F_k$ denote the $k$th Fibonacci number.


For all $k \geq 0$, $q_k \geq F_{k+1}$.


Proof

By Denominators of Simple Continued Fraction are Strictly Increasing, with the possible exception of $1 = q_0 = q_1$, the sequence $\left \langle {q_n}\right \rangle$ is strictly increasing.

Now, since $q_2 > q_1 \ge q_0 = 1$, we have $q_2 \geq 2$.

Then $q_{k+1} \ge q_k + q_{k-1}$ shows that from $q_3$ onwards, the $q_k$s increase in steps of at least $2$.

As $q_3 \ge 3$, it follows that $q_4 \ge 5$.

The result follows.

$\blacksquare$