Prove the following by using mathematical induction

Question

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove

$$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$

where $$ w^R$$ and $$\operatorname{comp}(w) $$ are reverse of $w$ and complement of $w$ that can be obtained by changing all $a$’s to $b$’s and all $b$’s to $a$’s in w. For example, if $w$ is $abaaabb$ , $\operatorname{comp}(w)$ is $babbbaa$ and $$w^R$$ is $bbaaaba$.

Answer 1

Let us prove the result by induction on the length $|w|$ of $w$. If $|w| = 0$, then $w$ is the empty word and the result is trivially true. Suppose that the result holds for all words of length $\leqslant n$ and let $w$ be a word of length $n + 1$. Without loss of generality, we may assume that the last letter of $w$ is an $a$. Thus $w = va$ for some word $v$ such that $|v| = n$. Then $w^R = av^R$ and by the induction hypothesis applied to $v$, we have $$ (\operatorname{comp}(v))^R = \operatorname{comp}(v^R). $$ Now, observing that $\operatorname{comp}(va) = \operatorname{comp}(v)b$ and $\operatorname{comp}(av^R) = b\operatorname{comp}(v^R)$, we get \begin{align} (\operatorname{comp}(w))^R &= ( \operatorname{comp}(va))^R = ( \operatorname{comp}(v)b)^R = b(\operatorname{comp}(v))^R\\ &= b\operatorname{comp}(v^R) = \operatorname{comp}(av^R) = \operatorname{comp}(w^R) \end{align} which concludes the induction step.

Answer 2

This fact is absolutely obvious, and the intended induction proof is apt to make it less believable. Hear this:

We are given a finite $\{a,b\}$-string. Interchanging all $a$s and $b$s, and then reversing it produces the same result as first reversing it and then interchanging all $a$s and $b$s.