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?

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$.
