(or recursion formula), a formula that reduces the computation of the nth term of some sequence (most often, a numerical sequence) to the computation of one or more of the terms preceding the nth term. The relevant preceding terms are usually found “near” the nth term, the number of the relevant preceding terms is independent of n, and the nth term can be expressed by means of these terms in a relatively simple manner. Recurrence formulas of a more complex nature, however, are possible. The general problems involved in recursion computations are the subject of the theory of recursive functions.
Examples. (1) The sequence Φn of Fibonacci numbers is defined by the formulas
Φ0 = 0
Φ1 = 1
Φπ+2 = Φπ+1 + Φπn ≥ 0
The last of these formulas is a recurrence formula and can be used to compute Φ2, Φ3, and subsequent terms of the sequence.
(2) Suppose
It can be easily proved that if n ≥ 2,
This recurrence formula reduces the calculation of In to the calculation of I0 or I1 depending on whether η is odd or even.
Recurrence formulas usually provide a convenient computational scheme for finding the terms of a sequence one after another. Sometimes, however, an attempt is made to obtain on the basis of recurrence formula an “explicit” expression for the nth term of the sequence described by the formula. Thus, in the case of the Fibonacci numbers,
Want to thank TFD for its existence? Tell a friend about us, add a link to this page, add the site to iGoogle, or visit the webmaster's page for free fun content.
| ?Page tools | ||
|---|---|---|
|