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!