ABSTRACT
We will then study integer sequences in general, with a focus on recursively defined sequences. For example, the sequence 1,2,4,8, . . . is recursively defined by an = 2an−1. This sequence is also defined by the formula an = 2n. A general question is how to find formulas (in terms of n rather than an−1, etc.) for recurrences; this is important because it’s faster to compute using a formula than using a recurrence. Once a formula is found, we need to prove that it is correct. Induction is the proof method of choice, as the recursive definition of a sequence usually provides the induction step in the proof.
