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?

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:


*

*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"

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