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:

    “Our species successfully raised children for tens of thousands of years before the first person wrote down the word “psychology.” The fundamental skills needed to be a parent are within us. All we’re really doing is fine-tuning a process that’s already remarkably successful.”
    —Lawrence Kutner (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)

    “It is sentimentalism to assume that the teaching of life can always be fitted to the child’s interests, just as it is empty formalism to force the child to parrot the formulas of adult society. Interests can be created and stimulated.”
    —Jerome S. Bruner (20th century)