The Sequences (hn) and (kn)

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

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

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

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