Fundamental recurrence formulas

From Wikipedia, the free encyclopedia

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}{\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}.\,

[edit] 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 Bn-1 nor Bn 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}}\,

Expressed this way, the determinant formula suggests the most obvious direct attack on the convergence problem; if the difference between successive convergents approaches zero, the continued fraction must converge. Unfortunately this naive approach cannot be carried through in many cases. It's much harder to prove convergence for infinite continued fractions, in general, than it is for infinite series.

[edit] 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}{\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.