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

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,

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