Recurrence Formula

(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

Φ₁ = 1

Φ_π+2 = Φ_π+1 + Φ_πn ≥ 0

The last of these formulas is a recurrence formula and can be used to compute Φ₂, Φ₃, and subsequent terms of the sequence.

(2) Suppose

It can be easily proved that if n ≥ 2,

This recurrence formula reduces the calculation of I_n to the calculation of I₀ or I₁ 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,