# A nicer proof of Lagrange's 'best approximations' law?

Let $p_N/q_N$ be the $N^\text{th}$ convergent of the continued fraction for some irrational number $\alpha$. It turns out that for any other approximation $p/q$ (with $q \le q_N$) which isn't a convergent $|\alpha q - p| > |\alpha q_{N-1} - p_{N-1}|$. I'm wondering if there are any nice proofs for this result?

In my book this is proved by picking $x,y$ that solves

$$\begin{pmatrix} p_N & p_{N-1} \\ q_N & q_{N-1} \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} p \\ q \end{pmatrix}$$

since $x$ and $y$ have opposite sign, as well as $\alpha q_N - p_N$ and $\alpha q_{N-1} - p_{N-1}$ have opposite sign we can conclude that $|\alpha q - p| = |x (\alpha q_N - p_N) + y (\alpha q_{N-1} - p_{N-1})| = |x| |\alpha q_N - p_N| + |y| |\alpha q_{N-1} - p_{N-1}|$ which proves the theorem.

I am looking for different proofs than this one.

-
This looks like an excellent self-contained proof. What's not nice about it? :-) (What book is this, BTW?) (I just looked up how this is proved in Khinchin's book… while his theorem is more general—α need not be irrational, and p/q is allowed to be a convergent as well—the proof relies on a couple of previous theorems, and I wouldn't call it "nicer". I can quote it if you like.) – ShreevatsaR Aug 13 '10 at 4:49
This is from the book Exploring the Number Jungle by Edward Burger (It's a really good book!). I just got the idea that this result has probably been proven in all kinds of different ways and I hope to see some of the best. – anon Aug 13 '10 at 5:16

Of course there is a nicer proof! In fact, it's almost obvious if one thinks about geometric interpretation of continued fraction: consider the line $y=\alpha x$; then the best approximation (i.e. approximation that minimizes $|\alpha q-p|=q|\alpha-\frac{p}{q}|$) is the point of integer lattice nearest to this line; finally observe that convergents with even/odd numbers of the continued fraction give coordinates of [verices of] the convex hull of [points of] lattice lying over/under the line.

One can also (as J. M. suggests) take a look at Lorentzen, Waadeland. Continued Fractions with Applications, I.2.1 (esp. figure 1 and the text near it; there are no words "convex hull" there but implicitly everything is explained, more or less).

Upd. One more reference is Davenport's "The Higher Arithmetics" (section IV.12).

Finally, an illustration (from Arnold's book).

• Bold line $y=\alpha x$ (on the picture $\alpha=\frac{10}7$) is approximated by vectors $e_i$ corresponding to convergents (namely, $e_i$ ends at $(p_i,q_i)$);
• each vector (starting from $e_3$) is a linear combination of two preciding ones: $e_{i+2}=e_i+a_{i-1}e_{i+1}$, where $a$ is the maximal integer s.t. the new vector still doesn't intersect the line;
• this is exactly the algorithm for representing $\alpha$ by a continued fraction: $\alpha=[a_0,a_1,\dots]$.

-
This is also in Lorentzen and Waadeland's "Continued Fractions with Applications" ; a nice book, if you can get to read it. – J. M. Aug 13 '10 at 6:37
I like the sound of this but I haven't been able to understand it yet – anon Aug 13 '10 at 17:53
To expand on my comment: there is a nice illustration of "best approximation" on an integer lattice on p. 12, and a short proof of Lagrange's on p. 408. – J. M. Aug 15 '10 at 2:25
More or less, that's actually why I remembered the book in the first place... (though my interests in the book are in different chapters) :) But the lattice picture is convincing enough I suppose. – J. M. Aug 15 '10 at 12:28
Thanks for the picture; it really clarifies many things about continued fractions. I wonder why not every book contains it! – ShreevatsaR Aug 17 '10 at 22:37