0

I have this question:

Prove by induction on strings that for any binary string $w$, $(oc(w))^R = oc(w^R)$.

note:

  • if $w$ is a string in $\{1,0\}^*$, the one's complement of $w$, $oc(w)$ is the unique string, of the same length as $w$, that has a zero wherever $w$ has a one and vice versa. So for example, $oc(101) = 010$.

  • the string to the power of $R$ is saying that string reversed. So $w^R$ is the reversal of the string $w$.

I don't know how to start an induction and where to go in the case of strings.

Any help is useful. Thank you.

mrp
  • 5,086
john
  • 11

1 Answers1

1

Start your induction with the empty string, which I’ll call $\epsilon$ (you may use $\lambda$ for this): prove that $\big(\mbox{oc}(\epsilon)\big)^R=\mbox{oc}(\epsilon^R)$.

For the induction step note that every non-empty string in $\{0,1\}^*$ is of the form $w0$ or $w1$ for some $s\in\{0,1\}^*$. Assuming as your induction hypothesis that $\big(\mbox{oc}(w)\big)^R=\mbox{oc}(w^R)$, prove that $\big(\mbox{oc}(w0)\big)^R=\mbox{oc}\big((w0)^R\big)$ and a similar result for $w1$.

I’ve case this as a structural induction, but you could also do it as an ordinary induction on the length of the string.

Brian M. Scott
  • 616,228