Recall that a **sequence** is a function, often from the naturals **N**, from **N**-{0}, or from initial prefix of the naturals (for finite sequences) to some set. Given a sequence x, its *i-th element* x_{i} is x(i).

# 1. Some common sequences

- Geometric progression
x

_{i}= ar^{i}. Example: 1, 2, 4, 8, 16, ... .- Arithmetic progression
x

_{i}= a+di. Example: 1, 5, 11, 16, 21, 26, ... .- Strings
The string x = "abracadrabra" can be thought of as a sequence with x

_{0}= "a", x_{2}= "b", etc.

# 2. Recognizing sequences

A common problem in discrete math and computer science is to recognize a sequence that you've observed by looking at small cases. For example, if you want to count the number of subsets of an n-element set, you might start by computing the first few terms of the sequence:

n |
x |
List of subsets |

0 |
1 |
{} |

1 |
2 |
{},{1} |

2 |
4 |
{},{1},{2},{1,2} |

Now for a general rule it would help to be able to find a sequence that starts 1, 2, 4, ... . A natural guess is that this is a geometric progression with a = 1 and r = 2. This would suggest that an n-element set always has 2^{n} elements, which you could then try to prove (e.g., by using induction.)

It's a bit dangerous, however, to generalize from the first few terms of a sequence without having some actual proof that the rule you come up with works. For example, here's another sequence that starts 1, 2, 4, ...: let x_{i} = x^{2}/2 + x/2 + 1. Then x_{0} = 1, x_{1} = 1/2 + 1/2 + 1 = 2, x_{2} = 4/2 + 2/2 + 1 = 2+1+1 = 4, etc. But for larger values of i, it seems unlikely that x_{i} = 2^{i}. (Try i = 3 and see what happens.)

Bearing this caveat in mind, there are nonetheless some good tricks for identifying sequences that work most of the time:

If there is some d for which x

_{i+1}= x_{i}+ d for all i, it's an arithmetic progression.If there is some r for which x

_{i+1}= r x_{i}for all i, it's a geometric progression.Some sequences repeat, e.g. 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 7, 1, 4, ... . Here even if you can't find an explicit formula for x

_{i}, you can at least compute x_{i}by figuring out where i falls in the repeating block.For some sequences, it's possible to write x

_{i}as a combination of more than one previous term. For example, the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... is given by the rule x_{i}= x_{i-1}+ x_{i-2}, with x_{0}= x_{1}= 1.

And if all else fails, you can ask an expert. The expert to ask for integer sequences is Neil Sloane. He is probably too busy to answer email, but much of what he knows about integer sequences can be found in his On-Line Encyclopedia of Integer Sequences.