April 29, 2020

Continued Fractions, Part 1: Convergents

Continued fractions seem to be somewhat a minor topic in modern mathematics, and I think it’s one of reasons why I’ve always been feeling difficulty in finding literature which gives minimal and clean description of them. So, I decided to create a starting point for that purpose.

Introduction

A continued fraction is, conceptually, a fraction of the form \[ a_0 + \cfrac{b_0}{a_1 + \cfrac{b_1}{a_2 + \cfrac{b_2}{\cdots}}}, \] where $a_k$ and $b_k$ are taken from a certain algebra depending on the context. We are going to give a precise definition and properties when this algebra is $\C$.

Definition

Let $\whC$ denote $\C \cup \{\infty\}$ and $\C^\times$ denote $\C \setminus \{0\}$. We include $0$ in $\N$.

Define $m_k:\whC\rightarrow\whC$ by $m_k(x) = a_k + \dfrac{b_k}{x}$ where $a_k \in \C$ and $b_k \in \C^\times$ for any $k\in\N$. Especially, we have $m_k(0) = \infty$ and $m_k(\infty) = a_k$.

A continued fraction is a sequence $\{c_k\}_{k\in\N}$ where $c_k\in\whC$ is defined by \[ c_{k+1} = (m_0\circ m_1\circ\cdots\circ m_k)(\infty), \quad c_0 = \infty. \] For example, we have \[ c_4=a_0+\cfrac{b_0}{a_1+\cfrac{b_1}{a_2+\cfrac{b_2}{a_3}}}. \] Each term $c_k$ of the sequence is called a convergent.

Properties of Convergents

Let $M_k$ be $\M{a_k}{b_k}{1}{0}\in\text{GL}_2(\C)$ and define $L_k$ by the recurrence relation \[ L_{k+1}=L_kM_k, \quad L_0=\M{1}{0}{0}{1}. \] Then $m_k$ is the associated Möbius transformation to $M_k$ and $m_0\circ m_1\circ\cdots\circ m_k$ to $L_{k+1}$. Therefore, if we write $L_k=\M{p_k}{r_k}{q_k}{s_k}$, we have $c_k=p_k/q_k$. On the other hand, we have \[ \begin{aligned} p_{k+1}&=a_kp_k+r_k, & p_0&=1, \\ q_{k+1}&=a_kq_k+s_k, & q_0&=0, \\ r_{k+1}&=b_kp_k, & r_0&=0, \\ s_{k+1}&=b_kq_k, & s_0&=1. \end{aligned} \] By eliminating $r_k$ and $s_k$, we get $L_{k+1}=\M{p_{k+1}}{b_kp_k}{q_{k+1}}{b_kq_k}$ and \[ \begin{aligned} \phantom{\text{(1.1a)}}&\hspace{4em} & p_{k+2}&=a_{k+1}p_{k+1}+b_kp_k, & p_1&=a_0, & p_0&=1, & \hspace{4em}&\text{(1.1a)} \\ \phantom{\text{(1.1b)}}& & q_{k+2}&=a_{k+1}q_{k+1}+b_kq_k, & q_1&=1, & q_0&=0. & &\text{(1.1b)} \end{aligned} \] This proves the following theorem.

Theorem. $c_k=p_k/q_k$ where $p_k$ and $q_k$ are defined by the recurrence relation $\text{(1.1a)}$ and $\text{(1.1b)}$.

When $c_{k+1}\ne\infty$ and $c_{k+2}\ne\infty$ for a certain $k\in\N$, we have \[ c_{k+2}-c_{k+1}=\frac{p_{k+2}}{q_{k+2}}-\frac{p_{k+1}}{q_{k+1}}=\frac{p_{k+2}q_{k+1}-p_{k+1}q_{k+2}}{q_{k+1}q_{k+2}}=\frac{\det L_{k+2}}{b_{k+1}q_{k+1}q_{k+2}} \] and \[ \det L_{k+2}=\det M_0 \det M_1 \cdots \det M_{k+1} = (-1)^k b_0b_1\cdots b_{k+1}. \] This proves the following corollary.

Corollary. For any $k\in\N$ which satisfies $c_{k+1}\ne\infty$ and $c_{k+2}\ne\infty$, we have \[ c_{k+2}-c_{k+1}=(-1)^k\frac{b_kb_{k-1}\cdots b_0}{q_{k+2}q_{k+1}}. \]

Remark. Since there is no $k\in\N$ for which both $c_{k+1}$ and $c_{k+2}$ are $\infty$, it is tempting to extend the above formula for the cases where either $c_{k+1}$ or $c_{k+2}$ is $\infty$. But the difficulty is we must handle $+\infty$, $-\infty$, and $\infty$ as if they are different elements although they are identical in the view of $\whC$. Therefore, we restrict ourselves to the cases where both are finite.

Appendix

The first few terms of $\{c_k\}_{k\in\N}$, written in the form of $p_k/q_k$, are \[ \begin{aligned} c_0&=\frac{1}{0}, \\ c_1&=\frac{a_0}{1}, \\ c_2&=\frac{a_1a_0+b_0}{a_1}, \\ c_3&=\frac{a_2a_1a_0+a_2b_0+b_1a_0}{a_2a_1+b_1}, \\ c_4&=\frac{a_3a_2a_1a_0+a_3a_2b_0+a_3b_1a_0+b_2a_1a_0+b_2b_0}{a_3a_2a_1+a_3b_1+b_2a_1}, \text{and} \\ c_5&=\frac{a_4a_3a_2a_1a_0+a_4a_3a_2b_0+a_4a_3b_1a_0+a_4b_2a_1a_0+a_4b_2b_0+b_3a_2a_1a_0+b_3a_2b_0+b_3b_1a_0}{a_4a_3a_2a_1+a_4a_3b_1+a_4b_2a_1+b_3a_2a_1+b_3b_1}. \end{aligned} \]

References

Revisions

Kenichi Kondo © 2001-2020