Continued Fractions - Basic Results

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} \geq 1$ since $a_{i + 1}$ is a positive integer. Then If $x_{i + 1} > 1$ , then $a_{i} = ⌊ x_{i} ⌋$ 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 \to p / q$ as $x \to ∞$ . By considering the derivative, $y$ either monotonically increases or decreases, implying the last lemma.

Sequences of convergents for $α$ describe sequences of graphs whose ranges for nonnegative $x$ are successively narrower and approach the horizontal line $y = α$ . Somewhere on all but the last graph, there is a unique $x \geq 0$ for which $y = α$ .