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:

    “Much of what contrives to create critical moments in parenting stems from a fundamental misunderstanding as to what the child is capable of at any given age. If a parent misjudges a child’s limitations as well as his own abilities, the potential exists for unreasonable expectations, frustration, disappointment and an unrealistic belief that what the child really needs is to be punished.”
    —Lawrence Balter (20th century)

    “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)

    “That’s the great danger of sectarian opinions, they always accept the formulas of past events as useful for the measurement of future events and they never are, if you have high standards of accuracy.”
    —John Dos Passos (1896–1970)