# Continued Fractions, Attempt 3, Part 6: Recurrence Relation for Convergents

## 1. Representing Convergents as Quotients

Let $\gamma$ be a regular infinite continued fraction $((a_0, b_0), (a_1, b_1), (a_2, b_2), \ldots)$, and $c_n$ the $n$-th convergent of $\gamma$.

Theorem 6.1. We have $c_n=p_n/q_n$, where $p_n$ and $q_n$ are defined by the recurrence relation \begin{aligned} \phantom{\text{(6.1a)}}&\hspace{4em} & p_{n+2}&=a_{n+1}p_{n+1}+b_np_n, & p_1&=a_0, & p_0&=1, & \hspace{4em}&\text{(6.1a)} \\ \phantom{\text{(6.1b)}}& & q_{n+2}&=a_{n+1}q_{n+1}+b_nq_n, & q_1&=1, & q_0&=0. & &\text{(6.1b)} \end{aligned}

Proof. By definition, we have \begin{aligned} c_n&=\lang(a_0,b_0),(a_1,b_1),\ldots,(a_{n-1},b_{n-1})\rang \\ &=(\phy\circ\pi_{a_0,b_0}\circ\pi_{a_1,b_1}\circ\cdots\circ\pi_{a_{n-1},b_{n-1}})\left(\B{1}{0}\right). \end{aligned} Since $\gamma$ is regular, we have \begin{aligned} (\pi_{a_0,b_0}\circ\pi_{a_1,b_1}\circ\cdots\circ\pi_{a_{n-1},b_{n-1}})\left(\B{1}{0}\right)=\left[M(a_0,b_0)M(a_1,b_1)\cdots M(a_{n-1},b_{n-1})\V{1}{0}\right]. \end{aligned}

Define $L_n$ by the recurrence relation $L_{n+1}=L_nM(a_n,b_n), \quad L_0=\M{1}{0}{0}{1}.$ If we write $L_n=\M{p_n}{r_n}{q_n}{s_n}$, we have $c_n=\phy\left(\left[L_n\V{1}{0}\right]\right)=\frac{p_n}{q_n}.$ Let us simplify the recurrence relation for $L_n$. We have \begin{aligned} p_{n+1}&=a_np_n+r_n, & p_0&=1, \\ q_{n+1}&=a_nq_n+s_n, & q_0&=0, \\ r_{n+1}&=b_np_n, & r_0&=0, \\ s_{n+1}&=b_nq_n, & s_0&=1. \end{aligned} By eliminating $r_n$ and $s_n$, we get $L_{n+1}=\M{p_{n+1}}{b_np_n}{q_{n+1}}{b_nq_n}$ and the recurrence relation $\text{(6.1a)}$, $\text{(6.1b)}$.

Corollary 6.2. Regarding $p_n$’s and $q_n$’s as multivariate polynomials of $a_n$’s and $b_n$’s, we can write $q_n=\frac{\partial p_n}{\partial a_0}.$

Proof. Differentiating $\text{(6.1a)}$ with respect to $a_0$ gives $\text{(6.1b)}$.

Corollary 6.3. We have $p_n=\det\begin{pmatrix} a_0 & b_0 & 0 & \cdots & 0 & 0 \\ -1 & a_1 & b_1 & \cdots & 0 & 0 \\ 0 & -1 & a_2 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & a_{n-2} & b_{n-2} \\ 0 & 0 & 0 & \cdots & -1 & a_{n-1} \end{pmatrix}.$ Note that we regard the determinant of the $0\times0$ matrix as $1$.

Proof. Define $u_n$ as the above determinant. By cofactor expansion with respect to the last row, we have $u_{n+2}=a_{n+1}u_{n+1}+b_nu_n,$ and $u_1=a_0$, $u_0=1$. This is the same recurrence relation as $\text{(6.1a)}$, and therefore $p_n=u_n$.

Remark. The determinant $\det\begin{pmatrix} x_0 & y_0 & 0 & \cdots & 0 & 0 \\ z_0 & x_1 & y_1 & \cdots & 0 & 0 \\ 0 & z_1 & x_2 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & x_{n-2} & y_{n-2} \\ 0 & 0 & 0 & \cdots & z_{n-2} & x_{n-1} \end{pmatrix}$ is called an extended continuant. $p_n$ is a special type of this.

## 2. Recurrence Relation For Convergents

Corollary 6.4. For any $n\in\N$, $c_{n+1}$ and $c_n$ cannot be simultaneously $\infty$.

Proof. Let us prove by contradiction. Assume $c_{k+1}=\infty$ and $c_k=\infty$ for some $k\in\N$. Then, we have $q_{k+1}=0$ and $q_k=0$. Since $q_n=\frac{q_{n+2}-a_{n+1}q_{n+1}}{b_n}$ for any $n\in\N$, we have $q_1=0$. This is a contradiction.

Corollary 6.5. For any $n\in\N$, we have $c_{n+1}-c_n=(-1)^{n+1}\frac{b_{n-1}b_{n-2}\cdots b_0}{q_{n+1}q_n}.$

Note that the left hand side is well-defined because of Corollary 6.4.

Proof. First, assume $c_{n+1}=\infty$. Then, the LHS is $\infty$, and the RHS is also $\infty$ because $q_{n+1}=0$.

Next, assume $c_n=\infty$. Then, the LHS is $\infty$, and the RHS is also $\infty$ because $q_n=0$.

Lastly, assume $c_{n+1}\ne\infty$ and $c_n\ne\infty$. Then, we have $c_{n+1}-c_n=\frac{p_{n+1}}{q_{n+1}}-\frac{p_n}{q_n}=\frac{p_{n+1}q_n-p_nq_{n+1}}{q_{n+1}q_n}=\frac{\det L_{n+1}}{b_nq_{n+1}q_n}$ and $\det L_{n+1}=\det M(a_0,b_0)\det M(a_1,b_1)\cdots\det M(a_n,b_n)= (-1)^{n+1}b_0b_1\cdots b_n.$

## Appendix

The first few $c_n$’s, written in the form of $p_n/q_n$, 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}