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 s_k the k-th term. Also denote by aⁿ a block of n copies of a. Then we may represent any s_k uniquely as a string of blocks in such a way that if aⁿ is adjacent to b^m, then a doesn't equal b. (So the fifth entry 111221 becomes 1³2²1¹ in this notation.)

Now suppose s_k = a₁^n₁... a_m^n_m, where each a_i and each n_i is either 1,2,or 3, and no a_i equals a_i+1. (The length of s_k, as a string, is n₁+...+n_m.) Then s_k+1= n₁a₁... n_ma_m. (The length of s_k+1 is 2m.) If there were a block of length four in s_k+1, then there would have to be some i such that a_i = n_i+1 = a_i+1, an impossibility. The exact same argument shows that there can be no digits larger than 4 either.