Continued Fractions

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\prime /q\prime$ is a closer rational approximation, then $q\prime >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. $\blacksquare$

Lemma: Suppose

$$\frac{a}{b}<\frac{c}{d}<\frac{a\prime }{b\prime }$$

and $ab\prime -a\prime b=-1$. Then $d>b$ and $d>b\prime$.

Proof: Manipulating the inequalities gives

$$0<\frac{cb-ad}{db}<\frac{a\prime b-ab\prime }{bb\prime }=\frac{1}{bb\prime }$$

As $cb-ad>0$, we find $b\prime <d$. The proof for $b$ is similar. $\blacksquare$

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+2p_{k+1}}{q_k+2q_{k+1}},...,\frac{p_k+(q_{k+2}-1)p_{k+1}}{q_k+(q_{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\prime /q\prime$ to $a$, we have three cases:

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

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

3. $p\prime /q\prime$ lies between the last intermediate convergent and $a$. By the theorem $q\prime >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}<q_k+q_{k+1}<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}}<\frac{1}{q_k(q_k+q_{k+1})}\le \mid x-\frac{p_k}{q_k}\mid \le \frac{1}{q_k{q}_{k+1}}<\frac{1}{q_k^2}$$

Now for a sort of converse:

Theorem: If $\mid \frac{r}{s}-a\mid <\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<\epsilon <\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})<\frac{q_k^2+q_k{q}_{k-1}}{2q^2}<\frac{q_k^2+q_k^2}{2q_k^2} \blacksquare$$

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=\mid p{q}_n-q{p}_n\mid =q{q}_n\mid \frac{p}{q}-\frac{p_n}{q_n}\mid <\frac{q{q}_n}{q_n^2}\to 0$$

as $n\to \mathrm{\infty }$, a contradiction.