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 a_n (the partial numerators) and the b_n (the partial denominators) are numbers. Denoting the successive numerators and denominators of the fraction by A_n and B_n, 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.

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 A_n are {1, 2, 3, 5, 8, 13, ...} and the successive denominators B_n 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.