Recursive definitions

An alternative way to describe a sequence is to list a few terms and to give a rule for computing the rest of the sequence. Our example (1) above can be described by the starting value $a_1=1$ and the rule $a_{n+1}=2a_n$ for integers $n \ge 1$. Starting from $a_1=1$, the rule implies that

$$a_2 = 2a_1 = 2(1) = 2$$

$$a_3 = 2a_2 = 2(2) = 4$$

$$a_4 = 2a_3 = 2(4) = 8,$$

and so on; each term in the sequence can be computed recursively in terms of the terms previously computed. A rule such as this giving the next term in terms of earlier terms is also called a recurrence relation (or simply recurrence).