Démonstration par récurrence.

C'est vrai pour $n=6$. Soit $n>6$, supposons la propriété vérifiée pour $n$ et montrons la pour $n+1$. Si $n$ est pair, $u_n$ se termine par $222112$. Le chiffre précédent, s'il existe, n'est pas un $2$ (puisqu'on n'a pas 4 chiffres identiques consécutifs).

Donc $u_n$ se termine par un bloc de trois 2, puis un bloc de deux 1, puis un 2, et donc $u_{n+1}$ se termine par $322112$ ; $n+1$ étant impair, c'est précisément ce qu'on attendait.

Si $n$ est impair, $u_n$ se termine par $322112$. Peu importe si le chiffre précédent est un 3 ou non, seuls les trois derniers blocs nous intéressent, et $u_{n+1}$ se termine donc par $222112$ ; $n+1$ étant pair, c'est ce qu'on attendait.

1. Pour tout $n \ge 6$, $x_n$ est un suffixe de $u_n$.
2. Pour tout $n \ge 6$, $x_n$ est un suffixe de $x_{n+2}$.
3. Pour $n\ge11$, $\vert x_n\vert$ est impair et $\vert x_{n+2}\vert \ge \vert x_n\vert+2$.
4. Pour tout $n$, $\vert x_n\vert \ge n-2$.