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

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

These recurrence relations are due to John Wallis (1616-1703) and Leonhard Euler (1707-1783)

Read more about Fundamental Recurrence Formulas:  The Determinant Formula, A Simple Example

Famous quotes containing the words fundamental, recurrence and/or formulas:

    “What is wanted—whether this is admitted or not—is nothing less than a fundamental remolding, indeed weakening and abolition of the individual: one never tires of enumerating and indicting all that is evil and inimical, prodigal, costly, extravagant in the form individual existence has assumed hitherto, one hopes to manage more cheaply, more safely, more equitably, more uniformly if there exist only large bodies and their members.”
    —Friedrich Nietzsche (1844–1900)

    “Forgetfulness is necessary to remembrance. Ideas are retained by renovation of that impression which time is always wearing away, and which new images are striving to obliterate. If useless thoughts could be expelled from the mind, all the valuable parts of our knowledge would more frequently recur, and every recurrence would reinstate them in their former place.”
    —Samuel Johnson (1709–1784)

    “You treat world history as a mathematician does mathematics, in which nothing but laws and formulas exist, no reality, no good and evil, no time, no yesterday, no tomorrow, nothing but an eternal, shallow, mathematical present.”
    —Hermann Hesse (1877–1962)