Irrational Number Approximation by Infinite Continued Fractions

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)

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)
• 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::
• Which is a contradiction. $\blacksquare$