Fundamental recurrence formulas

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

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 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.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Generalized continued fraction — In analysis, a generalized continued fraction is a generalization of regular continued fractions in canonical form in which the partial numerators and the partial denominators can assume arbitrary real or complex values.A generalized continued… …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • Convergent (continued fraction) — A convergent is one of a sequence of values obtained by evaluating successive truncations of a continued fraction. The nth convergent is also known as the nth approximant of a continued fraction.[1] Contents 1 Representation of real numbers 2… …   Wikipedia

  • Solving quadratic equations with continued fractions — In mathematics, a quadratic equation is a polynomial equation of the second degree. The general form is:ax^2+bx+c=0,,!where a ne; 0.Students and teachers all over the world are familiar with the quadratic formula that can be derived by completing …   Wikipedia

  • Euler's continued fraction formula — In the analytic theory of continued fractions, Euler s continued fraction formula is an identity connecting a certain very general infinite series with an infinite continued fraction. First published in 1748, it was at first regarded as a simple… …   Wikipedia

  • Complete quotient — In the metrical theory of regular continued fractions, the kth complete quotient ζ k is obtained by ignoring the first k partial denominators ai. For example, if a regular continued fraction is given by then the successive complete quotients ζ k… …   Wikipedia

  • Padé table — In complex analysis, a Padé table is an array, possibly of infinite extent, of the rational Padé approximants : R m , n to a given complex formal power series. Certain sequences of approximants lying within a Padé table can often be shown to… …   Wikipedia

  • Fast Fourier transform — A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex number arithmetic to group …   Wikipedia

  • Gamma function — For the gamma function of ordinals, see Veblen function. The gamma function along part of the real axis In mathematics, the gamma function (represented by the capital Greek letter Γ) is an extension of the factorial function, with its… …   Wikipedia

  • Bernoulli number — In mathematics, the Bernoulli numbers Bn are a sequence of rational numbers with deep connections to number theory. They are closely related to the values of the Riemann zeta function at negative integers. There are several conventions for… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”