Fundamental recurrence formulas

In the theory of continued fractions, the fundamental recurrence formulas relate the partial numerators and the partial denominators with the numerators and denominators of the fraction's successive convergents. Let

\[ x = b_0 + \cfrac{a_1}{b_1 + \cfrac{a_2}{b_2 + \cfrac{a_3}{b_3 + \cfrac{a_4}{b_4 + \ddots\,}}}} \]

be a general continued fraction, where the an (the partial numerators) and the bn (the partial denominators) are numbers. Denoting the successive numerators and denominators of the fraction by An and Bn, respectively, the fundamental recurrence formulas are given by

\[ \begin{align} A_0& = b_0& B_0& = 1\\ A_1& = b_1 b_0 + a_1& B_1& = b_1\\ A_{n+1}& = b_{n+1} A_n + a_{n+1} A_{n-1}& B_{n+1}& = b_{n+1} B_n + a_{n+1} B_{n-1}\, \end{align} \]

The continued fraction's successive convergents are then given by

\[ x_n=\frac{A_n}{B_n}.\,

These recurrence relations are due to John Wallis (1616-1703).
The determinant formula

It can be shown, by induction, that the determinant formula

\[ A_{n-1}B_n - A_nB_{n-1} = (-1)^na_1a_2\cdots a_n = \Pi_{i=1}^n (-a_i)\, \]

holds for all positive integers n > 0. If neither B_n-1 nor B_n is zero, this relationship can also be used to express the difference between two successive convergents of the continued fraction.

\[ x_{n-1} - x_n = \frac{A_{n-1}}{B_{n-1}} - \frac{A_n}{B_n} = (-1)^n \frac{a_1a_2\cdots a_n}{B_nB_{n-1}} = \frac{\Pi_{i=1}^n (-a_i)}{B_nB_{n-1}}\, \]

It is necessary but not sufficient for the convergence of an infinite continued fraction that the difference between successive convergents approaches zero; this is the subject of the convergence problem. (Note: By definition, the continued fraction converges if the sequence of convergents has a limit.)
A simple example

Consider the regular continued fraction in canonical form that represents the golden ratio φ:

\[ x = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \ddots\,}}}} \]

Applying the fundamental recurrence formulas we find that the successive numerators An are {1, 2, 3, 5, 8, 13, ...} and the successive denominators Bn are {1, 1, 2, 3, 5, 8, ...}, the Fibonacci numbers. Since all the partial numerators in this example are equal to one, the determinant formula assures us that the absolute value of the difference between successive convergents approaches zero quite rapidly.