\documentclass[11pt, twoside]{article}
\input{macros-course}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\renewcommand{\implies}{\longrightarrow}
\showsolutionstrue
\begin{document}
\solset{2}{February 23, 2001}

%6782685711022254907  
\textbf{Be sure to indicate your TA's name clearly on the solutions
you turn in}.

\paragraph{Reading}
Velleman, \textit{How to Prove It}, Sections 3.4--3.7 and 6.1--6.4;
Rosen, \textit{Discrete Mathematics and Its Applications}, Sections
3.2--3.4. Some of the examples and problems in Velleman treat
\emph{relations}, a topic we have not studied yet. You can skip these
examples and problems for now.

\vspace{-.25in}

\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should
mention their names on top of the problem set. If you did not
collaborate with anyone, you should explicitly say so. As a reminder,
the write-up of your solutions should be entirely your own.

\paragraph{Self-study}
Velleman, \emph{How to Prove It}, Section 2.3; Rosen, \emph{Discrete
  Mathematics and Its Applications}, Sections 1.4--1.5.

The following exercises are \emph{optional;} do them if you think you
need the practice. The mini-quiz in tutorial on Friday will draw
(only) from these problems.
\begin{enumerate}
\item Exercises from Velleman: Section 1.4, exercises 1, 3, 8;
  Section 2.3, exercises 3, 6, 7.
\item Exercises from Rosen (answers in the back of the book): Section
  1.4, exercises 5, 7, 9, 13, 17, 23; Section 1.5, exercises 3, 7, 15,
  17, 19, 21.
\end{enumerate}


\medskip
\begin{problems} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% BASIC INDUCTION

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Problems are from Kavita's section:
\problem Use induction to prove that the following equation holds for all
$n \geq 2$.

\begin{eqnarray*}
\left(1 - \frac{1}{2}\right)
\left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right) & = &      \frac{1}{n}
\end{eqnarray*}

\bigskip

\solution{%
\textbf{Solution:}

\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
the above equation holds.  In the base case, $P(2)$ is true because
$(1 - \frac{1}{2}) = \frac{1}{2}$.  In the inductive step, for $n \geq
2$ assume $P(n)$ to prove $P(n+1)$ as follows.

\begin{eqnarray*}
\left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right) \left(1 - \frac{1}{n+1}\right)
        & = &   \frac{1}{n} \left(1 - \frac{1}{n+1}\right) \\
        & = &   \frac{1}{n} \cdot \frac{n}{n+1} \\
        & = &   \frac{1}{n+1}
\end{eqnarray*}

The first step uses the induction hypothesis, and the second and third
steps are simplifications.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
\end{proof} 
}


% Velleman 6.3.7b & 6.3.7c
\problem

An important tool in the analysis of algorithms is to estimate the
growth rate of complex mathematical functions using other, hopefully
simpler, functions. A function central to probability theory is the
\emph{factorial}, defined recursively as
\begin{displaymath}
  n! = \begin{cases}
    n \times (n-1)! & \mbox{if $n > 0$,} \\
    1 & \mbox{otherwise,}
  \end{cases}
\end{displaymath}
for all $n \in \naturals$. Your task in this problem is to prove that
the factorial is sandwiched between $2^{2n}$ and $2^{n^2}$ for large
enough~$n$. More precisely, prove by induction that
\begin{problemparts}
\ppart For all $n \in \naturals$ such that $n \geq 9$, $n! \geq
2^{2n}$.
\solution{%

  \paragraph{Solution}
  Let $P(n)$ be the statement ``$n! \geq 2^{2n}$''. $P(9)$~is true since
  $9! = 362880 \geq 2^{18} = 262144$. Now assume that $P(n)$~is true for
  some $n \geq 9$. Then,
  \begin{displaymath}
    2^{2(n+1)} = 4\cdot2^{2n} \leq 4 n! \leq (n+1) n! = (n+1)!
  \end{displaymath}
  where the first inequality follows from the induction hypothesis and
  the second follows since $n \geq 9$.}
\ppart For all $n \in \naturals$, $n! \leq 2^{n^2}$.
\solution{

  \paragraph{Solution}
  Let $P(n)$ be the statement ``$n! \leq 2^{n^2}$''. $P(0)$~is true since
  \begin{displaymath}
    0! = 1 \leq 2^{0^2} = 2^{0} = 1.
  \end{displaymath}
  Now assume that $P(n)$ is true. Then
  \begin{displaymath}
    2^{(n+1)^2} = 2^{n^2+2n+1} \geq 2^{2n+1}n!.
  \end{displaymath}
  where the inequality follows by the induction hypothesis. In order
  to complete the proof, we must prove that $2^{2n+1} \geq n+1$ for
  all $n \in \naturals$. We do this by induction.
  
  Let $Q(n)$ be the statement ``$2^{2n+1} \geq n+1$''. $Q(0)$~is true
  since $2^{2\times0+1} = 2^1 = 2 \geq 0+1 = 1$. Now assume that
  $Q(n)$~is true for some $n \in \naturals$. Then
  \begin{displaymath}
    2^{2(n+1) + 1} = 2^{2n + 1 + 2} = 4 \cdot 2^{2n+1} \geq 4(n+1) \geq n+2
  \end{displaymath}
  where the first inequality follows from the induction hypothesis and
  the second inequality holds for any~$n \in \naturals$. Thus, $Q(n)$
  implies $Q(n+1)$.

  To wrap things up,
  \begin{displaymath}
    2^{(n+1)^2} = 2^{n^2+2n+1} \geq 2^{2n+1}n! \geq (n+1)n! = (n+1)!
  \end{displaymath}
  thus $P(n)$ implies $P(n+1)$.
}
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
% strong induction
% source: Velleman section 6.4, problem 9

Let the sequence $G_0, G_1, G_2,\ldots$ be defined recursively as
follows: $G_0 = 0$, $G_1 = 1$, and $G_n = 5 G_{n-1} - 6 G_{n-2}$, for
every $n \in \mathbb{N}, n \geq 2$.

Prove that for all $n \in \mathbb{N}$, $G_n = 3^n - 2^n$.

\solution{%
\medskip
\textbf{Solution:}
  Let $P(n)$ be the predicate that $G_n = 3^n - 2^n$.  We prove
  $P(n)$, for all $n \in \mathbb{N}$, by strong induction on $n$.

  \begin{description}\itemsep 0\baselineskip
  \item[Base Case:] \mbox{} \\ In order to simplify the strong
    induction, we use two base cases, in particular $n = 0$ and $n =
    1$.  By the definition of the sequence it is the case that $G_0 =
    0$.  For $n = 0$, it is the case that $3^n - 2^n = 3^0 - 2^0 = 1 -
    1 = 0$; that is, it follows that $P(0)$ holds.  Similarly, by the
    definition of the sequence it is the case that $G_1 = 1$.  For $n
    = 1$, it is the case that $3^n - 2^n = 3^1 - 2^1 = 3 - 2 = 1$;
    that is, it follows that $P(1)$ holds.

  \item[Inductive Step:] \mbox{} \\ %
    We must show that for all $n \in \nats, n \geq 2$, it is the case
    that $(\forall\; k \in [ 0, n ], P(k)) \implies P(n+1)$.
    
    \begin{enumerate}\itemsep 0\baselineskip
    \item Fix $n \in \nats, n \geq 2$.
      
    \item Assume that the elements of the sequence $G_x$, for $0 \leq
      x \leq n$, can be expressed as $G_x = 3^x - 2^x$.
      
    \item The element of the sequence $G_{n+1}$ can be expressed as
      $G_{n+1} = 3^{n+1} - 2^{n+1}$.
      
      \begin{enumerate}\itemsep 0\baselineskip
      \item By the definition of the sequence we have $G_{n+1} = 5 G_n
        - 6 G_{n-1}$.  
        
      \item By our induction hypothesis, it is the case that $G_n =
        3^n - 2^n$ and $G_{n-1} = 3^{n-1} - 2^{n-1}$
        
      \item Thus, $G_{n+1} = 5 (3^n - 2^n) - 6 (3^{n-1} - 2^{n-1})$.
        Working through the algebra, we conclude that $G_{n+1} =
        3^{n+1} - 2^{n+1}$, as needed for the inductive step.
        
      \item QED 
        
      \end{enumerate}
      
    \item QED (implication and UG)
      
    \end{enumerate}
    
  \item QED (induction)
    
  \end{description}
}

%This problem is from Kavita's section:
\problem 

The 6.042 course information sheet states:

\begin{quotation}
During the second hour or so [of recitation], the students will work
in groups of three or four, and each group will be assigned a problem
to solve as a team.
\end{quotation}
\bparts
\ppart
Using strong induction, prove that if a recitation contains at least 6
students, then the class can be divided into teams, each consisting of
either 3 or 4 students.

\bigskip

\solution{%
\textbf{Solution:}

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
a recitation with $n$ students can be divided into teams of 3 or 4.
In the base cases, $P(6)$ is true because there could be two teams of
3, $P(7)$ is true because there could be a team of 3 and a team of 4,
and $P(8)$ is true because there could be two teams of 4.  In the
inductive step, for $n \geq 8$, assume $P(6), \ldots, P(n)$ to prove
$P(n+1)$.  If a recitation has $n+1$ students, then three students can
form a team of 3, and the remaining $n-2$ students can be divided into
teams of 3 or 4 by induction.  This shows that $P(6), \ldots, P(n)$
imply $P(n+1)$, and the claim is proved by induction.
\end{proof}
}

%We have another very similar proglem, so change One to Another; Ivan
%One plan considered by the 6.042 staff, then dropped, involved

Another plan considered by the 6.042 staff, then dropped, involved
requiring students in tutorials to work in groups of either exactly 4
or exactly 7 students. 
We abandoned this plan when we realized that a tutorial section of
size 13 could not be split up in this way.


\ppart What is the smallest number $k$ such that all tutorials of $k$
or more students \emph{can} be split into teams of 4 and 7?

\ppart Prove that $k$ is the smallest such number.

\ppart Prove (by induction) that all tutorials of $k$ or more students
can be split into teams of size 4 and 7.

\bigskip

\solution{%

\noindent 
\textbf{Solution:}
\noindent
  The smallest number $k$ such that all tutorials of $k$ or
  more students \emph{can} be split into teams of 4 and 7 is $18$.

  A tutorial of size $17$ \emph{can not} be split into teams of
  4 and 7.  In particular, a tutorial of size $17$ can contain at most
  2 groups of 7.  Consider the various possible splits of the
  tutorial: (i) no groups of 7: since the only other group size is 4 we
  can not split the tutorial of 17; (ii) one group of 7: the remaining
  10 students can not be split into groups of 4; (iii) two groups of 7:
  the remaining 3 students can not be split into groups of 7.

  The proof is by strong induction on the size $n$ of the
  tutorial.  Let $P(n)$ be the predicate that a tutorial of size $n$
  can be split into groups of size 4 and 7.

  We must show that $P(n)$ holds for all $n \geq 18$.

  \begin{tabbing}
    XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=XXX\=\kill
    1. \textbf{Base Case:} $P(18)$, 18 = 4 + 7 + 7 \\
    2. \textbf{Base Case:} $P(19)$, 19 = 4 + 4 + 4 + 7 \\
    3. \textbf{Base Case:} $P(20)$, 20 = 4 + 4 + 4 + 4 + 4 \\
    4. \textbf{Base Case:} $P(21)$, 21 = 7 + 7 + 7 \\
    5. \textbf{Inductive Step:} 
    $\forall\; n \geq 21, ( \forall\; k \in [18,n], P(k) ) \implies P(n+1)$ \\
    \> 1. Fix $n \geq 21$.\\
    \> 2. From the inductive hypothesis $P(k)$ holds, for all $k \in [18,n]$. \\
    \> 3. In particular, $P(n-3)$ holds. \\
    \> 4. The size of the $n+1$ student tutorial is $4$ students
    greater than the $n-3$ student tutorial. \\
    \> 5. Thus, we can split up the $n+1$ tutorial as the $n-3$ tutorial \\
    \> \quad\ and with an extra 4 student group. \\
    \> 6. QED \\
    6. QED                        
  \end{tabbing}

}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%
%pset2 problem6 from spring98 (part A variant of F94)

\problem Pinpoint, and illustrate with a counterexample, \emph{exactly}
where the following suggested proofs go awry.

\bparts
\ppart Claim 1: $(\forall \mbox{real } x) (\forall n\in \naturals) : x^n=1$.

Suggested proof by strong induction on $n$:

(Base case, $ n= 0$) $x^n = x^0=1$ by definition of ``zeroth power'' of a
real number.

(Strong Induction hypothesis) For all $k\leq n: x^k=1$.

We must show that $x^{n+1}=1.$ By the strong inductive hypothesis, with
$k=n$ and $k=1,$ we have $x^n=1$ and $x^1=1$.  So,
\[x^{n+1}=x^nx^1 = 1\times 1=1.\] \qed

\solution{
The proof of the induction step is not correct when $n=0$.  In this case,
$k=1$ is not $\leq n$, so we cannot assume by strong induction that $x^1 =
1$, which of course it is not when $x\neq 1$.
}

\ppart Claim 2: For any positive integers $p, n, x_1, x_2,\ldots,
x_n$, if $p \divides x_1x_2\ldots x_n$, then $p \divides x_i$ for some
$1\leq i\leq n$.

Suggested proof by strong induction on $n$:

(Base case, $n= 1$) When $n=1$, we have $p \divides x_1$, therefore we
can let $i=1$ and conclude $p \divides x_i$.

(Induction case) Now assuming the claim holds for all $k\leq n$, we must
prove it for $n+1$.

So suppose $p \divides x_1x_2\ldots x_{n+1}$.  Let $y_n = x_n
x_{n+1}$, so $x_1x_2\ldots x_{n+1} = x_1x_2\ldots x_{n-1}y_n$.  Since
the righthand side of this equality is a product of $n$ terms, we have
by induction that $p$ divides one of them.  If $p \divides x_i$ for
some $i < n$, then we have the desired $i$.  Otherwise $p \divides
y_n$.  But since $y_n$ is a product of the two terms $x_n, x_{n+1}$,
we have by strong induction that $p$ divides one of them.  So in this
case $p \divides x_i$ for some $i = n$ or $i = n+1$. \qed

\solution{
\bigskip
The statement ``we have by strong induction that $p$ divides one of them''
is the place where the proof breaks down: it appeals to strong induction
to justify applying the induction hypothesis for $2=k\leq n$.  But the
base case was $n=1$, so we can't assume $2 \leq n$.  Note that the
reasoning above is fine for every $n\geq 2$, so the whole proof would be
fine if we had an argument to prove the claim for $n+1=2$.  But of course
we can't prove it for $n+1=2$ because it isn't true: let $p=6, x_1 =2, x_2
=3$.  Even though the reasoning is fine for every $n\geq 2$, the fact that
it failed for $n=1$ let us deduce a patently false result.
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem There are two types of creature on planet Xoros 19, A-lings
and B-lings. Furthermore, every creature belongs to a particular
generation.  The creatures in each generation reproduce according to
certain rules and then die off.  The subsequent generation consists
entirely of their offspring.

The creatures of Xoros 19 pair with a mate in order to reproduce.
First, as many A-B pairs as possible are formed.  The remaining
creatures form A-A pairs or B-B pairs, depending on whether there is
an excess of A-lings or of B-lings.  If there are an odd number of
creatures, then one in the majority species dies without reproducing.
The number and type of offspring is determined by the types of the
parents

\begin{itemize}
\item If both parents are A-lings, then they have three A-ling
offspring.

\item If both parents are B-lings, then they have two B-ling offspring
and one A-ling offspring.

\item If there is one parent of each type, then they have one
offspring of each type.
\end{itemize}

There are 200 A-lings and 800 B-lings in the first generation.  Use
induction to prove that the number of A-lings will always be at most
twice the number of B-lings.

\bigskip

\solution{%
\textbf{Solution:}

An induction proof with the hypothesis that the number of A-lings is
always at most twice the number of B-lings will not go through.  A
stronger induction hypothesis is required.

\medskip

\begin{proof}
We will prove that there are always at least as many B-lings as
A-lings; the claim that the number of A-lings is always at most twice
the number of B-lings is weaker and thus follows.

The proof is by induction on the generation number.  Let $P(n)$ be the
proposition that there are at least as many B-lings as A-lings in
generation $n$.  In the base case, $P(1)$ is true because there are
800 B-lings and only 200 A-lings in the first generation.

In the inductive step, for $n \geq 1$ assume that there are at least
as many B-lings as A-lings in generation $n$ to prove that there are
at least as many B-lings as A-lings in generation $n+1$.  Let $a$ be
the number of A-lings in generation $n$, and let $b$ be the number of
B-lings.  Note that $b \geq a$ by the induction assumption.  Then
there are no A-A pairs formed, there are $a$ A-B pairs formed, and
there are $\lfloor \frac{b - a}{2} \rfloor$ $B-B$ pairs formed.  As a
result, the number of A-lings in generation $n+1$ is $a + \lfloor
\frac{b - a}{2} \rfloor$, and the number of B-lings is $a + 2 \lfloor
\frac{b - a}{2} \rfloor$.  Therefore, there are at least as many
B-lings as A-lings in generation $n+1$.  Thus, for all $n \geq 1$,
$P(n)$ implies $P(n+1)$, and the claim is proved by induction.
\end{proof}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% These problems are from Joe's section
% multi base cases, strong induction






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%STRUCTURAL INDUCTION
%These problems are from StructuralInduction.tex and they are 
% Ray's section (I don't know what year..)

%Problem 5
%\problem The famous Towers of Hanoi problem. There are three poles. On
%one of the poles there is a stack of rings, largest at the bottom,
%smallest at the top.  You have to move the rings from one pole
%to another,
%%pole $r$, $r \in \{1,2,3 \}$ to pole $s$, $s \in \{1,2,3 \}$
%so that the rings are in thes
%same order on the new pole, while observing the following rules:
%\begin{itemize}
%\item
%Only one ring may be moved at a time. 
%\item At no time may a larger ring be on top of a smaller ring. 
%\end{itemize}
%Prove by induction that the Towers of Hanoi Problem can always be
%solved.  


%\noindent

%\solution{%
%\noindent
%\textbf{Solution:}
%It is important to formalize the inductive hypothesis in the right way.
%We are proving a predicate $P(n)=$``For any poles $P_1,P_2$, a Hanoi
%tower of height $n$ can be moved from $P_1$ to $P_2$ according to
%the rules above.'', for any $n\geq{1}$

%\medskip
%\noindent 
%
%{\em Base case:} $P(1)$ is true because a single ring can be moved
%from one pole to another in accordance with the rules.

%\medskip
%\noindent 
%%
%{\em Inductive case:} Let $n$ be some nonnegative integer.  Assume
%$P(n)$.  We prove $P(n+1)$ as follows: Assume that a Hanoi tower $T$
%of height $n+1$ has to be moved from pole $P_1$ to $P_2$.  Think about
%the top $n$ rings of $T$ (all rings except the base ring $R$) as a
%``subtower'' $T'$.  Since $T'$ is a Hanoi tower of height $n$, from
%the inductive assumption $P(n)$, we know that we can move it according
%to the Hanoi-Tower game rules from $P_1$ to $P_3$ (the ring $R$ on the
%bottom of pole $P_1$ does not trouble us since it is bigger than all
%rings of $T'$).  When such move of $T'$ from $P_1$ to $P_3$ is done,
%we move $R$ from $P_1$ to $P_2$, and then we use the $P(n)$ assumption
%again to argue that there are some Hanoi-Tower game moves which allow
%$T'$ to be moved from $P_3$ to $P_2$, on top of $R$.  In this way, the
%whole tower $T$ was moved from $P_1$ to $P_2$, and so $P(n+1)$ is
%true.
%}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
% structural induction 

The set $W$ of ``well-formed parenthesis strings'' can be defined by
the following rules:

\vspace*{-0.5\baselineskip}

\begin{enumerate}\itemsep 0\baselineskip
\item the empty string is in $W$, and
\item if $s$ and $t$ are in W then the string $(s)t$ is in $W$.
\end{enumerate}
For example, the string $(()())()$ is a well-formed parenthesis
string, where as the string $)(())$, isn't.

Use structural induction to prove that any prefix of any well-formed
parenthesis string has at least as many left parentheses as right
parentheses.

\solution{
\textbf{Solution:}

  Let $P(t)$, for $t \in W$, be the predicate that any prefix of a
  well-formed parenthesis string $t$ has at least as many left as
  right parentheses.  We prove that $P(t)$ holds for all $t \in W$ by
  structural induction.

  \begin{description}\itemsep 0\baselineskip
  \item[Base Case:] \mbox{} \\ %
    Let $t$ be the empty string $\lambda$.  $P(\lambda)$ holds since
    there are no left or right parentheses.

  \item[Inductive Step:] \mbox{} \\ %
    We must show that for all $s, t \in W$, $P(s)$ and $P(t)$ imply
    $P((s)t)$; that is, that any prefix of the string $(s)t$ has at
    least as many left as right parentheses.  Let $s, t$ be any
    strings in $W$ and assume that $P(s)$ and $P(t)$ hold.  Moreover,
    for any $s_1$ and $s_2$, let $s_1 \leq s_2$ denote that $s_1$ is a
    prefix of the string $s_2$.  Let $p$ be any prefix of the string
    $(s)t$ and consider the following set of exhaustive cases:

    \begin{description}\itemsep 0\baselineskip
    \item[$p = \lambda$] \mbox{} \\ %
      In this case, $p$ trivially satisfies the claim.

    \item[$p = ($] \mbox{} \\ %
      In this case, $p$ trivially satisfies the claim.

    \item[$p = (s'$, for some string $s'$, $s' \leq s$] \mbox{} \\ %
      In this case, since $P(s)$ holds, it follows that $s'$ has at
      least as many left as right parentheses.  Thus, the same
      property holds for the string $(s'$.

    \item[$p = (s)$] \mbox{} \\ %
      In this case, since $P(s)$ holds, the string $(s)$ has at least
      as many left as right parentheses.

    \item[$p = (s)t'$, for some string $t'$, $t' \leq t$] \mbox{} \\ %
      In this case, by the previous case, we know that the string
      $(s)$ has at least as many left as right parentheses.  Moreover,
      since $P(t)$ holds, it follows that $t'$ has at least as many
      left as right parentheses.  Thus, it follows that the string
      $(s)t'$ has at least as many left as right parentheses.
    \end{description}

    Thus, any prefix of $(s)t$ has at least as many left as right
    parentheses; that is, $P((s)t)$ holds.  Finally, by universal
    generalization, the inductive step holds for any such $s, t \in
    W$.

  \end{description}

}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\def\mult{\diamond}
\problem Consider the following ``mungiplication''
operation $\mult$, defined recursively on the natural numbers as follows:
\begin{enumerate}
\item for any $x$, $0 \mult x = 0$
\item for any $x$, $(n+1) \mult x = n\mult x + x$
\end{enumerate}
(You may note some similarity to the famous ``multiplication''
operation, but should {\bf not} use any facts about multiplication in
this problem.)  Do not assume anything about $\mult$ beyond what is
given above.
\begin{problemparts}

\ppart Prove the {\bf distributive law:} for any $n,a,b$, 
\[
n\mult (a+b) = n\mult a+n \mult b
\]
You may use all standard facts about addition.  But do not use
summation notation.

\solution{
{\bf Solution:}
\begin{proof}
By induction on $n$:

{\em Base case, $n = 0$:}
\[ 0 \mult (a + b) = 0 = 0 + 0 = (0 \mult a) + (0 \mult b) \]

{\em Inductive case, assuming $n \mult (a + b) = (n \mult a) + (n \mult b)$:}

\begin{eqnarray}
\label{mung-one}
(n + 1) \mult (a + b) & = & n \mult (a + b) + (a + b)\\
\label{mung-two}
& = & n \mult a + n \mult b + (a + b)\\
\label{mung-three}
& = & (n \mult a + a) + (n \mult b + b)\\
\label{mung-four}
& = & (n + 1) \mult a + (n + 1) \mult b
\end{eqnarray}

Equations~\ref{mung-one}~and~\ref{mung-four} are by the
``mungiplication'' definition. Equation~\ref{mung-two} is by the inductive
assumption. Equation~\ref{mung-three} is by addition's commutative and associative
properties.
\end{proof}
}

\ppart Prove the {\bf annihilation law:} for any $x$,
\[
x \mult 0 = 0
\]

\solution{
{\bf Solution:}
\begin{proof}
By induction on $x$:

{\em Base case, $x = 0$:}
\[ 0 \mult 0 = 0 \]
{\em Inductive case, assuming $x \mult 0 = 0$:}

By the ``mungiplication'' definition,
\( (x + 1) \mult 0 = x \mult 0 + 0\).
But \( x \mult 0 + 0 = x \mult 0 = 0 \) by the inductive assumption.
\end{proof}
}

\ppart Prove the {\bf commutative law:} for any $x, n$,
\[
x \mult n = n \mult x
\]

\solution{
{\bf Solution:}
\begin{proof}
By induction on $n$:

{\em Base case, $n = 0$:}
\[ x \mult 0 = 0 \mult x = 0 \]
{\em Inductive case, assuming $x \mult n = n \mult x$:}

\begin{eqnarray}
\label{mungcom-one}
x \mult (n + 1) & = & x \mult n + x \mult 1\\
\label{mungcom-onefive}
& = & x \mult n + x\\
\label{mungcom-two}
& = & n \mult x + x\\
\label{mungcom-three}
& = & (n + 1) \mult x
\end{eqnarray}

Equation~\ref{mungcom-one} is by the distributive property from part A.
Equation~\ref{mungcom-onefive} is by a subproof that we show next. 
Equation~\ref{mungcom-two} is by the inductive assumption.
Equation~\ref{mungcom-three} is by the ``mungiplication'' definition.
\end{proof}

\begin{proof}For any $x$, $x \mult 1 = x$ (by strong induction):

{\em Base cases, $x = 0,1$:}
\[ 0 \mult 1 = 0 \]
\[ 1 \mult 1 = 0 \mult 1 + 1 = 0 + 1 = 1 \]

{\em Inductive case, assuming $x \mult 1 = x$:}
\begin{eqnarray}
\label{lemma-one}
(x + 1) \mult 1 & = & x \mult 1 + 1\\
\label{lemma-two}
& = & x + 1
\end{eqnarray}

Equation~\ref{lemma-one} is by the ``mungiplication'' definition.
Equation~\ref{lemma-two} is by the inductive assumption.
\end{proof}
}

\ppart
{\em Optional:} Prove the {\bf associative law:} for any $a, b, n$,
\[
(a \mult n) \mult b = a \mult (n \mult b)
\]

\solution{
\begin{proof}
By induction on $n$:

{\em Base case, $n = 0$:}
\[
(a \mult 0) \mult b = 0 \mult b = 0 = a \mult 0 = a \mult (0 \mult b)
\]
This is by the identity law from part B and the definition of
``mungiplication''.

{\em Inductive case, assuming $(a \mult n) \mult b = a \mult (n \mult b)$:}

\begin{eqnarray}
\label{mungbon-1}
(a \mult (n + 1)) \mult b & = & ((n + 1) \mult a) \mult b\\
\label{mungbon-2}
& = & (n \mult a + a) \mult b\\
\label{mungbon-3}
& = & (n \mult a) \mult b + a \mult b\\
\label{mungbon-4}
& = & (a \mult n) \mult b + a \mult b\\
\label{mungbon-5}
& = & a \mult (n \mult b) + a \mult b\\
\label{mungbon-6}
& = & a \mult (n \mult b + b)\\
\label{mungbon-7}
& = & a \mult ((n + 1) \mult b)
\end{eqnarray}

Equations~\ref{mungbon-1}~and~\ref{mungbon-4} use the commutative property from
part C. Equations~\ref{mungbon-2}~and~\ref{mungbon-7} use the
``mungiplication'' definition.
Equation~\ref{mungbon-6} uses the distributive property from part A.
Equation~\ref{mungbon-3} uses both the commutative and
distributive properties. Equation~\ref{mungbon-5} uses the inductive assumption.

\end{proof}
}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}
\end{document}                            
