Fundamental recurrence formulas

Remarks

Proof idea: write $x_n = t_0 \circ t_1 \circ \cdots \circ t_n(0)$ with $t_0(w) = b_0 + w$ and $t_k(w) = \frac{a_k}{b_k + w}$. These are Möbius transformations, and the product of their matrices is $\begin{pmatrix} A_{n-1} & A_n \\ B_{n-1} & B_n \end{pmatrix}$ by induction. Taking determinants gives item 2, and applying the product to $0$ gives item 1; item 2 shows that $A_n$ and $B_n$ do not both vanish. Example: for $1 + \cfrac{1}{2 + \cfrac{1}{2 + \cdots}}$ the recurrences give $A_n = 1, 3, 7, 17, \dots$ and $B_n = 1, 2, 5, 12, \dots$, the convergents of $\sqrt{2}$. Item 2 gives $x_n - x_{n-1} = \dfrac{(-1)^{n-1} a_1 \cdots a_n}{B_n B_{n-1}}$, so the convergents are the partial sums of a series, and convergence questions become questions about series.

Going deeper

For a student

The numerators $A_n$ and denominators $B_n$ satisfy a three-term linear recurrence, the same one for both. For a simple continued fraction they reduce to the recurrences for $p_n$ and $q_n$, and item 2 becomes $p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}$. The difference formula in the remarks is the starting point of the Śleszyński–Pringsheim theorem and other convergence tests for continued fractions.