15. (Morse-Thue Sequence) Starting from 0, each time append the "complement sequence" of the current sequence:
(1) Let the digits of the final sequence be denoted as . Prove that: , ;
(2) Prove that: , where is the largest power of 2 not exceeding . Find ;
(3) Prove that the sequence is not periodic;
(4) Represent non-negative integers in binary in increasing order: . Now take the sum of the digits of each number modulo 2, resulting in a sequence. Prove that this sequence is the Morse-Thue sequence.
Solution
15. (1) Starting from the digit 0, repeatedly applying the transformation , we get , thus we obtain the Morse-Thue sequence in another way, where represents the first digits of the sequence. Applying the transformation to the entire sequence leaves it unchanged, which makes (1) almost obviously true, and (2) is the same.
(3) We notice that the adjacent terms and are always different. If the sequence eventually becomes periodic, and let be an element within a period of the sequence, then must not be a multiple of the period (otherwise , a contradiction). Similarly, it can be proven that are also not multiples of the period, but this is impossible.
(4) This conclusion is correct because the -bit 0-1 sequence is formed by adding a 1 and possibly some 0s in front of the binary numbers up to bits.