Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Possible Duplicate:
A nicer proof of Lagrange's 'best approximations' law?

I was reading through the wikipedia article on continued fractions, and they state, essentially, that for any convergent $\frac{a}{b}$, it is the best approximation you can have. More formally, for an irrational number $x$ with a convergent $\frac{a}{b}$,

$\forall c\forall d \quad |\frac{c}{d}-x| < |\frac{a}{b}-x| \implies d > b$.

However they give no proof of it. Is there a nice one, or did they not give one because it's messy to show?

share|cite|improve this question

marked as duplicate by Srivatsan, Asaf Karagila, t.b., J. M., Mike Spivey Dec 6 '11 at 5:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

@Srivatsan, it isn't quite a duplicate, since that question asks about $|a-bx|$, and this one asks about $|(a/b)-x|$. But it's certainly true that OP may find something of interest in that other thread. – Gerry Myerson Nov 14 '11 at 5:21
(Cf. my vote to close and @Gerry's comment.) Apologies to james for the hasty vote to close as duplicate. – Srivatsan Nov 14 '11 at 5:23
I don't know of a particularly short proof of this fact. The expositions I've seen in textbooks (such as chapter 7 of Niven, Zuckerman, & Montgomery's book) take a few lemmas to establish this. – Greg Martin Nov 14 '11 at 5:56

It's not true. For example, $3/1$ is a convergent of $x = \frac{15}{4} = 3 + 1/(1 + 1/3)$, but it is not a best approximation since $|4/1 - x| < |3/1 - x|$.

share|cite|improve this answer
Technically, $x$ is required by the OP to be irrational. I suppose the counter-example can be fixed easily to handle that (e.g., by picking $x$ to be sufficiently close to $15/4$)... – Srivatsan Nov 14 '11 at 6:42
The correct result is that if $|\alpha−c/d|<|\alpha−p_k/q_k|$, where $k\ge 1$, then $d>q_k$. There is no claim about $k=0$. If we change the question to what are the best approximations to $\alpha$ with denominator $\le s$, the answer changes to convergents or secondary convergents. (The definition of secondary convergent is too long for a comment.) – André Nicolas Nov 14 '11 at 7:34

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