# 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)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:

- 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:

- Hence:

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}$:

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

- 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:

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

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

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

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:

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

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}$:

- 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:

- 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:

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