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

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\).∎

Exercise: Actually, there’s a hole in the proof! What is it?

Solution: What if an infinite continued fraction approaches a rational? Such a rational would have at least three expansions. We rule out this possibility after we derive some bounds.

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

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

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\).