[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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, ... .


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:



List of subsets










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:

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.


2014-06-17 11:58