3
$\begingroup$

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?

  • 1
    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.2011-11-14

1 Answers 1

2

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|$.

  • 3
    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.)2011-11-14