Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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