### PUZZLE #5: WHAT'S THE NEXT NUMBER? (SOLUTION)

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ...

The first four or five entries of this sequence was the title of a talk that John H. Conway gave at Marquette in the mid 1980s. In the abstract, he said that while he himself hadn't dreamed up the sequence, he was fascinated by it and set about to determine some of its properties. Unfortunately, I had to be out of town that day, and couldn't attend the talk. People told me that I'd missed a really entertaining presentation.

I'm told that women usually see the pattern sooner then men and that nonmathematicians generally get it before mathematicians do. The secret is to sound it out, counting digits from left to right. The first entry is one 1, hence the second entry is 11. But that entry is two 1s, so the third entry is 21. And so on.

What digits are possible? We see 1, 2, and 3 appear; will there ever be a 4? If so, then the first entry in which a 4 appears will have to result from a block of four identical digits in the previous entry. So let's prove this cannot happen by showing inductively that any block of identical digits can have length at most 3. (We get a block of 3 ones by the fifth entry.) So our inductive assumption is that only 1,2,3 appear in term k and that there are no blocks of any length greater than three in that term. Denote by sk the k-th term. Also denote by an a block of n copies of a. Then we may represent any sk uniquely as a string of blocks in such a way that if an is adjacent to bm, then a doesn't equal b. (So the fifth entry 111221 becomes 132211 in this notation.)

Now suppose sk = a1n1... amnm, where each ai and each ni is either 1,2,or 3, and no ai equals ai+1. (The length of sk, as a string, is n1+...+nm.) Then sk+1= n1a1... nmam. (The length of sk+1 is 2m.) If there were a block of length four in sk+1, then there would have to be some i such that ai = ni+1 = ai+1, an impossibility. The exact same argument shows that there can be no digits larger than 4 either.