information:classification, information:highlighting, stylistic:tone
Defining a sequence by recursion

Sequences whose elements are related to the previous elements in a straightforward way are often defined using recursion. This is in contrast to the definition of sequences of elements as functions of their positions.

To define a sequence by recursion, one needs a rule, called recurrence relation to construct each element in terms of the ones before it. In addition, enough initial elements must be provided so that all subsequent elements of the sequence can be computed by successive applications of the recurrence relation.

The Fibonacci sequence is a simple classical example, defined by the recurrence relation

with initial terms a 0 = 0 {\displaystyle a_{0}=0} and a 1 = 1 {\displaystyle a_{1}=1}. From this, a simple computation shows that the first ten terms of this sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.

A complicated example of a sequence defined by a recurrence relation is Recamán's sequence, defined by the recurrence relation

with initial term a 0 = 0. {\displaystyle a_{0}=0.}

A linear recurrence with constant coefficients is a recurrence relation of the form

where c 0, …, c k {\displaystyle c_{0},\dots,c_{k}} are constants. There is a general method for expressing the general term a n {\displaystyle a_{n}} of such a sequence as a function of n; see Linear recurrence. In the case of the Fibonacci sequence, one has c 0 = 0, c 1 = c 2 = 1, {\displaystyle c_{0}=0,c_{1}=c_{2}=1,} and the resulting function of n is given by Binet's formula.

A holonomic sequence is a sequence defined by a recurrence relation of the form

where c 1, …, c k {\displaystyle c_{1},\dots,c_{k}} are polynomials in n. For most holonomic sequences, there is no explicit formula for expressing a n {\displaystyle a_{n}} as a function of n. Nevertheless, holonomic sequences play an important role in various areas of mathematics. For example, many special functions have a Taylor series whose sequence of coefficients is holonomic. The use of the recurrence relation allows a fast computation of values of such special functions.

Not all sequences can be specified by a recurrence relation. An example is the sequence of prime numbers in their natural order (2, 3, 5, 7, 11, 13, 17,...).