About continued fractions as best rational approximations

Question

I'm reading this notes about continued fractions:

http://www.math.jacobs-university.de/timorin/PM/continued_fractions.pdf

I had no problems understanding everything there, except one thing that has me stuck.

At page 9, the author proves that the "convergents" are the best rational approximations. In that proof, he says that $|x-\frac{h_n}{k_n}|<\frac{1}{2k_n^2}$ (*).

Previously, he has shown that $|x-\frac{h_n}{k_n}|<\frac{1}{k_{n+1}k_n}$. And as $k_{n+1}>k_n$ (increasing denominators), I see that you can get $|x-\frac{h_n}{k_n}|<\frac{1}{k_n^2}$. But I really don't understand where that 2 in (*) (which is vital for the proof) comes from. The author seems to justify that step saying that denominators increase and $k_{n+1}\geq 2$...

Anybody can help me with this? Thanks a lot in advance.

Answer 1

Well, it's wrong. We have the equality

$$\left\lvert x - \frac{h_n}{k_n}\right\rvert = \frac{1}{k_n(\alpha_{n+1}k_n + k_{n-1})},$$

where $\alpha_{n+1} = [a_{n+1},\, a_{n+2},\, \dotsc\,]$ is the $n+1^{\text{st}}$ complete quotient, and the $a_k$ are the partial quotients. We know that $a_{n+1} < \alpha_{n+1} < a_{n+1}+1$ (unless the continued fraction ends at $a_{n+1}$, in which case we have equality on the left, or it ends at $a_{n+2}$ and that is $1$, then we have equality on the right).

So we only have

$$\left\lvert x - \frac{h_n}{k_n}\right\rvert < \frac{1}{2k_n^2}$$

if $\alpha_{n+1} + \frac{k_{n-1}}{k_n} > 2$. If $a_{n+1} \geqslant 2$, that is satisfied, also if $a_{n+1} = 1$ and $k_{n-1}$ is close enough to $k_n$, but not in general.

As an example, consider $x = \frac{137}{127} = [1,\, 12,\,1,\,2,\,3]$ and its convergent $\frac{13}{12} = [1,\,12]$. We have

$$\frac{13}{12} - \frac{137}{127} = \frac{7}{12\cdot 127} > \frac{1}{2\cdot 12^2}.$$

The result, that the convergents (except possibly the $0^{\text{th}}$) are best approximations, is true, but the given proof is invalid.

It is not hard to fix, though. We suppose $n \geqslant 1$, since as we said, the $0^{\text{th}}$ convergent need not be a best approximation. There are two possibilities,

• $\frac{p}{q}$ and $\frac{h_n}{k_n}$ lie on the same side of $x$, then $$\frac{1}{k_n^2} > \left\lvert x - \frac{h_n}{k_n}\right\rvert \geqslant \left\lvert \frac{p}{q} - \frac{h_n}{k_n}\right\rvert = \frac{\lvert pk_n-qh_n\rvert}{qk_n} \geqslant \frac{1}{qk_n} \Rightarrow q > k_n,$$
• or they lie on different sides of $x$, then $$\frac{1}{k_nk_{n-1}} = \left\lvert\frac{h_{n-1}}{k_{n-1}} - \frac{h_n}{k_n}\right\rvert = \left\lvert\frac{h_{n-1}}{k_{n-1}} - \frac{p}{q} \right\rvert + \left\lvert \frac{p}{q} - \frac{h_n}{k_n}\right\rvert \geqslant \frac{1}{qk_{n-1}} + \frac{1}{qk_n} = \frac{k_n+k_{n+1}}{qk_nk_{n-1}},$$ whence $q \geqslant k_n + k_{n-1} > k_n$. (We used that $\left\lvert x -\frac{h_n}{k_n}\right\rvert < \left\lvert x - \frac{h_{n-1}}{k_{n-1}}\right\rvert$.)