Convergents are Best Approximations
Theorem
Let $x$ be an irrational number.
Let $(p_n)_{n\geq0}$ and $(q_n)_{n\geq0}$ be the numerators and denominators of its continued fraction expansion.
Let $\dfrac {p_n} {q_n}$ be the $n$th convergent.
Let $\dfrac a b$ be any rational number such that $0 < b < q_{n+1}$.
Then:
- $\forall n > 1: \left\vert{q_n x - p_n}\right\vert \le \left\vert{b x - a}\right\vert$
The equality holds only if $a = p_n$ and $b = q_n$.
Corollary
Each convergent $\dfrac {p_n} {q_n}$ is a best rational approximation to $x$.
That is, for any rational number $\dfrac a b$ such that $1 \le b \le q_n$:
- $\left\vert{x - \dfrac {p_n} {q_n}}\right\vert \le \left\vert{x - \dfrac a b}\right\vert$
The equality holds only if $a = p_n$ and $b = q_n$.
Proof
Let $\dfrac a b$ be a rational number in canonical form such that $b < q_{n + 1}$.
Suppose it is not true that $a = p_n$ and $b = q_n$, in which case the equality certainly holds.
Consider the system of equations:
| \(\displaystyle a\) | \(=\) | \(\displaystyle r p_n + s p_{n - 1}\) | $\quad$ | $\quad$ | |||||||||
| \(\displaystyle b\) | \(=\) | \(\displaystyle r q_n + s q_{n - 1}\) | $\quad$ | $\quad$ |
Multiplying the first by $b_n$, and the second by $a_n$, then subtracting, we get:
- $a q_n - b p_n = s \left({p_{n + 1} q_n - p_n q_{n + 1} }\right)$
After applying Difference between Adjacent Convergents of Simple Continued Fraction we get:
| \(\displaystyle s\) | \(=\) | \(\displaystyle \left({-1}\right)^{n + 1} \left({a q_n - b p_n}\right)\) | $\quad$ | $\quad$ | |||||||||
| \(\displaystyle r\) | \(=\) | \(\displaystyle \left({-1}\right)^{n + 1} \left({b p_{n + 1} - a q_{n + 1} }\right)\) | $\quad$ by a similar process | $\quad$ |
So $r$ and $s$ are integers.
Neither of them is $0$ because:
- if $r = 0$ then $a q_{n + 1} = b p_{n + 1}$, and Euclid's Lemma means $q_{n + 1} \mathrel \backslash b$ as $p_{n + 1} \perp q_{n + 1}$, which contradicts $0 < b < q_{n + 1}$
- if $s = 0$ we have $\dfrac a b = \dfrac {p_n} {q_n}$ and this we have already excluded as a special case.
the below needs to link to a stronger result
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues.
To discuss this proof in more detail, feel free to use the talk page.
If you are able to fix this page, then when you have done so you can remove this instance of {{Questionable}} from the code.
If you would welcome a second opinion as to whether your correction is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
From Even Convergent of Simple Continued Fraction is Strictly Smaller than Odd Convergent, the convergents are alternately greater than and less than $x$.
Hence since $0 < b = r q_n + s q_{n + 1} < q_{n + 1}$, the integers $r$ and $s$ must have opposite sign.
It follows that $r \left({q_n x - p_n}\right)$ and $s \left({q_{n + 1} x - p_{n + 1} }\right)$ have the same sign.
This is necessary for the Triangle Inequality to hold.
So:
| \(\displaystyle \left\vert{b x - a}\right\vert\) | \(=\) | \(\displaystyle \left\vert{\left({r q_n + s q_{n + 1} }\right) x - \left({r p_n + s p_{n+1} }\right)}\right\vert\) | $\quad$ | $\quad$ | |||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \left\vert{r \left({q_n x - p_n}\right) + s \left({q_{n + 1} x - p_{n + 1} }\right)}\right\vert\) | $\quad$ | $\quad$ | |||||||||
| \(\displaystyle \) | \(=\) | \(\displaystyle \left\vert{r}\right\vert \left\vert{q_n x - p_n}\right\vert + \left\vert{s}\right\vert \left\vert{q_{n + 1} x - p_{n + 1} }\right\vert\) | $\quad$ | $\quad$ | |||||||||
| \(\displaystyle \) | \(>\) | \(\displaystyle \left\vert{r}\right\vert \left\vert{q_n x - p_n}\right\vert\) | $\quad$ | $\quad$ | |||||||||
| \(\displaystyle \) | \(\ge\) | \(\displaystyle \left\vert{q_n x - p_n}\right\vert\) | $\quad$ | $\quad$ |
as we wanted to prove.
$\blacksquare$
