What comes next: 1, 2, 5, ...

What comes next in this sequence: 1, 2, 5, ...?

I know of at least seven reasonable answers: 10, 11, 12, 13, 14, or 15.

Here are explanations for each of them. Throughout, I'll denote the nth term of each sequence by a_n, where indexing starts at 1. (So a₃ = 5, and we're looking for a₄. This indexing convention is awkward for the first couple cases but agrees with the conventional indexing for Catalan and Bell numbers.)

1, 2, 5, 10, ... -- a_n = (n-1)² + 1.

1, 2, 5, 11, ... --

1, 2, 5, 12, ... -- a_n = 2a_n-1 + a_n-2, where a₁ = 1, a₂ = 2. This sequence occurs in the convergents of the continued fraction for √2. The first few convergents are

1/1, 3/2, 7/5, 17/12, 41/29

and in general the nth convergent, b_n/a_n, has a_n = a_n-1 + b_n-1, b_n = a_n + b_n-1, with a₁ = b₁ = 1. An explicit formula for these is given by

1, 2, 5, 13, ... -- alternate members of the Fibonacci sequence, which begins 1, 1, 2, 3, 5, 8, 13. If you don't like referring to another sequence, this one can be defined by the recurrence a_n = 3a_n-1 - a_n-2, where a₁ = 1, a₂ = 2. An exact formula for the nth Fibonacci number is f_n = (φⁿ - (-&phi)^-n)/√5, where φ = (-1+√5)/2; then a_n = f_2n-1.

1, 2, 5, 14, ... -- the Catalan numbers. These satisfy . The Catalan numbers count basically everything. Okay, not everything. But in Richard Stanley's book Enumerative Combinatorics, he gives 66 sets counted by Catalan numbers; he has an ever-expanding list of them on his web site, which is currently up to 162, numbered (a), (b), (c), ..., (z), (aa), ..., (zz), (aaa), ... (zzz), (a⁴), ..., (z⁴), ..., (f⁷). This list may hold the prize for "longest list of things indicated by letters". The canonical example of "things counted by Catalan numbers" is binary trees, counted by number of leaves, and most of these other things can eventually be reduced to that case. The Catalan numbers satisfy the nice recurrence

which explains why they're so prevalent; they correspond to combinatorial objects that can be generated recursively, where each object of size n+1 consists of a pair of similar objects whose sizes together add up to n.

1, 2, 5, 15, ... -- the Bell numbers. These are the number of set partitions of the set {1, 2, ..., n}; that is, the number of ways to arrange n balls in some boxes. For four balls, we have the partitions

1234, 123/4, 124/3, 134/2, 234/1, 12/34, 13/24, 14/23, 12/3/4, 13/2/4, 14/2/3, 23/1/4, 24/1/3, 34/1/2, 1/2/3/4

where slashes separate the different boxes. There's no explicit formula for these, but they satisfy the recursion

which can be justified as follows. If we want to count set partitions of {1, 2, ..., n+1}, we can count them by the number of elements in the block containing n+1. The number of set partitions of {1, 2, ..., n+1} where n+1 is in a block of size j+1 is ; we can pick the j elements which are in the same block as n+1 and then make a set partition out of the remaining n-j elements. Thus

and letting k = n-j and recalling ${n \choose n-k} = {n \choose k}$ gives the desired result.

These sequences diverge from each other quickly; the next term of each sequence is 17, 21, 29, 34, 42, and 52 respectively. And the growth rates of the six sequences in question are quite different; roughly, the sequences given here grow like n², n³/6, (1+&sqrt;(2))ⁿ, ((3+&sqrt;(5))/2)ⁿ, 4ⁿ/(π n³)^1/2, and (really fast). Their generating functions also look quite different. For the first five sequences, we have ordinary generating functions which converge in some neighborhood of the origin, which are

but the last one doesn't even have a convergent ordinary generating function; its exponential generating function is exp(exp(z)-1). There's a subtle difference among the ordinary generating functions as well -- the first two have singularities at z=1, so the sequences they represent grow only as fast as powers of n, while the last three have singularities closer to the origin than z=1, so the sequences they represent grow roughly exponentially.

This is all an example of what I've heard called "the law of small numbers" -- the fact that there just aren't enough small numbers to avoid numerical coincidences like these.