4
$\begingroup$

I'm TA-ing an intro class on theoretical CS, and this week class only covered the simplest concepts, such as words and languages. I wanted to take this chance to present some combinatorics on words, and prove the cube-freeness of the Thue-Morse sequence (which I want to define as w_0 = a, w_i = w_{i-1}w'_{i-1} where w' is $w$ where the $a$'s and the $b$'s are exchanged).

Salomaa's old book (http://bit.ly/hHeWbK) gives the following program: (1) Show that neither $a^3$ nor $b^3$ can appear in $w_i$, (2) Show that neither $ababa$ nor $babab$ can appear in $w_i$, (3) show than any sequence $aa$ or $bb$ appears in $w_i$ on an even position, (4) Conclude by induction.

(1-3) are pretty easy by induction, but I can't think of a solution for (4). I came to the easy conclusion that no odd-length word can appear as a cube, but I've got nothing for the even part (and I really want to avoid going through the overlap-free proof, or use the definition of the sequence using the binary expansion of natural numbers).

Any idea?

Thanks!

1 Answers 1

3

Use the fact that the even positions in $w_i$ are $w_{i-1}$, and the odd positions are w'_{i-1} (if we start counting at zero).

Edit: let's prove this bit by induction.

Denote by $E(s)$ every second bit starting with $0$, and $O(s)$ every second bit starting with $1$.

Want to prove that for $i \geq 1$, $E(w_i) = w_{i-1}$ and O(w_i) = w'_{i-1}.

Base case $i=1$: Just check: $E(w_1) = E(ab) = a = w_0$ while O(w_1) = O(ab) = b = a' = w'_0.

Induction step: Assume that it holds for $i$, prove it for $i+1$: E(w_{i+1}) = E(w_i w'_i) = E(w_i) E(w'_i) = E(w_i) E(w_i)' = w_{i-1} w'_{i-1} = w_i, and similarly O(w_{i+1}) = O(w_i w'_i) = O(w_i) O(w'_i) = O(w_i) O(w_i)' = w'_{i-1} w_{i-1} = w_i'. In both steps, we used the fact that $|w_i|$ is even (this is true for $i \geq 1$).

  • 0
    It is indeed, thank you.2011-01-15