Denominators of Continued Fraction are Strictly Increasing

From ProofWiki

Jump to: navigation, search

Theorem

Let $\left[{a_1, a_2, a_3, \ldots}\right]$ be a continued fraction expansion.

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

Then:

With the possible exception of $q_1 = q_2$, the sequence $\left \langle {q_n}\right \rangle$ is strictly increasing.
For any SCF, $\forall k > 5: q_k > k$.

By definition of simple continued fraction, all partial quotients of $\left[{a_1, a_2, a_3, \ldots}\right]$ are positive, with the possible exception of $a_1$.

So $q_1 = 1, q_2 = a_2$ and $q_3 = a_3 a_2 + 1$ all satisfy $1 = q_1 \le q_2 < q_3$.

Suppose $q_k > q_{k-1} \ge 1$ for some $k \ge 3$.

Then $q_{k+1} = a_{k+1} q_k + q_{k-1} \ge q_k + q_{k-1} \ge q_{k} + 1 > q_k$.

So, by induction, $\left \langle {q_n}\right \rangle$ is strictly increasing except when possibly $q_1 = q_2 = 1$.

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

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

The result follows.

$\blacksquare$