How to prove that the following sequence will never contains number greater than 3

You may now the following sequence:

1
11
21
1211
111221
312211
13112221


Explanation of the sequence (I've put an hint just for the ones who want to search a bit ;) )

Where, in each iteration you count the number of occurrence of a digit then put the count and the digit in the new child. (First you've 1, then you've got one 1 (11), then you've got two 1(21)...)

I've the feeling that the numbers of the sequence will never contains a digit >3 but my mathematics knowledge are way to poor to prove it. So I've made a little program that compute the terms for me to found out if there is a number greater than 3 but up to the 42th term it doesn't find any.

As the length of the string is growing very fast, I can't compute a lot more terms and, even if I was able to do so, this would not be a proof.

So here's the question: How can I prove my feeling?

Consider the problem systematically: Starting with $1$, the sequence cannot contain the number $2$ until there are $2$ adjacent $1$s. Similarly, the sequence cannot contain $3$ until there are either $3$ adjacent $1$s or $3$ adjacent $2$s. Since the former will occur first, this occurs when there are $3$ adjacent $1$s.

Continuing this trend, it is not possible for the sequence to contain a $4$ until there are $4$ adjacent $1$s, $2$s, or $3$s.

In order to show that the number $4$ will not appear, you must show that there must not be $4$ adjacent $1$s, $2$s, or $3$s.

Assume that $\cdots 1111 \cdots$ occurs somewhere in the sequence, where the numbers preceding and succeeding this subsequence are not $1$. Thus, we have $\cdots a1111b \cdots$, $a,b \ne 1$.

There are two possible interpretations of the subsequence, depending on whether the index of $a$ is even or odd.

If even, the interpretation is that there were $a$ $1$s followed by $1\,$ $1$ followed by $1$ $b$ in the preceding sequence. However, if there were $a$ $1$s followed by $1\,$ $1$, we would simply write $(a+1)1$ in the sequence. Therefore, the subsequence $1111$ could not exist here.

If odd, the interpretation is that there was $1\,$ $1$ followed by $1\,$ $1$ in the preceding sequence; hence: $11$. However, this would be translated into the current sequence as $21$ rather than as $1111$. The subsequence $1111$ could not exist in this case either.

Similar logic will show that $2222$ and $3333$ cannot exist anywhere in the sequence. Therefore, as a result, the sequence cannot contain $4$ anywhere.

This is a typical proof by induction. The base case is just that the first term ($1$) does not contain any digit greater than $3$ nor more than $3$ consecutive, equal digits.

If some term had a digit greater than $3$, it would have had to come from more than $3$ (that is, $4$ or more) consecutive, equal digits in the previous term. But the first four of such digits (say that the digit is $k$) would had have to come from $k$ consecutive $k$s followed by $k$ consecutive $k$s, which makes no sense, because we would have written $2k$ and after $k$.

Example: if a term contains $41$ then the previous term contains $1111$ and then, the previous one contains "one $1$ and one $1$", that is, $11$, which should be transformed to $21$ and not to $1111$.

• It should be noted that $k$ consecutive $k$s followed by $k$ consecutive $k$s is not the only interpretation of $kkkk$, depending on the parity of the index of the first $k$. For example, $akkkkb$ could mean $a$ consecutive $k$s followed by $k$ consecutive $k$s followed by $k$ consecutive $b$s. – user134593 Aug 25 '15 at 13:02
• @stonebrakermatt Put differntly: By definition of the look-and-say process, the $2i$th and the $(2i+2)$th digit are different at any fixed stage. Any block of four or more consecutive digits covers two positions of even index, hence different digits. – Hagen von Eitzen Aug 25 '15 at 13:08

Prove it by contradiction. Suppose thre is some step at which a number larger than $3$ appears. Let step $i$ be the one such step. Obviously, $i\neq 1$ since the first step has only 1.

Then, in step $i$, you have the subsequence Ak in your sequence for some A>3, meaning that step $i-1$ had a subsequence

xkkkky


for some values x,y. Now, you have two options:

1. The step xkkkky is read as "x repetitions of k, then k repetitions of k, then k repetitions of y". This is not possible, as instead of x repetitions of k, then k repetitions of k, you would simply write x+k repetitions of k"

2. The step reads as k repetitions of k, then another k repetitions of k, which is again impossible.

Each number contains pairs of type $xy$ where x is the number of corresponding consecutive y digit in the previous number. Consider the first number in sequence containing digit 4. Then the previous number must have 4 equal consecutive digits, let's say $dddd$.Now, $dddd$ cannot represents two pair of d repetition of d, therefore we must have something like k repetitions of d and d repetitions of d which also is not possible.