Sequences defined by recurrence

As well as being given by an explicit formula for $a_n$, a sequence can be described by indicating how to build each term starting from the previous ones.

Definition — Sequence by recurrence

A sequence is said to be defined by recurrence if, by assigning the first term (or the first $k$ terms) and a rule that expresses $a_{n+1}$ in terms of $a_n$ (or of several previous terms), every subsequent term is determined.

Example — Fibonacci sequence

$F_0 = 0$, $\;F_1 = 1$, $\;F_{n+1} = F_n + F_{n-1}$: $0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots$

Links

Topics: Sequences
Concepts: Sequence · Sequence by recurrence
People: Leonardo Fibonacci