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$.