The nth Convergent of an Infinite Continued Fraction

# The nth Convergent of an Infinite Continued Fraction

Recall from The Sequences (hn) and (kn) page that if $\langle a_0; a_1, a_2, ... \rangle$ is a simple continued fraction (finite or infinite) and if $a_0 \in \mathbb{Z}$, $a_n \in \mathbb{N}$ for all $n \geq 1$ then the corresponding sequences $(h_n)_{n \geq -2}$ and $(k_n)_{n \geq -2}$ are defined recursively as:

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

We proved an important theorem which says that if $\langle a_0; a_1, ..., a_{n-1}, x \rangle$ is a continued fraction where $a_0 \in \mathbb{Z}$, $a_m \in \mathbb{N}$ for all $1 \leq m \leq n-1$, and $x > 0$ then:

(2)
\begin{align} \quad \langle a_0; a_1, ..., a_{n-1}, x \rangle = \frac{xh_{n-1} + h_{n-2}}{xk_{n-1} + k_{n-2}} \end{align}
 Definition: Let $\langle a_0; a_1, a_2, ... \rangle$ be a infinite simple continued fraction where $a_0 \in \mathbb{Z}$ and $a_n \in \mathbb{N}$ for $n \geq 1$. The $n^{\mathrm{th}}$ Convergent of this fraction is defined to be finite simple continued fraction $r_n = \langle a_0; a_1, a_2, ..., a_n \rangle$.

The following proposition gives us a nice formula for the $n^{\mathrm{th}}$ convergent using the corresponding sequences $(h_n)$ and $(k_n)$.

 Proposition 1: Let $\langle a_0; a_1, a_2, ... \rangle$ be an infinite simple continued fraction with $a_0 \in \mathbb{Z}$ and $a_n \in \mathbb{N}$ for $n \geq 1$. Let $(h_n)_{n \geq -2}$ and $(k_n)_{n \geq -2}$ be the corresponding sequences as defined above. Then $\displaystyle{r_n = \frac{h_n}{k_n}}$.
• Proof: By the theorem referenced above, set $x = a_n$. Then:
(3)
\begin{align} \quad r_n = \langle a_0; a_1, a_2, ..., a_{n-1}, a_n \rangle = \frac{a_nh_{n-1} + h_{n-2}}{a_nk_{n-1} + k_{n-2}} = \frac{h_n}{k_n} \quad \blacksquare \end{align}
 Definition: Let $\langle a_0; a_1, a_2, ... \rangle$ be an infinite simple continued fraction where $a_0 \in \mathbb{Z}$ and $a_n \in \mathbb{N}$ for $n \geq 1$. Then this infinite continued fraction is said to Converge provided that the sequence $(r_n)$ of $n^{\mathrm{th}}$ converges converges, i.e., $\displaystyle{\lim_{n \to \infty} r_n}$ exists. The value of this infinite continued fraction is said to equal the limit.

The following few lemmas give us some important identities regarding the sequences $(h_n)$, $(k_n)$, and $(r_n)$.

 Lemma 2: Let $\langle a_0; a_1, a_2, ... \rangle$ be an infinite simple continued fraction with $a_0 \in \mathbb{Z}$ and $a_n \in \mathbb{N}$ for $n \geq 1$. Then: a) $\displaystyle{h_jk_{j-1} - h_{j-1}k_j = (-1)^{j-1}}$ for each $j \geq -1$. b) $\displaystyle{r_j - r_{j-1} = \frac{(-1)^{j-1}}{k_jk_{k-1}}}$ for each $j \geq -1$.
• Proof of a) When $j = -1$ we have that:
(4)
\begin{align} \quad h_{-1}k_{-2} - h_{-2}k_{-1} = (1)(1) - (0)(0) = 1 = (-1)^{-1 -1} \end{align}
• Suppose that for $j \geq -1$ we have that $h_{j}k_{j-1} - h_{j-1}k_{j} = (-1)^{j-1}$. Then:
(5)
\begin{align} \quad h_{j+1}k_j - h_jk_{j+1} &= [a_{j+1}h_j + h_{j-1}]k_j - h_j[a_{j+1}k_j + k_{j-1}] \\ &= a_{j+1}h_jk_j + h_{j-1}k_j - a_{j+1}h_jk_j - h_jk_{j-1} \\ &= h_{j-1}k_j - h_jk_{j-1} \\ &= -[h_jk_{j-1} - h_{j-1}k_j] \\ & \overset{I.H.} = -(-1)^{j-1} \\ &= (-1)^{(j+1) - 1} \end{align}
• So (a) is true by the principle of mathematical induction. $\blacksquare$
• Proof of b) We have by (a) that for each $j \geq -1$:
(6)
\begin{align} \quad r_j - r_{j-1} = \frac{h_j}{k_j} - \frac{h_{j-1}}{k_{j-1}} = \frac{h_jk_{j-1} - h_{j-1}k_j}{k_jk_{j-1}} = \frac{(-1)^{j-1}}{k_jk_{j-1}} \quad \blacksquare \end{align}
 Lemma 3: Let $\langle a_0; a_1, a_2, ... \rangle$ be an infinite simple continued fraction with $a_0 \in \mathbb{Z}$ and $a_n \in \mathbb{N}$ for $n \geq 1$. Then: a) $\displaystyle{h_jk_{j-2} - h_{j-2}k_j = (-1)^j a_j}$ for each $j \geq 0$. b) $\displaystyle{r_j - r_{j-2} = \frac{(-1)^{j}a_j}{k_jk_{j-2}}}$ for each $j \geq 0$.
• Proof of a) If $j \geq 0$ then by Lemma 2 (a) we have that:
(7)
\begin{align} \quad h_jk_{j-2} - h_{j-2}k_j &= [a_jh_{j-1} + h_{j-2}]k_{j-2} - h_{j-2}[a_jk_{j-1} + k_{j-2}] \\ &= a_jh_{j-1}k_{j-2} + h_{j-2}k_{j-2} - a_jh_{j-2}k_{j-1} - h_{j-2}k_{j-2} \\ &= a_j[h_{j-1}k_{j-2} - h_{j-2}k_{j-1}] \\ &= a_j(-1)^{j-2} \\ &= (-1)^ja_j \quad \blacksquare \end{align}
• Proof of b) If $j \geq 0$ then by Lemma 3 (a) we have that:
(8)
\begin{align} \quad r_j - r_{j-2} = \frac{h_j}{k_j} - \frac{h_{j-2}}{k_{j-2}} = \frac{h_jk_{j-2} - h_{j-2}k_j}{k_jk_{j-2}} = \frac{(-1)^ja_j}{k_jk_{j-2}} \quad \blacksquare \end{align}
 Corollary 4: Let $\langle a_0; a_1, a_2, ... \rangle$ be an infinite simple continued fraction with $a_0 \in \mathbb{Z}$ and $a_n \in \mathbb{N}$ for $n \geq 1$. Then $(h_j, k_j) = 1$ for all $j \geq -2$.
• Proof: Clearly it is true for $j = -2$ and $j = -1$. For $j \geq 0$, by Lemma 2 (a) we have that:
(9)
\begin{equation} h_jk_{j-1} - h_{j-1}k_j = (-1)^{j-1} \end{equation}
• Suppose that $(h_j, k_j) = d$. Then from the equation above, $d | (-1)^{j-1}$. So $d = 1$. $\blacksquare$