Irrational Number Approximation by Infinite Continued Fractions

Consider the infinite continued fraction $\langle 1; 2, 2, 2, 2, ... \rangle$. We already know that this infinite continued fraction represents an irrational number $x$ and that:

(1)

\begin{align} \quad x = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + ...}}} = 1 + \frac{1}{1 + 1 + \frac{1}{2 + \frac{1}{2+ \frac{1}{2 + ...}}}} = 1 + \frac{1}{1 + x} \end{align}

Therefore $x(1 + x) = (1 + x) + 1$. So $x^2 + x = 1 + x + 1$ and $x^2 = 2$. Since $x > 0$ we must have that $x = \sqrt{2}$. Therefore, the limit of the $n^{\mathrm{th}}$ convergents is $x$, i.e., $\lim_{n \to \infty} r_n = 0$. Let's compute some $\displaystyle{r_n = \frac{h_n}{k_n}}$. We first compute $h_n$ and $k_n$ with the recursive formulas:

(2)

\begin{align} \quad h_{-2} = 1, \quad h_{-1} = 0, \quad h_n = a_nh_{n-1} + h_{n-2} \\ \quad k_{-2} = 0, \quad k_{-1} = 1, \quad k_n = a_nk_{n-1} + k_{n-2} \end{align}

Some of the first few $h_n$ and $k_n$ are calculated in the table below:

$n$	$a_n$	$h_n$	$k_n$	$r_n$
$-2$	-	$0$	$1$	-
$-1$	-	$1$	$0$	-
$0$	$1$	$1$	$1$	$1$
$1$	$2$	$3$	$2$	$\frac{3}{2}$
$2$	$2$	$7$	$5$	$\frac{7}{5}$
$3$	$2$	$17$	$12$	$\frac{17}{12}$
$4$	$2$	$41$	$29$	$\frac{41}{29}$
$5$	$2$	$99$	$70$	$\frac{99}{70}$

Objectively, $r_5$ is a rather good approximation of $\sqrt{2}$. However, is $r_5$ a better approximation that $r_6$ for example? The following propositions help answer this question.

Theorem 1: Let $\epsilon$ be an irrational number and let $\displaystyle{r_n = \frac{h_n}{k_n}}$ be the $n^{\mathrm{th}}$ convergent of its infinite continued fraction. Then $\displaystyle{\left | \epsilon - \frac{h_n}{k_n} \right | < \frac{1}{k_nk_{n+1}}}$ for each $n \in \mathbb{N}$.

• Proof: Let $\epsilon = \langle a_0; a_1, a_2, ... \rangle$. Then for some irrational $\epsilon_{n+1}$ we have that $\epsilon = \langle a_0; a_1, a_2, ..., a_n, \epsilon_{n+1} \rangle$. So:

(3)

\begin{align} \quad \left | \epsilon - \frac{h_n}{k_n} \right | &= \left | \frac{\epsilon_{n+1}h_n + h_{n-1}}{\epsilon_{n+1}k_n + k_{n-1}} - \frac{h_n}{k_n} \right | \\ &= \left | \frac{(\epsilon_{n+1}h_n + h_{n-1})k_n - (\epsilon_{n+1}k_n + k_{n-1})h_n}{(\epsilon_{n+1}k_n + k_{n-1})k_n}\right | \\ &= \left | \frac{h_{n-1}k_n - h_{n}k_{n-1}}{(\epsilon_{n+1}k_n + k_{n-1})k_n}\right | \\ &= \left | \frac{(-1)^n}{(\epsilon_{n+1}k_n + k_{n-1})k_n} \right | \\ &= \frac{1}{(\epsilon_{n+1}k_n + k_{n-1})k_n} \end{align}

• Now observe that since $\epsilon_{n+1} = \langle a_{n+1}; a_{n+2}, ... \rangle > a_{n+1} \geq 1$ and since $a_{n+1}k_n + k_{n-1} = k_{n+1}$, we have that:

(4)

\begin{align} \quad (\epsilon_{n+1}k_n + k_{n-1})k_n > (a_{n+1}k_n + k_{n-1})k_n = k_{n+1}k_n \end{align}

• Hence:

(5)

\begin{align} \quad \left | \epsilon - \frac{h_n}{k_n} \right | < \frac{1}{k_nk_{n+1}} \quad \blacksquare \end{align}

Corollary 2: Let $\epsilon$ be an irrational number and let $\displaystyle{r_n = \frac{h_n}{k_n}}$ be the $n^{\mathrm{th}}$ convergent of its infinite continued fraction. Then $|k_{n+1}\epsilon - h_{n+1}| < |k_n\epsilon - h_n|$ for each $n \in \mathbb{N}$.

• Proof: From proposition 1 we have that for each $n \in \mathbb{N}$:

(6)

\begin{align} \quad \left | \epsilon - \frac{h_n}{k_n} \right | = \frac{1}{(\epsilon_{n+1}k_n + k_{n-1})k_n} < \frac{1}{k_nk_{n+1}} \end{align}

• Observe that $\epsilon_{n+1} < a_{n+1} + 1$. Therefore:

(7)

\begin{align} \quad \epsilon_{n+1}k_n + k_{n-1} < (a_{n+1} + 1)k_n + k_{n-1} = a_{n+1}k_n + k_n + k_{n-1} = (a_{n+1}k_n + k_{n-1}) + k_n = k_{n+1} + k_n \overset{(*)} \leq k_{n+2} \end{align}

• Where the inequality at $(*)$ comes from the fact that $k_{n+2} = a_{n+2}k_{n+1} + k_n \geq k_{n+1} + k_n$ since $a_{n+2} \geq 1$. Hence:

(8)

\begin{align} \quad \frac{1}{k_nk_{n+2}} < \left | \epsilon - \frac{h_n}{k_n} \right | < \frac{1}{k_nk_{n+1}} \end{align}

• Multiplying both sides by $k_n > 0$ gives us that for each $n$:

(9)

\begin{align} \quad \frac{1}{k_{n+2}} < |k_n \epsilon - h_n| < \frac{1}{k_{n+1}} \quad (**) \end{align}

• And since this is true for each $n$ we also have that:

(10)

\begin{align} \quad \frac{1}{k_{n+3}} < |k_{n+1} \epsilon - h_{n+1}| < \frac{1}{k_{n+2}} \quad (***) \end{align}

• Combining the first inequality of $(**)$ with the second inequality of $(***)$ gives us that for each $n$:

(11)

\begin{align} \quad |k_{n+1}\epsilon + h_{n+1}| < \frac{1}{k_{n+2}} < |k_n\epsilon + h_n| \Leftrightarrow |k_{n+1}\epsilon + h_{n+1}| < |k_n\epsilon + h_n| \quad \blacksquare \end{align}

Corollary 3: Let $\epsilon$ be an irrational number and let $\displaystyle{r_n = \frac{h_n}{k_n}}$ be the $n^{\mathrm{th}}$ convergent of its infinite continued fraction. Then $\displaystyle{\left | \epsilon - \frac{h_{n+1}}{k_{n+1}} \right | < \left | \epsilon - \frac{h_n}{k_n} \right |}$ for each $n \in \mathbb{N}$.

Corollary 4 tells us that the approximations $r_n$ of $\epsilon$ are guaranteed to be better and better as $n$ gets larger and larger.

• Proof: By corollary 2 we have that for each $n \in \mathbb{N}$, $|k_{n+1}\epsilon + h_{n+1}| < |k_n\epsilon + h_n|$. Divide both sides of this inequality by $k_{n+1}$ to get:

(12)

\begin{align} \quad \left | \epsilon - \frac{h_{n+1}}{k_{n+1}} \right | < \frac{1}{k_{n+1}} |k_n \epsilon - h_n| \end{align}

• Since $k_n \leq k_{n+1}$ we have that $\frac{1}{k_{n+1}} \leq \frac{1}{k_n}$ and so:

(13)

\begin{align} \quad \left | \epsilon - \frac{h_{n+1}}{k_{n+1}} \right | < \frac{1}{k_n} |k_n \epsilon + h_n| = \left |\epsilon - \frac{h_n}{k_n} \right | \quad \blacksquare \end{align}

Corollary 4: If $\epsilon$ is irrational then there exists infinitely many $\frac{a}{b} \in \mathbb{Q}$ for which $\displaystyle{\left | \epsilon - \frac{a}{b} \right | < \frac{1}{b^2}}$.

We have already proved Corollary 4 in a different context on the Irrational Number Approximation by Rational Numbers page.

• Proof: By proposition 1 we have that for each $n \in \mathbb{N}$:

(14)

\begin{align} \quad \left | \epsilon - \frac{h_n}{k_n} \right | < \frac{1}{k_nk_{n+1}} < \frac{1}{k_n^2} \end{align}

• Each $\frac{h_n}{k_n} \in \mathbb{Q}$ is a distinct by corollary 3 and so there are infinitely many satisfying the condition of corollary 4. $\blacksquare$

Proposition 5: Let $\epsilon \in \mathbb{R}$. Then: a) For all $n \geq 0$ and $b < k_{n+1}$ we have that $| k_n \epsilon - h_n | \leq |b \epsilon - a|$ for all $a \in \mathbb{Z}$. b) For all $n \geq 1$ and $b < k_{n}$ we have that $\displaystyle{\left | \epsilon - \frac{h_n}{k_n} \right | \leq \left | \epsilon - \frac{a}{b} \right |}$ for all $a \in \mathbb{Z}$.

Proposition 5 above tells us that the $n^{\mathrm{th}}$ convergents of $\epsilon$ are the best such rational approximations of $\epsilon$ in the sense then if $\frac{a}{b}$ is claimed to approximate $\epsilon$ and $b$ is less than or equal to the denominator $k_n$ or $r_n = \frac{h_n}{k_n}$ then $\frac{a}{b}$ is further away from $\epsilon$ than $r_n$ is.

• Proof of (a): Suppose instead that there exists an $\frac{a}{b} \in \mathbb{Q}$ with $b < k_{n+1}$ and $b \neq k_n$ for which $|k_m \epsilon - h_n| > |b \epsilon - a|$. Consider the following system of linear equations:

(15)

\begin{align} \quad k_nx + k_{n+1}y &= b \\ \quad h_nx + h_{n+1}y &= a \end{align}

• The coefficient matrix for this system has determinant $k_nh_{n+1} - k_{n+1}h_n = \pm 1$. Since the determinant of the coefficient matrix is nonzero, there is a unique solution. Furthermore, by Cramer's Rule, the unique solution $(x, y)$ is an integer solution.

• Now we will show that $xy < 0$.

• First suppose that $x = 0$. Then the first equation becomes $k_{n+1}y = b$. So $y = \frac{b}{k_{n+1}}$. But since $b < k_{n+1}$ this implies that $0 < y < 1$ which contradicts $y \in \mathbb{Z}$.

• Now suppose that $y = 0$. Then the system above becomes:

(16)

\begin{align} \quad k_nx &= b \\ \quad h_nx &= a \end{align}

• The second equation implies that $x = \frac{a}{h_n}$. Plugging this into the first equation gives us $k_n \frac{a}{h_n} = b$, and so $\frac{h_n}{k_n} = \frac{a}{b}$. This is also a contradiction since $k_n \neq b$.

• So we have established that $x \neq 0$ and $y \neq 0$. Suppose that $y > 0$. We have that $k_nx = b - k_{n+1}y \leq b - k_{n+1} < 0$. So $k_nx < 0$. But since $k_n > 0$ this means that $x < 0$. Now suppose that $y < 0$. Then $k_nx = b - k_{n+1}y > 0$. So $k_nx > 0$. Since $k_n > 0$ this means that $x > 0$.

• Hence $x$ and $y$ have opposite signs and so $xy < 0$. Now observe that $x(\epsilon k_n - h_n)$ and $y(\epsilon k_{n+1} - h_{n+1})$ must therefore have the same sign. Using this fact we get that::

(17)

\begin{align} \quad | \epsilon b - a | &= |\epsilon(xk_n + yk_{n+1}) - (xh_n + yh_{n+1})| \\ &= |x(\epsilon k_n - h_n) + y(\epsilon k_{n+1} - h_{n+1})| \\ &= |x||(\epsilon k_n - h_n)| + |y||(\epsilon k_{n+1} - h_{n+1})| \\ & > |(\epsilon k_n - h_n) | \end{align}

• Which is a contradiction. $\blacksquare$