Today I Learned: the Thue-Morse sequence

I did the 15 km run for the kids last Sunday. It took me about 80 minutes to run the whole thing, and I beat my frenemy Han Liang Gan by 1 second. So, yea, pretty much the best run ever! =)

Orrite - it's maths time! Now, let's say that you're only allowed to write "A"s and "B"s, no spaces and no punctuation. What's the length of a longest square-free word that you can write? That is: what is a longest word that you can write before you have the same sequence of letters appearing twice consecutively, such as in AA or ABAB?

Okay, orrite, orrite - that was a pretty silly question. The answer is obviously 3 (either ABA or BAB).

But what if I'd asked for the longest cube-free word instead? That is: subsequences like ABAABAABA are forbidden since it's ABA repeated thrice.

Well, the answer is \(\infty\).

And in fact, it's actually surprisingly easy to construct an example of an infinitely long cube-free word:

The Thue-Morse sequence.

1. Start with an initial sequence just given by: A.
2. Stick a copy of the sequence that you've got at the end, but with "A"s and "B"s switched.
3. Go back to step 2.

Specifically, applying those instructions, we grow the following sequence:
A\(\rightarrow\)AB\(\rightarrow\)ABBA\(\rightarrow\)ABBABAAB\(\rightarrow\)ABBABAABBAABABBA\(\rightarrow\)\(\ldots\)

So how can we prove this? Well, I'm certainly not going to write up a proof right now - I'm off to Easter camp tomorrow and there's much packing and stuff to be done! =)