The Sequences (hn) and (kn)

Definition: Let $a_0 \in \mathbb{Z}$ and let $a_n \in \mathbb{N}$ for all $n \geq 1$. The corresponding sequence $(h_n)_{n \geq -2}$ is defined recursively by $h_{-2} = 0$, $h_{-1} = 1$, and $h_n = a_nh_{n-1} + h_{n-2}$ for $n \geq 0$. The corresponding sequence $(k_n)_{n \geq -2}$ is defined recursively by $k_{-2} = 1$, $k_{-1} = 0$, and $k_n = a_nk_{n-1} + k_{n-2}$ for $n \geq 0$.

Note that the sequences $(h_n)$ and $(k_n)$ start at $n = -2$. Furthermore, if $(a_n)$ is an infinite sequence then so is $(h_n)$ and $(k_n)$. If $(a_n)$ is a finite sequence then so is $(h_n)$ and $(k_n)$.

If $\langle x_0; x_1, x_2, ... \rangle$ is a simple continued fraction (finite or infinite) then we can obtain corresponding sequences $(h_n)$ and $(k_n)$ using $(x_n)$. For example, consider the simple continued fraction $\langle 2; 4, 6, 8 \rangle$. Then the corresponding $(h_n)$ and $(k_n)$ are given in the following table:

$n$	$x_n$	$h_n$	$k_n$
$-2$	-	$0$	$1$
$-1$	-	$1$	$0$
$0$	$2$	$2$	$1$
$1$	$4$	$9$	$4$
$2$	$6$	$56$	$25$
$3$	$8$	$457$	$204$

The following theorem connects continued fractions to the sequences $(h_n)$ and $(k_n)$.

Theorem 1: Let $\langle a_0; a_1, a_2, ..., a_{n-1}, x \rangle$ be a simple continued fraction where $a_0 \in \mathbb{Z}$ and $a_m \in \mathbb{N}$ for each $1 \leq m \leq n - 1$. Then for all $x > 0$, $\displaystyle{\langle a_0; a_1, a_2, ..., a_{n-1}, x \rangle = \frac{xh_{n-1} + h_{n-2}}{xk_{n-1} + k_{n-2}}}$.

• Proof: We prove Theorem 1 by mathematical induction.

• For the base step, observe that $\langle x \rangle = x$, and:

(1)

\begin{align} \quad \frac{xh_{-1} + h_{-2}}{k_{-1} + h_{-2}} = \frac{x(1) + 0}{0 + 1} = \frac{x}{1} = x \end{align}

• So the theorem is true when $n = 0$. Suppose that for some $m \geq 0$ that $\displaystyle{\langle a_0; a_1, ..., a_{m-1}, x \rangle = \frac{xh_{m-1} + h_{m-2}}{xk_{m-1} + k_{m-2}}}$ for all $x > 0$. Using the identity that $\langle a_0; a_1, ..., a_m, x \rangle = \left \langle a_0; a_1, ..., a_m + \frac{1}{x} \right \rangle$ and observing that $a_m + \frac{1}{x} > 0$, we have that:

(2)

\begin{align} \quad \langle a_0; a_1, a_2, ..., a_m, x \rangle &= \left \langle a_0; a_1, ..., a_m + \frac{1}{x} \right \rangle \\ & \overset{I.H.}= \frac{\left (a_m + \frac{1}{x} \right )h_{m-1} + h_{m-2}}{\left (a_m + \frac{1}{x} \right )k_{m-1} + k_{m-2}} \\ &= \frac{(a_mx + 1)h_{m-1} + xh_{m-2}}{(a_mx + 1)k_{m-1} + xk_{m-2}} \\ &= \frac{a_mxh_{m-1} + h_{m-1} + xh_{m-2}}{a_mxk_{m-1} + k_{m-1} + xk_{m-2}} \end{align}

• Since $h_m = a_mh_{m-1} + h_{m-2}$ and $k_m = a_mk_{m-1} + k_{m-2}$, we have:

(3)

\begin{align} \quad \langle a_0; a_1, a_2, ..., a_m, x \rangle = \frac{xh_m + h_{m-1}}{xk_m + k_{m-1}} \end{align}

• Therefore the theorem is true by the principle of mathematical induction. $\blacksquare$