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 xi is x(i).
1. Some common sequences
- Geometric progression
xi = ari. Example: 1, 2, 4, 8, 16, ... .
- Arithmetic progression
xi = a+di. Example: 1, 5, 11, 16, 21, 26, ... .
- Strings
The string x = "abracadrabra" can be thought of as a sequence with x0 = "a", x2 = "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 |
xn |
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 2n 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 xi = x2/2 + x/2 + 1. Then x0 = 1, x1 = 1/2 + 1/2 + 1 = 2, x2 = 4/2 + 2/2 + 1 = 2+1+1 = 4, etc. But for larger values of i, it seems unlikely that xi = 2i. (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 xi+1 = xi + d for all i, it's an arithmetic progression.
If there is some r for which xi+1 = r xi 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 xi, you can at least compute xi by figuring out where i falls in the repeating block.
For some sequences, it's possible to write xi 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 xi = xi-1 + xi-2, with x0 = x1 = 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.