I'm reading this notes about continued fractions:


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.

  • 2
    $\begingroup$ The converse is, however, true: if $|x-(p/q)|\lt1/(2q^2)$, then $p/q$ is a convergent. Also, there's a theorem that says that of any two consecutive convergents there is at least one that satisfies the inequality (I think --- I'm doing this from memory). Get yourself a reliable book, like Hardy & Wright, or Niven, Zuckerman and Montgomery. It may cost more than a webpage, but it's worth it. $\endgroup$ – Gerry Myerson Oct 6 '13 at 11:26
  • 2
    $\begingroup$ Memory served right, @GerryMyerson, and of any three successive convergents, at least one satisfies $\lvert x - p/q\rvert < \frac{1}{q^2\sqrt{5}}$. And $\sqrt{5}$ is the best possible constant (meaning, for any larger, there are $x$ such that the inequality holds for only finitely many convergents). $\endgroup$ – Daniel Fischer Oct 6 '13 at 11:32

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$.)
  • $\begingroup$ Thanks a lot for your answer.I also suspected that proof was wrong. You saved me :) However, i don't see one thing in your fix of the proof: In the second case (second equality), you seem to use the triangle inequality as an equality. How can you justify it? $\endgroup$ – Mark_Hoffman Oct 6 '13 at 11:34
  • $\begingroup$ Since $\frac{h_{n-1}}{k_{n-1}}$ is farther away form $x$ than $\frac{h_n}{k_n}$, and by assumption $\frac{p}{q}$ is closer to $x$, we must have that $\frac{p}{q}$ lies between $\frac{h_{n-1}}{k_{n-1}}$ and $x$, and a fortiori between $\frac{h_{n-1}}{k_{n-1}}$ and $\frac{h_{n}}{k_{n}}$. Hmm, actually, the second part works also if $\frac{p}{q}$ lies on the same side of $x$ as $\frac{h_{n}}{k_{n}}$, so the first is unnecessary. $\endgroup$ – Daniel Fischer Oct 6 '13 at 11:37
  • $\begingroup$ Everything clear now. Thank you very much for your help, Daniel! $\endgroup$ – Mark_Hoffman Oct 6 '13 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.