0

The problem at hand:

Recall our recursive definition of the reversal of a string over $\Sigma$.

  • Base case: $\epsilon^R=\epsilon$
  • If $w \in \Sigma^*$ and $c \in \Sigma$, then $(wc)^R =cw^R$.

Use the definition above along with mathematical induction to prove the following: If $v,w$ are strings over $\Sigma$, then $(vw)^R= w^Rv^R$.

I'm honestly stumped and don't know where to begin. I've done mathematical induction on actual numbers but not on just variables like this problem. Any help is appreciated.

Andrés E. Caicedo
  • 79,201
Ervin Enriquez
  • 11

1 Answers1

0

You can prove it by induction on the structure of $w.$ The idea is to show that

  1. The equation holds for $w=\epsilon$.
  2. If the equation holds for $w'$ and $c$ is a character, then it holds for $w'c.$

Hopefully you can see how this implies it holds for any string $w$ by analogous reasoning to induction on $\mathbb N$.

(Alternatively as Lord Shark suggests in the comments, you can just think of it as ordinary induction on the length of $w.$ If $w=w'c,$ then $w'$ is a string shorter than $w.$)

The base case is easy. Then for the induction step we have $$(v w'c)^R = c(vw')^R=cw'^Rv^R=(w'c)^Rv^R$$ where the second equality uses the induction hypothesis and the other two use the definition of $R.$

spaceisdarkgreen
  • 58,508