the Thue-Morse sequence

A non-periodic sequence of 0s and 1s, with no 3 consecutive identical blocks of any length.
Ways of constructing it:

1. For each nonnegative integer n, let \alpha_n=0 if the number of 1‘s in the binary representation of n is even, and \alpha_n=1 if this number is odd. (Conway calls these evil and odious numbers, respectively)

2. At each step, append a copy of the sequence so far, with 0s and 1s interchanged.
i.e. Start with 0. Append 1 to that. \to 01.
Append 10 to that \to 0110.
Append 1001 to that \to 01101001.
Append 10010110 to that \to 0110100110010110. etc.

3. Start with 0. Apply 0\to 01 and 1\to 10.

If n is \overline{ab\dots c} in binary notation, then 2n=\overline{ab\dots c0}, with the same number of binary 1s as n, and 2n+1=\overline{ab\dots c1}, containing one more 1. So:

    \[\alpha_{2n}=\alpha_n \quad \text{ and } \quad \alpha_{2n+1}=1-\alpha_{2n} \quad \text{ for } n=1,2,\dots\]

i.e. the sequence is determined by its odd-numbered terms, and each of those is different to the previous (even) term.

Interpreted as a binary fraction, 0.0110100110010110\dots=0.4124\dots, the Morse-Thue constant, it’s intimately related to period-doubling bifurcation and the Mandelbrot set.

The Tarry-Escott problem

Can the set \{0,1,2,3,\dots,2^{k+1}-1\} be partitioned into two disjoint subsets \{x_1,x_2,\dots,x_{2^k}\} and \{y_1,y_2,\dots,y_{2^k} \} such that

    \[ \sum_{i=1}^{2^k} x_i^a=\sum_{i=1}^{2^k} y_i^a \quad \text{for all a=0,1,2,\dots,k?}\]

The Thue-Morse sequence determines such a partitioning.
Let X_k be the set of all n \in \{ 0,1,2,\dots,2^{k+1}-1\} with \alpha_n=0,
and Y_k be the set of n \in \{ 0,1,2,\dots,2^{k+1}-1\} with \alpha_n=1.

e.g. Take k=3.
The first 16 terms of the sequence are 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0, so
X_n = \{0,3,5,6,9,10,12, 15\}, and Y_n = \{1,2,4,7,8,11,13, 14\}.
And sure enough…

This works for any polynomial of degree \les k.
If f(x) if a polynomial of degree not exceeding k, then

    \[ \sum_{n \in X_k} f(n)= \sum_{n \in Y_k} f(n).\]

Further reading
Savchev, Andreescu – Mathematical Miniatures (2002)
Manfred Schroeder – Fractals, Chaos, Power Laws