
\problemdata     
{S01-PS3-7}           
{induction, proofs}              
{}              
{S01-PS3} 		
{S01 Karger}        	



\begin{problem}  Read the recursive definition of strings over an alphabet
$\Sigma$ in Rosen 3.3, example 10.  Define the {\em reversal} of a
  string $w$, written $w^R$, as follows:
\begin{itemize}
\item $\lambda^R = \lambda$
\item if $w=vx$ where $v \in \Sigma^*$ and $x \in \Sigma$, then $w^R \
=  xv^R$
\end{itemize}
Prove that for any $s,t \in \Sigma^*$, $(st)^R = t^Rs^R$

\solution{
We use structural induction. Specifically, the induction is on $t$ in
the assertion.
For the base case, we must show $\forall s\in\Sigma^*$,
$(s\lambda )^R=\lambda^Rs^R$---but this is clear since the left side
is $s^R$ and the right side is $s^R$ (because $\lambda$ is the empty
string).

Now we must show that if for some $t$, we have that $\forall s\in\Sigma^*$,
$(st)^R=t^Rs^R$, then $\forall s\in\Sigma^*,x\in\Sigma$,
$(s(tx))^R=(tx)^Rs^R$. We have $(s(tx))^R=(st(x))^R=x(st)^R$, the last
equality by the second property of reversal. But $x(st)^R=xt^Rs^R$ by
the structural inductive assumption and $xt^Rs^R=(tx)^Rs^R$ again by
the second property of reversal.
}
\end{problem}