Editing Sequence (section)

===Defining a sequence by recursion===
{{main|Recurrence relation}}
Sequences whose elements are related to the previous elements in a straightforward way are often defined using [[Recursive definition|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
:<math>a_n = a_{n-1} + a_{n-2},</math>
with initial terms <math>a_0 = 0</math> and <math>a_1 = 1</math>. 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]],<ref>{{cite OEIS|1=A005132|2=Recamán's sequence|access-date=26 January 2018}}</ref> defined by the recurrence relation
:<math>\begin{cases}a_n = a_{n-1} - n,\quad \text{if the result is positive and not already in the previous terms,}\\a_n = a_{n-1} + n, \quad\text{otherwise},
\end{cases}</math>
with initial term <math>a_0 = 0.</math>

A ''linear recurrence with constant coefficients'' is a recurrence relation of the form
:<math>a_n=c_0 +c_1a_{n-1}+\dots+c_k a_{n-k},</math>
where <math>c_0,\dots, c_k</math> are [[constant (mathematics)|constants]]. There is a general method for expressing the general term <math>a_n</math> of such a sequence as a function of {{mvar|n}}; see [[Linear recurrence]]. In the case of the Fibonacci sequence, one has <math>c_0=0, c_1=c_2=1,</math> and the resulting function of {{mvar|n}} is given by [[Binet's formula]].

A [[holonomic sequence]] is a sequence defined by a recurrence relation of the form 
:<math>a_n=c_1a_{n-1}+\dots+c_k a_{n-k},</math>
where <math>c_1,\dots, c_k</math> are [[polynomial]]s in {{mvar|n}}. For most holonomic sequences, there is no explicit formula for expressing <math>a_n</math> as a function of {{mvar|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 number]]s in their natural order (2, 3, 5, 7, 11, 13, 17, ...).