next up previous
Next: Linear recursive sequences Up: Linear recursive sequences Previous: Sequences

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

$\displaystyle a_2$ $\displaystyle = 2a_1 = 2(1) = 2$    
$\displaystyle a_3$ $\displaystyle = 2a_2 = 2(2) = 4$    
$\displaystyle a_4$ $\displaystyle = 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).

Zvezdelina Stankova-Frenkel 2000-09-20