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!

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Michaël Cadilhac Jan 14 '11 at 22:15
  • $\begingroup$ It's very easy to prove by induction. $\endgroup$ – Yuval Filmus Jan 14 '11 at 23:08
  • $\begingroup$ It is indeed, thank you. $\endgroup$ – Michaël Cadilhac Jan 15 '11 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.