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.


Ben Lynn blynn@cs.stanford.edu 💡