# Recurrence Formula

## Recurrence Formula

(or recursion formula), a formula that reduces the computation of the *n*th term of some sequence (most often, a numerical sequence) to the computation of one or more of the terms preceding the *n*th 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 *n*th 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

*Φ*of Fibonacci numbers is defined by the formulas

_{n}*Φ*_{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 *I _{n}* to the calculation of

*I*

_{0}or

*I*

_{1}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 *n*th term of the sequence described by the formula. Thus, in the case of the Fibonacci numbers,