# Thue-Morse sequence cube-freeness proof from the Book

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!

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

• Thanks. I'm mainly wondering if this is needed, as showing $w_{i}[j] = w'_{i}[2j]$ (start counting at 1 :)) is too involved for a first course class. – Michaël Cadilhac Jan 14 '11 at 22:15
• It's very easy to prove by induction. – Yuval Filmus Jan 14 '11 at 23:08
• It is indeed, thank you. – Michaël Cadilhac Jan 15 '11 at 21:37