Convergence

In some sense, the convergents are the best possible approximations for a given nonnegative real:

Theorem: Let $p/q$ be a convergent for the nonnegative real $a$. Then if $p'/q'$ is a closer rational approximation, then $q' \gt q$.

Proof: Recall successive convergents get closer to $x$ and alternatively overshoot and undershoot $x$. Also recall $p_k q_{k-1} - q_k p_{k-1} = (-1)^k$. The result follows from the next lemma.∎

Lemma: Suppose

\[ \frac{a}{b} \lt \frac{c}{d} \lt \frac{a'}{b'} \]

and $a b' - a' b = -1$. Then $d \gt b$ and $d \gt b'$.

Proof: Manipulating the inequalities gives

\[ 0 \lt \frac{c b - a d}{d b} \lt \frac{a' b - a b'}{b b'} = \frac{1}{b b'} \]

As $c b - a d \gt 0$, we find $b' \lt d$. The proof for $b$ is similar.∎

We can say more about any rational approximation to $a$. Suppose $k$ is odd. The following generalizes to even $k$ by flipping signs.

Since $p_{k+1}, q_{k+1}$ are coprime, the solutions of $p_{k+1} x - q_{k+1} y = 1$ are given by $x = q_k + t q_{k+1}, y = p_k + t p_{k+1}$ for all integers $t$. Likewise, we can construct a sequence of approximations, the intermediate convergents,

\[ \frac{p_k}{q_k} , \frac{p_k + p_{k+1}}{q_k + q_{k+1}} , \frac{p_k +2 p_{k+1}}{q_k +2 q_{k+1}} , ..., \frac{p_k +(a_{k+2} - 1) p_{k+1}}{q_k + (a_{k+2} - 1) q_{k+1}} , \frac{p_{k+2}}{q_{k+2}} \]

This sequence strictly increases, as do all the numerators and denominators, and gets closer and closer to $p_{k+1}/q_{k+1}$.

Given a rational approximation $p'/q'$ to $a$, we have three cases:

  1. $p'/q'$ is one of the intermediate convergents.

  2. $p'/q'$ lies between two of the intermediate convergents, hence by the lemma $q'$ is greater than the denominator of the intermediate convergents on either side.

  3. $p'/q'$ lies between the last intermediate convergent and $a$. By the theorem $q' \gt q_{k+2}$.

We establish handy rules of thumb for the accuracy of a convergent. Let $x_k = [a_k; a_{k+1},...]$. Recall

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

thus

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

Furthermore $x_{k+1}q_k + q_{k-1} \ge a_{k+1} q_k + q_{k-1} = q_{k+1} \ge q_k $, with equality only when $x$ is a rational terminating with $a_{k+1}$. We also have

\[ x_{k+1} q_k + q_{k-1} = (x_{k+1} -a_{k+1})q_k + q_{k+1} \lt q_k + q_{k+1} \lt 2q_{k+1} \]

In summary,

Theorem: Let $p_k/q_k$ be the convergents of a nonnegative real $a$. Then

\[ \frac{1}{2q_k q_{k+1}} \lt \frac{1}{q_k(q_k + q_{k+1})} \le \left| x - \frac{p_k}{q_k} \right| \le \frac{1}{q_k q_{k+1}} \lt \frac{1}{q_k^2} \]

Now for a sort of converse:

Theorem: If $\left| \frac{r}{s} - a \right| \lt \frac{1}{2s^2}$ where $r,s$ are coprime then $\frac{r}{s}$ is a convergent of $a$.

Proof: Let the expansion of $r/s$ be $[a_1; a_2,...,a_k]$ where $k$ is odd. (Recall a rational has two possible expansions, one exactly one term longer than the other.) Define $x_{k+1}$ by the real that satisfies $a = [a_1;a_2,...,a_k, x_{k+1}]$.

We will show $x_{k+1} \ge 1$, because this implies we could expand $x_{k+1}$ into a continued fraction with a nonzero first term and obtain a continued fraction expansion for $a$, proving the theorem.

Rewriting

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

gives

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

As $k$ is odd, we have $x - \frac{p_k}{q_k} = \epsilon$ for some $0 \lt \epsilon \lt \frac{1}{2q_k^2}$, thus

\[ x_{k+1} = \frac{1 - \epsilon q_k q_{k-1}}{\epsilon q_k^2} \]

We need only show $1 - \epsilon q_k q_{k-1} \ge \epsilon q_k^2$:

\[ \epsilon(q_k^2 + q_k q_{k-1}) \lt \frac{q_k^2 + q_k q_{k-1}}{2q^2} \lt \frac{q_k^2 + q_k^2}{2q_k^2} ∎ \]

At last we plug a hole in our proof that rationals have exactly two finite continued fraction expansions. Suppose the rational $p/q$ has an infinite continued fraction expansion. This would imply

\[ 1 = | p q_n - q p_n | = q q_n \left|\frac{p}{q} - \frac{p_n}{q_n}\right| \lt \frac{q q_n}{q_n^2} \rightarrow 0 \]

as $n \rightarrow \infty$, a contradiction.