Basic Results

Theorem: Let \(a\) be a nonnegative real. If \(a\) is irrational, it has a unique simple continued fraction expansion. Otherwise there are exactly two expansions representing \(a\), namely \([a_1,...,a_{n-1},a_n, 1]\) and \([a_1,...,a_{n-1},a_n + 1]\).

Proof: Let \(x_i = [a_i; a_{i+1}, ...]\) for all \(i\). Then

\[ x_i = a_i + \frac{1}{x_{i+1}} \]

By inductive assumption \(a_1, ..., a_{i-1}\) are uniquely determined.

We have \(x_{i+1} \ge 1\) since \(a_{i+1}\) is a positive integer. If \(x_{i+1} \gt 1\), then \(a_i = \lfloor x_i \rfloor\) and uniqueness of \(a_i\) follows by induction. Otherwise \(x_{i+1} = 1\) and the fraction must terminate here. Then \(a\) is rational and we could discard \(a_{i+1}\) and add one to \(a_i\).∎

Actually there’s a hole in the proof. We neglected to rule out that an infinite continued fraction cannot approach a rational. We show this once we derive some bounds.

Define \(x_i\) as in the proof. Then by induction,

\[ a = \frac{x_{k+1} p_k + p_{k-1}}{x_{k+1} q_k + q_{k-1}} \]

Observe that to convert a rational \(p/q\) to a simple continued fraction, we perform Euclid’s algortihm on \(p\) and \(q\). The quotients become the continued fraction sequence.

The recurrence relation of continued fractions is also related to division with remainder in the Euclid’s algorithm.

Theorem: Let \(a, b\) be coprime. If \(a/b\) is expanded into a continued fraction, then \(q_{n-1}, p_{n-1}\) is a solution of \(a x- b y = (-1)^n\) where \(n\) is the number of convergents.

Proof: We have \(p_n = a, q_n =b\) and \(p_k q_{k-1} - q_k p_{k-1} = (-1)^k\) for all \(k\).∎

Lemma: For any distinct rationals \(p/q\) and \(p'/q'\), the sequence

\[ \frac{p}{q} , \frac{p x + p'}{q x + q'} , \frac{p'}{q'} \]

is strictly increasing, or strictly decreasing for any nonnegative real \(x\).

Proof: Calculation shows the sign of \(p q' - p'q\) determines the direction of the sequence.∎

Visualizing the graph of \(y = \frac{p x + p'}{q x + q'}\) for nonnegative \(x\) is instructive. We have part of a hyperbola with \(y\)-intercept \(y = p'/q'\) at \(x = 0\), and \(y \rightarrow p/q\) as \(x \rightarrow \infty\). By considering the derivative, \(y\) either monotonically increases or decreases, implying the last lemma.

Sequences of convergents for \(\alpha\) describe sequences of graphs whose ranges for nonnegative \(x\) are successively narrower and approach the horizontal line \(y = \alpha\). On each graph, there is a unique \(x \ge 0\) for which \(y = \alpha\).


Ben Lynn blynn@cs.stanford.edu 💡