\problemdata
{strong induction}
{strings}

\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 = x v^R$.
\end{itemize}
\nopagebreak Prove that $(vw)^R = w^Rv^R$

\begin{solution}
\begin{proof}
\newline
by \textbf{strong induction} on the length, $n$, of $vw$.
\newline
\begin{tabbing}
XXti\=XXti\=XXti\=XXXXXXXXXXXXXX\=    \kill
\textbf{Base:} vw is of length 0.  Here, $vw = \lambda$ which means $v = w = \lambda$, so $(vw)^R = (\lambda)^R = \lambda = \lambda \lambda = w^Rv^R$.\\
\textbf{Inductive step: Assume:} $P(n): \forall i \in \naturals \; (0 \leq i \leq n) Q(i)$ holds (Inductive Hypothesis).\\
\> That is, $Q(i): ``(vw)^R = w^Rv^R \; for \; an \; arbitrary \; string \; vw \; of \; length \; i''$ \\
We now \textbf{prove} $P(n+1)$ holds.\\
Let $vw$ be an arbitrary string of length $n+1$.\\
\> \textbf{Case 1:} $w$ is of length exactly 0\\
\> \> then $(vw)^R = (v)^R = \lambda v^R = \lambda^R v^R = w^Rv^R$.\\
\> \textbf{Case 2:} $w$ is of length exactly 1\\
\> \> then $v \in \Sigma^*$ and $w \in \Sigma$ ($w$ is a single symbol)\\
\> \> $(vw)^R = wv^R$ by the definition of \emph{reversal}\\
\> \> then $w = w^R$ as $w^R = (\lambda w)^R = w \lambda^R = w$ by definition of \emph{reversal} for a single symbol\\
\> \> so $(vw)^R = w^Rv^R$\\
\> \textbf{Case 3:} $w$ is of length $> 1$ and $\leq n$\\
\> \> then $v \in \Sigma^*$ and has length $\geq 1$\\
\> \> $x \in \Sigma^*$ and $y \in \Sigma$ for some $x$, $y$, s.t. $w = xy$\\
\> \> thus, $vw = vxy$ for some $y \in \Sigma$\\
\> \> let $t = vx$  then, $t \in \Sigma^*$ and is of length $n$ by the definition of \emph{length}\\
\> \> then, $vw = ty$ so that $(vw)^R = (ty)^R = yt^R$ by the definition of \emph{reversal}\\
\> \> we know that $t^R = (vx)^R = x^Rv^R$ by the Inductive Hypothesis at n.\\
\> \> so, $(vw)^R = yx^Rv^R = y^Rx^Rv^R$ by substitution and $y = y^R$ for a single symbol.\\
\> \> we have that $y^Rx^R = (xy)^R = w^R$ by the Inductive Hypothesis at some $i \leq n$\\
\> \> thus, $(vw)^R = w^Rv^R$.\\
\> \textbf{Case 4:} $w$ is of length $n+1$\\
\> \> we have in this case that $v = \lambda$\\
\> \> thus, $(vw)^R = (\lambda w)^R = (w)^R = w^R\lambda = w^R\lambda^R = w^Rv^R$\\
$QED$\\
\end{tabbing}
\end{proof}
}
\end{problem}
