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

## Intermediate Convergents

We can say a little more about rational approximations. Let $$k$$ be 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}$$.

Suppose $$p'/q'$$ is a rational approximation to $$a$$ that is at least as close as $$p_k/q_k$$. 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}$$.

## Bounds

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 finite expansions, and one is 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.

## Mediants

The mediant (affectionately known as the freshman sum) of $$\frac{a}{b}$$ and $$\frac{c}{d}$$ is $$\frac{a+c}{b+d}$$, and lies strictly between them unless the fractions are equal. Here, the fractions need not be reduced. In fact, we may generalize the numerators and denominators beyond integers.

Above, the intermediate convergents are the mediants of $$\frac{p_k}{q_k}$$ and each of $$\frac{p_{k+1}}{q_{k+1}}, \frac{2p_{k+1}}{2q_{k+1}}, ...$$.

Suppose we have two different approximations to $$r$$ whose geometric mean is $$r$$. Then for any $$x$$ strictly between the two approximations, the interval between $$x$$ and $$r^2/x$$ is smaller.

For example, to approximate $$\sqrt{2}$$, we can start by guessing such as $$1/1$$ and $$2/1$$. Their mediant is $$3/2$$, and dividing 2 by this yields $$4/3$$, so $$3/2$$ and $$4/3$$ are a closer pair of approximations. Repeating this yields the interval between $$7/5$$ and $$10/7$$, and repeating again leads to $$17/12$$ and $$24/17$$.

We happen to produce exactly the continued fraction convergents (and their reciprocals doubled) but in general this process is less efficient than continued fractions. Roughly speaking, continued fractions are better because they scale up the numerator and denominator of the other convergent by the best possible amount before computing the mediant.

Here’s a curiosity. Suppose we want to approximate $$\sqrt{D}$$, and we begin with $$x$$ and $$D/x$$. Write $$x$$ as the fraction $$x^2/x$$, and the resulting mediant is:

$\frac{x^2 + D}{2x}$

Improving approximations via mediants has led to Newton’s method! Though really, if we wish to avoid calculus, it’s simpler to find approximations with a given convergence rate by studying polynomials rather than play with mediants.

For example, suppose we desire quintic convergence to $$\sqrt{D}$$. We find

$(x - \sqrt{D})^5 = x^5 + 10 x^3 D + 5 x D^2 - \sqrt{D} (5 x^4 + 10 x^2 D + D^2)$

Thus if $$x$$ is an approximation, then

$\frac {x^5 + 10 x^3 D + 5 x D^2} {5 x^4 + 10 x^2 D + D^2} - \sqrt{D} \le B (x - \sqrt{D})^5$

for some bound $$B$$.

Ben Lynn blynn@cs.stanford.edu 💡