Criterion for a/b to be a Convergent of an Infinite Continued Fraction

Criterion for a/b to be a Convergent of an Infinite Continued Fraction

Theorem 1: Let $\epsilon \in \mathbb{R} \setminus \mathbb{Q}$. If there exists $\frac{a}{b} \in \mathbb{Q}$ with $(a, b) = 1$ such that $\displaystyle{\left | \epsilon - \frac{a}{b} \right | < \frac{1}{2b^2}}$ then for some $n \in \mathbb{N}$, $\frac{a}{b} = r_n$.

Theorem 1 asserts that if a rational number $\frac{a}{b}$ in lowest terms is "too close" to an irrational number $\epsilon$ then $\frac{a}{b}$ must equal one of the convergents of that irrational number.

  • Proof: Suppose otherwise, i.e., suppose that $\frac{a}{b} \in \mathbb{Q}$ with $(a, b) = 1$ is such that $\left | \epsilon - \frac{a}{b} \right | < \frac{1}{2b^2}$ and $\frac{a}{b} \neq r_n$ for all $n \in \mathbb{N}$. For each $n \in \mathbb{N}$ we have that if $b < k_{n+1}$ then:
(1)
\begin{align} \quad \left | \epsilon - \frac{a}{b} \right | \geq \left | \epsilon - \frac{h_n}{k_n} \right | \end{align}
  • Since $b \neq k_n$ for any $n \in \mathbb{N}$ let $j$ be the index for which $k_j < b < k_{j+1}$. This $j$ can be found since $(k_n)$ increases to infinity and $b$ is fixed. Then:
(2)
\begin{align} \quad \frac{1}{2b^2} > \left | \epsilon - \frac{a}{b} \right | \geq \left | \epsilon - \frac{h_j}{k_j} \right | \end{align}
  • Hence:
(3)
\begin{align} \quad \left | \epsilon - \frac{h_j}{k_j} \right | < \frac{1}{2b^2} \end{align}
  • But also, since $\frac{h_j}{k_j} \neq \frac{a}{b}$ we have that
(4)
\begin{align} \quad \left | \frac{h_j}{k_j} - \frac{a}{b} \right | = \frac{|h_jb - ak_j|}{bk_j} \geq \frac{1}{bk_j} \quad (*) \end{align}
  • But also by the triangle inequality we have that:
(5)
\begin{align} \left | \frac{h_j}{k_j} - \frac{a}{b} \right | &= \left | \frac{h_j}{k_j} - \epsilon + \epsilon - \frac{a}{b} \right | \\ & \leq \left | \frac{h_j}{k_j} - \epsilon \right | + \left | \epsilon - \frac{a}{b} \right | \\ & < \frac{1}{2b^2} + \frac{1}{2b^2} \\ & < \frac{1}{b^2} \quad (**) \end{align}
  • Using the inequalities at $(*)$ and $(**)$ we see that:
(6)
\begin{align} \quad \frac{1}{bk_j} < \frac{1}{b^2} \end{align}
  • So $bk_j > b^2$ which implies that $k_j > b$ which contradicts $k_j < b < k_{j+1}$. Hence the assumption that $\frac{a}{b} \neq r_n$ for all $n \in \mathbb{N}$ is false. So $\frac{a}{b} = r_n$ for some $n$. $\blacksquare$
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License