|
The Prouhet-Thue-Morse sequence is a binary sequence which begins as follows: $$ 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, \ldots $$
The $n$ th term is defined to be the number of $1$ s in the binary expansion of $n$ , modulo 2. That is, $t_n = 0$ if the number of $1$ s in the binary expansion of $n$ is even, and $t_n = 1$ if it is odd.
The sequence satisfies the following recurrence relation, with $t_0=0$ :
The Prouhet-Thue-Morse sequence is an automatic sequence. It has been shown to be cube-free (no three consecutive identical blocks) and overlap-free i.e no sub-block of the form $awawa$ , where $a \in \{0,1\}$ , when viewed as a word of infinite length over the binary alphabet $\{0,1\}$ .
The generating function $T(x)=\sum_{n=0}^{\infty} t_nx^n$ for the sequence satisfies the relation $$ T(x) = T(x^2)(1-x) + \frac{x}{1-x^2} $$
The Thue-Morse sequence was independently discovered by P. Prouhet, Axel Thue, and Marston Morse, and has since been rediscovered by many others.
|
