\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: w/new solution spring01 ps3, spring00 ps3
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 an arbitrary $t\in\Sigma^*$, 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.

{\bf Alternative 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}
=======
the second property of reversal.
}
%END   Joe's problems

%BEGIN Ray's problems
<<<<<<< StructuralInduction.tex
%END   Ray's problems

%BEGIN Ivan's problems
%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  


\problem \textbf{Structural Induction}

The set $SSS$ of ``super-symmetric strings'' is defined as follows:
\begin{enumerate}
\item
The length one strings consisting of individual letters of the
alphabet, $a$, $b$, $c$, $d$, $\ldots$, $z$, are in $SSS$. 
\item
If $\alpha$ and $\alpha'$ are two strings in $SSS$ then the string
$\alpha \alpha' \alpha$ is in $SSS$.
\item
$SSS$ contains nothing else.
\end{enumerate}
\bparts
\ppart
Which of the following are super-symmetric strings?\\
i.  a\\     
ii.  aaaba\\   
iii.  abcbacabcba\\
iv. $\lambda$, the empty string\\
v. abaabcbaaba\\

\solution{
\medskip
\textbf{Solutions:}\\
i. Yes.  This is stated in part 1 of the definition.\\
ii. No.  This string is not of the form $\alpha \alpha' \alpha$.\\
iii. Yes.  Formally, consider $\alpha'=aca$, $\alpha=bcb$.  Then we have
a string of the form $a \alpha \alpha' \alpha a$, which is in $SSS$
by parts 1 and 2 of the definition.\\
iv.  No.  By part 3 of the definition\\
v. Yes. Similar reasoning to part iii shows that the string $bcb$ is in the 
middle of the super-symmetric\\ 
string, with the string $a$ wrapped around it, and with the string
$aba$ wrapped around that.

}

\ppart
Prove by structural induction that in any super-symmetric string $\alpha$, 
exactly one letter appears an odd number of times.\\

%%%
%Fix this either to be more complete, or to use Structural Induction.
%Find out what structural induction is, too.
%%%

\solution{
\medskip
\textbf{Solution:}\\
\textbf{Proof:} Define $P(e)$: String $e$ has exactly one letter which appears an odd number of times.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall e \in SSS \ P(e)$.\\
1. (Base) $P(a)$\>\>\>\>The string $a$ has exactly one letter which appears an odd number of times.\\
2. (Base) $P(b)$\>\>\>\>Same for the string $b$\\
$\vdots$\\
26. (Base) $P(z)$\>\>\>\> Still has exactly one letter which appears once.\\
27. (Inductive Step) $\forall e, e' \in SSS \ P(e)\wedge P(e') \longrightarrow P(ee'e)$ \\
\>1. Fix $e,e' \in SSS$.\\
\>2. Assume $P(e) \wedge P(e')$.  That is, each of $e$ and $e'$ has exactly one letter which\\
\>\>appears and odd number of times.\\
\>3. By the inductive hypothesis, both $e$ and $e'$ have exactly one letter which appears an odd\\
\>\> number of times.  When we form the string $ee'e$, the letters in $e$ all get repeated, \\
\>\> and thus they all appear an even number of times.  By the IH, there is one letter in $e'$\\
\>\> which appears an odd number of times in $e'$.  Now, even if this letter is also present in\\
\>\>$e$, it will still appear an odd number of times in $ee'e$ (since
the sum of an odd number \\
\>\>and an even number is odd).  Therefore, we
have shown $P(ee'e)$.\\ 
\>4. QED.\\
\end{tabbing}
}

\eparts        
%%%%%%%%%%%%%%%%%%%%%%%%%END  Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems

%Fall 99
%%%%%%%%%%%%%%%%%%%%%%%%%%
% Pset 2 problem 9
\problem \textbf{Structural Induction}

Suppose we start with a sequence of fully parenthesized arithmetic or
Scheme expressions, and then erase all the alphanumeric characters other
than parentheses.  The result is a string of parentheses which ``match
up''.

For example, erasing non-parenthesis characters from the expression
\texttt{(if (or x y) u v)} leaves the string \texttt{(())}.  Similarly,
erasing non-parentheses from the sequence of three arithmetic expressions
\[
\texttt{(x * x), (y + (3 * (z - 9))), ((x + y) * (u + w))}
\]
leaves the string
\[
\texttt{()((()))(()())}.
\]
On the other hand, even though the string \texttt{())(()} has an equal
number of left and right parentheses, it cannot be obtained by erasing in
this way---because the two middle parentheses don't match up.  Also, no
string of parentheses which begins with a right parenthesis or ends with a
left parenthesis can match up.

We can give an inductive definition of the set, SMU, of ``Strings which
Match Up'', as follows:

\begin{itemize}
\item The empty string (consisting of no parentheses) is an SMU.

\item If $s$ and $t$ are SMU's, then the string $\texttt{(}s\texttt{)}t$
is an SMU.  That is, the new string starts with a left parenthesis which
is followed by the parenthesis characters in the string $s$, followed by a
right parenthesis, followed by the parenthesis characters in the string
$t$.

\end{itemize}


There is a simple test to determine whether a string of parentheses is an
SMU: starting with zero, read the string from left to right adding one for
each left parenthesis and -1 for each right parenthesis.  A string
\emph{counts well} when the count never goes negative and is back to zero
by the end of the string.  Let CW be the set of strings of parentheses
which Count Well.

\bparts
\ppart Prove that CW contains SMU.

\solution{We prove by induction on the definition of SMU (that is,
structural induction) that every element of SMU counts well, so SMU is
contained in CW.  The induction hypothesis is
\[
P(s) ::\equiv s \in \mbox{CW}.
\]
\begin{proof}

{\bf Base Case}: $P(\mbox{empty string})$ holds since the count of the
empty string ends when it starts at zero.

{\bf Inductive Step:} Assume $P(s)$ and $P(t)$ are true.  We need to show
that $P(\texttt{(}s\texttt{)}t)$ is true.

The count values for $\texttt{(}s\texttt{)}t$ start with 0.  Reading the
initial left parenthesis yields 1 as the next count value.  This 1 serves
as the start of a series of count values exactly equal to the count values
of $s$, with each value incremented by one.  Since $s \in \mbox{CW}$ by
hypothesis, these incremented count values begin with 1, always stay
positive, and end with 1.  The right parenthesis immediately after $s$
reduces the ending count to 0.  This 0 serves as the start of the
remaining count values which are exactly the count values of $t$.  Since
$t \in \mbox{CW}$, these remaining values never go negative and end at 0.
Hence the entire sequence of count values for $\texttt{(}s\texttt{)}t$
starts with 0, never goes negative, and ends with 0, which proves that
$\texttt{(}s\texttt{)}t \in \mbox{CW}$.
\end{proof}}

\ppart Conversely, prove that SMU contains CW.

\solution{We show that every string $r\in \mbox{CW}$ is an SMU by
strong induction on the length of $r$.  The induction hypothesis is
\[Q(n) ::\equiv \forall r \in \mbox{CW}(\mbox{if $r$ is length $n$, then
$r \in \mbox{SMU}$}).\]
\begin{proof}

{\bf Base Case} $n = 0$: In this case there is only one string of length
$n$, namely the empty string, which is in SMU by definition, proving
$Q(0)$.

{\bf Inductive Step:} Assume that $Q(k)$ is true for all $k\leq n$, we
need to prove that $Q(n+1)$ is also true.

So suppose $r$ is a length $n+1$ string that counts well.  We must prove
that $r \in \mbox{SMU}$.

Now since $r$ counts well, it must start with a left parenthesis (or else
the count would immediately go negative).  Likewise, since the count for
$r$ returns to the value 0 by the end, $r$ must end with right
parenthesis.  So there must be a \emph{first} right parenthesis in $r$
after which the count returns to 0.  Let $s$ be the substring of $r$
between the initial left parenthesis and this right parenthesis.  So
\[
r = \texttt{(}s\texttt{)}t
\]
for some string $t$.

Since counts only change by one as each parenthesis character is read, and
the count for $r$ \emph{first} returns to 0 after the right parenthesis
following $s$, the count during $s$ must start and end with 1 and must
stay \emph{positive} in between.  But this implies that a count for $s$
alone, which would start with 0, would also end with 0 and stay
\emph{nonnegative} in between.  That is, $s$ by itself counts well.  Since
the length of $s \in \mbox{CW}$ is less than the length of $r$, we have by
strong induction that $s \in \mbox{SMU}$.

Further, we know the count for $r$ returns to 0 after the right
parenthesis following $s$, and since $r \in \mbox{CW}$, the count ends
with 0 again and stays nonnegative in between.  But this implies that $t$
counts well, and since the length of $t$ is less than the length of $r$,
we have by strong induction that $t \in \mbox{SMU}$.  Now by the second
case in the definition of SMU, we conclude $\texttt{(}s\texttt{)}t$,
namely $r$, is in SMU.
\end{proof}}

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% wellordering - recursive sets
% pset 2, #8
\problem \textbf{Well-ordering Principle}

Let $a,b$ be integers, and assume at least one of $a$ and $b$ is nonzero.
Define a set $L_{a,b} \subseteq \integers$ inductively as follows:
\begin{itemize}
\item $a,b \in L_{a,b}$.
\item If $c,d \in L_{a,b}$, then $c+d \in L_{a,b}$.
\item If $c \in L_{a,b}$, then $cn \in L_{a,b}$ for all $n\in\integers$.
\end{itemize}
Do the following parts without appeal to the result of~\ref{ax+by:induct}.

\bparts

\ppart %(a)

Show by induction on the definition of $L_{a,b}$ that any common
divisor of $a$ and $b$ also divides every member of $L_{a,b}$.

\solution{
\begin{proof}
The induction hypothesis $P(c)$ is ``any common divisor of $a$ and $b$
also divides $c$.''

\emph{Base case}: $P(a)$ is immediate, since any common divisor of $a$ and
$b$ certainly divides $a$.  Likewise for $P(b)$.

\emph{($c+d$) case}: Assuming $P(c)$ and $P(d)$, we must prove
$P(c+d)$.  So suppose $e$ is a common divisor of $a$ and $b$.  Then $e
\mid c$ by hypothesis $P(c)$ and $e \mid d$ by hypothesis $P(d)$.  That
is, $c = ef$ and $d=eg$ for some $f,g \in \integers$.  Hence $c+d = ef+eg=
e(f+g)$ so $e \mid c+d$, namely $P(c+d)$.

\emph{($cn$) case}: Assuming $P(c)$ and $n \in \integers$, we must
prove $P(cn)$.  So suppose $e$ is a common divisor of $a$ and $b$.  Then
$e \mid c$ by hypothesis.  Hence $e \mid cn$, namely $P(cn)$.
\end{proof}
}

\ppart %(b)

Show that if $c,d \in L_{a,b}$ and $c= dq + r$ for some $q,r \in
\integers$, then $r \in L_{a,b}$.

\solution{Since $d \in L_{a,b}$, we have $d(-q) \in L_{a,b}$ by
the ($nc$) case.  Then since $c \in L_{a,b}$, we have $c + d(-q) = r \in
L_{a,b}$ by ($c+d$) case.}

\ppart %(c)

Show that there is a positive integer $g \in L_{a,b}$ which divides every
member of $L_{a,b}$.  \hint Show that there is a least positive member of
$L_{a,b}$.

\solution{At least one of the integers $a, -a, b, -b \in L_{a,b}$ must be
positive.  Hence by the well-ordering principle, there is a least positive
integer $g \in L_{a,b}$.

Suppose $c \in L_{a,b}$.  We must show that $g \mid c$.

We prove this by contradiction: if $g$ does not divide $c$, then the
remainder of $c$ divided by $g$ is a positive number smaller than $g$,
which by the previous part is in $L_{a,b}$, contradicting the fact that
$g$ is the smallest such integer.
}

\ppart %(d)

Conclude that $g = \gcd(a,b)$.

\solution{By part (a), any common divisor of $a$ and $b$ divides $g$.
Also, since $a,b \in L_{a,b}$, part (c) implies $g$ is a common divisor of
$a$ and $b$, which implies $g$ is the greatest common divisor.}

\ppart Conclude that $\gcd(a,b) = ax+by$ for some $x,y \in \integers$.

\solution{It's easy to prove by structural induction that every element of
$L_{a,b}$ is equal to $ax + by$ for some $x,y \in \integers$, so $g$ is
of this form.}

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%
%END   Tina's problems


\end{problems}

\end{document}



