Thue-Morse sequence

In mathematics and its applications, the Thue-Morse sequence, or Prouhet-Thue-Morse sequence, is a certain binary sequence whose initial segments alternate (in a certain sense).

Definition

There are several equivalent ways of defining the Thue-Morse sequence.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Recurrence relation

The Thue-Morse sequence is the sequence t_n satisfying t_0 = 0 and

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:t_{2n} = t_n

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:t_{2n+1} = 1-t_n

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

for all positive integers n.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Characterization using bitwise negation

The Thue-Morse sequence in the form given above, as a sequence of bits, can be defined recursively using the operation of bitwise negation.

Related Topics:
Bit - Recursive - Bitwise negation

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

So, the first element is 0.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Then once the first 2n elements have been specified, forming a string s, then the next 2n elements must form the bitwise negation of s.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Now we have defined the first 2n+1 elements, and we recurse.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Spelling out the first few steps in detail:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• We start with 0.
• The bitwise negation of 0 is 1.
• Combining these, the first 2 elements are 01.
• The bitwise negation of 01 is 10.
• Combining these, the first 4 elements are 0110.
• The bitwise negation of 0110 is 1001.
• Combining these, the first 8 elements are 01101001.
• And so on.

Infinite product

The sequence can also be defined by:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: prod_{i=0}^{infty} (1 - x^{2^{i}}) = sum_{j=0}^{infty} (-1)^{t_j} x^{j} mbox{,} !

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where tj is the jth element if we start at j = 0.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~