For the purposes of this question, I'm subscribing to the following definition of the Thue-Morse sequence:
Let $T_0 = 0$, and $C$ be the bitwise complement function. $T_n = T_{n - 1} + C(T_{n - 1})$.
I'm working on an exercise that proves that when the Lindenmeyer algorithm is applied to a Thue-Morse sequence $T_n$, it produces the next string $T_{n + 1}$ in the Thue-Morse sequence. It is supposed to be done by induction. Below is the actual question and my proof:
(b) 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}$.
Base Case: Let $n_{0}=0$. $T_{n_{0}}=T_{0}=0$. If we replace the $0$ with $01,$ we end up with $01,$ which equals $T_{1}$.
Induction Hypothesis: Assume that for $n \geq n_{0},$ the proposition holds.
Induction Step: Prove that for $n+1$, submitting $T_{n+1}$ to the aforementioned algorithm yields $T_{n+2}$. Let $F$ be the aforementioned algorithm that operates on bitwise strings, and let $C$ be the complement function, that is, bitwise negation. Note that $F(C(0))=$ $C(F(0))=10,$ and $F(C(1))=C(F(1))=01,$ and more generally, $F(C(x))=C(F(x))$ where $x$ is a bitwise string. Therefore we need to prove:
\begin{aligned}
T_{n+2} &=F\left(T_{n+1}\right) \\
T_{n+1}+C\left(T_{n+1}\right) &=F\left(T_{n+1}\right) \\
F\left(T_{n}\right)+C\left(F\left(T_{n}\right)\right) &=F\left(T_{n+1}\right) \\
F\left(T_{n}\right)+F\left(C\left(T_{n}\right)\right) &=F\left(T_{n+1}\right) \\
F\left(T_{n}+C\left(T_{n}\right)\right) &=F\left(T_{n+1}\right) \\
F\left(T_{n}+C\left(T_{n}\right)\right) &=F\left(T_{n}+C\left(T_{n}\right)\right)
\end{aligned}
I think the proof is sound, but I just can't tell if I'm making correct use of my Induction Hypothesis. It seems OK, but something feels a little off, so I'm looking for some constructive criticism on what I've got. Any advice or direction would be appreciated!
There are a few steps that make me take a second look to figure out why.
We have $F(A+B)=F(A)+F(B)$ where $+$ denots concatenation because $F$ is a bitwise replacement of constant length.
Similarly, we have $C(A+B)=C(A)+C(B)$.
For $F(C(x))=C(F(x))$, I use another induction to see it.
Suppose $x = \sum_{i=1}^{n}x_i$ denotes the concatenation of substring from lef to the right.
\begin{align} F(C(x)) &= F\left( C\left( \sum_{i=1}^n x_i\right)\right) \\ &= F\left( \sum_{i=1}^n C\left( x_i\right)\right) \\ &=F\left( \sum_{i=1}^{n-1} C\left( x_i\right) + C(x_n)\right) \\ &=F\left( \sum_{i=1}^{n-1} C\left( x_i\right)\right) + F(C(x_n)) \\ &=C\left( \sum_{i=1}^{n-1} F\left( x_i\right)\right) + C(F(x_n)) \\ &= C(F(x)) \end{align}
We want to show that $$T_{n+2}=F(T_{n+1})$$
Proof: \begin{align} F(T_{n+1}) &= F(T_n + C(T_n)), \text{ by definition} \\ &= F(T_n) + F(C(T_n)) , \text{ since } F(A+B)=F(A)+F(B)\\ &= T_{n+1} + C(F(T_n)), \text{ by induction hypothesis and since } F(C(x))=C(F(x))\\ &= T_{n+1} + C(T_{n+1}), \text{ by induction hypothesis}\\ &= T_{n+2}, \text{by definition} \end{align}