3
$\begingroup$

From here.

This particular item deals with excluding strings that have a consecutive repeated sequence. That is, ab*b*a and abcab*ab*c both have doubles whereas abcabacba doesn't. When working in base $2$, the number of sequences is easily seen to be finite.

0
1

00
01
10
11

010
011
100
101

0100
0101
1010
1011

They also mention that base $10$ is known to be infinite. In addition, base $3$ seems to be infinite, as evidenced by this exponentially-growing pattern.

My question is: how can you prove that the number of repetition-free sequences is infinite for base $b \ge 3$?

  • 0
    @Arturo: Ah, neat! Thanks!2012-02-14

2 Answers 2

8

This paper gives a very nice elementary presentation of the Thue-Morse sequence and in particular of the result that there is an infinite square-free sequence over an alphabet of three letters.

7

Thue proved that any alphabet on three or more letters contains an infinite squarefree word. An example due to Leech (A problem on strings of beads, Math. Gazette 41 (1957) 277– 278):

On the alphabet that contains $a$, $b$, and $c$, define $w_1$ to be a word beginning with $a$ (say, $w_1=a$).

Given $w_n$, define $w_{n+1}$ by replacing each occurrence of $a$ in $w_n$ by $abcbacbcabcba$; every occurrence of $b$ in $w_n$ by $bcacbacabcacb$; and every occurrence of $c$ by $cabacbabcabac$.

Then $w_n$ converges to an infinite squarefree word, which begins $abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb\ldots$