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:

    “This declared indifference, but as I must think, covert real zeal for the spread of slavery, I can not but hate. I hate it because of the monstrous injustice of slavery itself. I hate it because it deprives our republican example of its just influence in the world ... and especially because it forces so many really good men amongst ourselves into an open war with the very fundamental principles of civil liberty.”
    —Abraham Lincoln (1809–1865)

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