Accuracy of Convergents of Continued Fraction

Theorem

Let $x$ be an irrational number.

Let $\left \langle {C_n}\right \rangle$ be the sequence of convergents of $x$.

Let $p_1, p_2, p_3, \ldots$ and $q_1, q_2, q_3, \ldots$ be its numerators and denominators.

Then:

$\displaystyle \forall k \ge 1: \left\vert{x - \frac {p_{k+1}} {q_{k+1}}}\right\vert \le \frac 1 {q_{k+1} q_{k+2}} \le \frac 1 {2 q_k q_{k+1}} < \left\vert{x - \frac {p_k} {q_k}}\right\vert$.

Corollary

$\displaystyle \forall k \ge 1: \frac 1 {q_k q_{k+1}} > \left\vert{x - \frac {p_k} {q_k}}\right\vert > \frac 1 {2 q_k q_{k+1}}$

Proof

Let $x$ have an SICF of $\left[{a_1, a_2, a_3, \ldots}\right]$.

The Continued Fraction Algorithm gives the following system of eqns:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x\)	\(=\)	\(\displaystyle \left[{a_1, x_2}\right]\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left[{a_1, a_2, x_3}\right]\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \ldots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left[{a_1, a_2, \ldots, a_n, x_{n+1} }\right]\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \ldots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

and

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left\vert{x - \frac {p_n} {q_n} }\right\vert\)	\(=\)	\(\displaystyle \left\vert{\left[{a_1, a_2, \ldots, a_n, x_{n+1} }\right] - \frac {p_n} {q_n} }\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left\vert{\frac {x_{n+1} p_n + p_{n-1} } {x_{n+1} q_n + q_{n-1} } - \frac {p_n} {q_n} }\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Value of Simple Continued Fraction
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left\vert{\frac {p_{n-1} q_n - p_n q_{n-1} } {q_n \left({x_{n+1} q_n + q_{n-1} }\right)} }\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac 1 {q_n \left({x_{n+1} q_n + q_{n-1} }\right)}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Properties of Convergents of Continued Fractions

Now $x_{n+1} = \left[{a_{n+1}, a_{n+2}, a_{n+3}, \ldots}\right]$ from the Continued Fraction Algorithm.

So $a_{n+1} < x_{n+1} < a_{n+1} + 1$.

Therefore:

$\displaystyle \left\vert{x - \frac {p_n} {q_n}}\right\vert < \frac 1 {q_n \left({a_{n+1} q_n + q_{n-1}}\right)} = \frac 1 {q_n q_{n+1}}$.

This gives the LHS of the inequality when $n = k+1$.

We also have:

$\displaystyle \left\vert{x - \frac {p_n} {q_n}}\right\vert > \frac 1 {q_n \left({\left({a_{n+1} + 1}\right) q_n + q_{n-1}}\right)}$

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left\vert{x - \frac {p_n} {q_n} }\right\vert\)	\(>\)	\(\displaystyle \frac 1 {q_n \left({\left({a_{n+1} + 1}\right) q_n + q_{n-1} }\right)}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac 1 {q_n \left({a_{n+1} q_n + q_{n-1} }\right) + q_n^2}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac 1 {q_n \left({q_{n+1} + q_n}\right)}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(>\)	\(\displaystyle \frac 1 {q_n \left({q_{n+1} + q_{n+1} }\right)}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac 1 {2 q_n q_{n+1} }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

This gives the RHS of the inequality when $n = k$.

For the middle inequality, note that:

$q_{k+2} = a_{k+2} q_{k+1} + q_k > q_k + q_k = 2 q_k$

So:

$\displaystyle \frac 1 {q_{k+1} q_{k+2}} \le \frac 1 {2 q_k q_{k+1}}$

Proof of Corollary

Immediate.

Comment

The left hand side of the inequality gives an indication of how close each convergent gets to its true value.

The right hand side gives a bound that limits its accuracy.