I am currently going through a discrete math textbook and came across this problem. I couldn't find the solution manual to the book so I don't know if my version of the answer is right or not. I'd love to get some insight into this.
NOTE: For anyone that might not know what the Thue–Morse sequence or Prouhet–Thue–Morse sequence or parity sequence is, it is the binary sequence obtained by starting with $0$ and successively appending the Boolean complement of the sequence obtained thus far.
$$ T_0 = 0\\ T_1 = 01\\ T_2 = 0110\\ \vdots $$
Prove the following about the Thue-Morse sequence:
For every $n \ge 1$, $T_{2n}$ is a palindrome; that is, a string that reads the same in both directions.
For every $n$, if $0$ is replaced by $01$ and $1$ is replaced by $10$ simultaneously everywhere in $T_n$, the result is $T_{n+1}$.
Answer:
Base case: for $n = 1$, $T_{2 \cdot 1} = 0110 \implies T_2$ is a palindrome.
Inductive Hypothesis: Assume that for some $n > 1$, $T_{2n}$ is a palindrome.
Inductive step:
We need to prove $T_{2n+2}$ is also a palindrome.
Every iteration of the Thue-Morse sequence either is of the form $01 \dots 10$ or $01 \dots 01$, therefore assume $T_{2n}$ is of the form $01 \dots 10$.
$T_{2n+1}$ is $T_{2n}$ appended with the complement of $T_{2n}$:
$T_{2n+1} = 01 \dots 1010 \dots 01 \implies$ not a palindrome. (i)
$T_{2n+2}$ is $T_{2n+1}$ appended with the complement of $T_{2n+1}$.
From (i), $T_{2n+2} = 01 \dots 1010 \dots 0110 \dots 0101 \dots 10 \implies$ palindrome.
Conclusion: Every even iteration of the Thue sequence is a palindrome, i.e., for every even nonnegative $n$, $T_{2n}$ is a palindrome.
Base case: for $n = 0$, $T_0 = 0$. Applying the process from the statement gives $T_{0+1} = 01$.
Inductive hypothesis: Assume that for some $n > 0$, $T_n$ after applying the process from the statement gives $T_{n+1}$.
Inductive step:
We need to prove $T_{n+1}$ becomes $T_{n+2}$ when the statement is applied.
We know that the Thue-Morse sequence grows by a factor of $2^n$ and that every even iteration of it is of the form $01 \dots 10$ and every odd iteration of it is of the form $01 \dots 01$.
Therefore, if $n+1$ is odd, $T_{n+2}$ has to be a palindrome and twice the size of $T_{n+1}$ and if $n+1$ is even, it wouldn't be a palindrome but it should still be twice the size of $T_{n+1}$.
Let's say $n+1$ is odd, then if every $0$ in it becomes $01$ and every $1$ becomes $10$, it gives (written as $\to$): $T_{n+1} = 01......01 \to 0110 \dots 0110$. The term it gives is twice the size of $T_{n+1}$ and is a palindrome, therefore it must be $T_{n+2}$.
Conclusion: If in an iteration of the Thue sequence every $0$ is replaced with $01$ and every $1$ is replaced with $10$, you'd get the next iteration of the sequence.
The part I'm worried about is the "$\dots$" part. I'm worried whether it introduces some ambiguity in the proof and if it does, please tell me if there is any other way to do it. thanks for your time ;)
For those that don't know what the Thue-Morse sequence is, it is a sequence of $1$s and $0$s where $T_0=0$ and given $T_n$, $T_{n+1}$ is generated by taking the complement of all of the current bits and appending them to the end. The first few elements are $$T_0=0\\T_1=01\\T_2=0110\\\text{etc.}$$ For part 1:
Let's make some simplifying notation. For a sequence $T$, let $\bar T$ be the sequence of complements.
The base case is actually $T_0=T_{2(0)}=0$ which is a palindrome.
For the inductive step, suppose $T_{2k}$ is a palindrome. Then $$T_{2k+1}=T_{2k}\bar T_{2k}$$ and $$T_{2k+2}=T_{2k}\bar T_{2k}\bar T_{2k}T_{2k}$$ which is a palindrome. Since that is true for all $k$, $T_{2n}$ is a palindrome.
For part 2:
Let $R_n$ equal $T_n$ with $0$ replaced by $01$ and $1$ replaced by $10$.
$T_0=0$ and $R_0 = 01 = T_1$ so the claim is true for the base case.
For the inductive part, Suppose $R_k=T_{k+1}$. We know that, by definition, $$T_{k+1}=T_k\bar T_k$$ so the inductive hypothesis tells us when we replace $0$ by $01$ and $1$ by $10$, we get $$R_{k+1}=T_{k+1}\bar T_{k+1}=T_{k+2}=T_{(k+1)+1}$$
Therefore, $R_n=T_{n+1}$ for all $n$