\documentstyle[12pt,twoside]{article}

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

\begin{document}\induction


\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Velleman 6.3.7b & 6.3.7c
%
% Was on pset2 spring 2001. /Lars
%
\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}

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

%BEGIN Kavita's problems
%Fall 1998


%**************
%   PSET 2    *
%**************

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

\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

\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}

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


\problem Use induction to prove that the following equation holds for
all $n \geq 1$.

\begin{eqnarray*}
\frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + \ldots \frac{1}{2^n}
        & = & 1 - \frac{1}{2^n}
\end{eqnarray*}

\bigskip

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

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

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

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

\problem Use induction on $n$ to prove that the following inequality
holds for all integers $n \geq 1$ and for all non-negative real
numbers $x_1, \ldots, x_n$.

\begin{eqnarray*}
(x_1 + x_2 + \ldots + x_n)^2 \geq x_1^2 + x_2^2 + \ldots + x_n^2
\end{eqnarray*}

\bigskip

\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
the above inequality holds for all non-negative real numbers $x_1,
\ldots, x_n$.  In the base case, $P(1)$ is true because both sides of
the inequality are equal to $x_1^2$, and so the $\leq$ relation is
satisfied.  In the inductive step, for $n \geq 1$ assume $P(n)$ in
order to prove $P(n+1)$ as shown below.

\begin{eqnarray*}
(x_1 + x_2 + \ldots + x_n + x_{n+1})^2
        & = &   (x_1 + x_2 + \ldots + x_n)^2
                + 2 (x_1 + x_2 + \ldots + x_n) x_{n+1}
                + x_{n+1}^2 \\
        & \geq &        (x_1 + x_2 + \ldots + x_n)^2 + x_{n+1}^2 \\
        & \geq &        x_1^2 + x_2^2 + \ldots + x_n^2 + x_{n+1}^2
\end{eqnarray*}

The first step is algebra.  In the second step, a term is dropped;
this gives an inequality, because the dropped term must be
non-negative on account of all the $x_i$ being non-negative.  The
third step uses the induction hypothesis.  This shows that $P(n)$
implies $P(n+1)$, and the claim is proved by induction.
\end{proof}

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

\problem Use induction to prove that for all $n \geq 2$, the quantity
$n (n^2 - 1) (n^2 - 4)$ is either divisible by 5 or by 7.  For
example, $6 (6^2 - 1) (6^2 - 4) = 6720 = 7 \cdot 960$.

\medskip

\bigskip

An induction proof with the hypothesis that the expression is
divisible by 5 or by 7 will not go through; this assumption is not
strong enough to complete the inductive step.  In fact, the expression
is always divisible by 5, but is only sometimes divisible by 7.
Therefore, the right idea is to strengthen the induction hypothesis to
assert that the expression is always divisble by 5.

\begin{proof}
We will prove the stronger statement that $n (n^2 - 1) (n^2 - 4)$ is
always divisible by 5.  The proof uses the fact that this expression
can be rewritten by factoring $n^2 - 1$ and $n^2 - 4$ as follows:

\begin{eqnarray*}
n (n^2 - 1) (n^2 - 4) & = &(n - 2) (n - 1) n (n + 1) (n + 2).
\end{eqnarray*}

The proof now proceeds by induction.  Let $P(n)$ be the propositon
that $(n - 2) (n - 1) n (n + 1) (n + 2)$ is divisible by 5.  In the
base case, $P(5)$ is true because $5 (5^2 - 1) (5^2 - 4) = 2520 = 5
\cdot 504$.  In the inductive step, for $n \geq 2$ assume $P(n)$
to prove $P(n+1)$; that is, we want to prove that $(n - 1) n (n + 1)
(n + 2) (n + 3)$ is divisible by 5.  We can rewrite this expression as
follows.

\begin{eqnarray*}
(n - 1) n (n + 1) (n + 2) (n + 3)
        & = &   (n - 2) (n - 1) n (n + 1) (n + 2) + \\
        & \mbox{} &     5 (n - 1) n (n + 1) (n + 2)
\end{eqnarray*}

The top term on the right is divisible by 5 by the induction
hypothesis, and the botton term on the right is divisible by 5 because
the leading coefficient is 5.  Therefore, the right side and the left
side of the equation are both divisible by 5.  This shows that $P(n)$
implies $P(n+1)$, and the claim is proved by induction.
\end{proof}

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

\problem Use induction on $n$ to prove that for all $n \geq 0$, there
are $2 n^2 + 2n + 1$ solutions to the inequality $|x| + |y| \leq n$,
where $x$ and $y$ are integers.

\bigskip

\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
there are $2 n^2 + 2n + 1$ solutions to the inequality $|x| + |y| \leq
n$, where $x$ and $y$ are integers.  In the base case, $P(0)$ is true
because $2 (0)^2 + 2 (0) + 1 = 1$, and there is one solution to the
equation $|x| + |y| \leq 0$, namely $x = y = 0$.

In the inductive step, assume $P(n)$ to prove $P(n+1)$.  That is, we
want to prove that there are $2 (n+1)^2 + 2 (n + 1) + 1 = 2n^2 + 6n +
5$ solutions to the inequality $|x| + |y| \leq n + 1$.  Every solution
to this inequality is also either a solution to the tighter inequality
$|x| + |y| \leq n$ or else to the equation $|x| + |y| = n + 1$.  Thus,
the number of solutions is equal to the number of solutions to the
tighter inequality plus the number of solutions to the equation.

By induction, there are $2 n^2 + 2n + 1$ solutions to the tighter
inequality.  All that remains is to count solutions to the equation.
The value of $x$ must be in the range $-(n+1), \ldots, n+1$.  If $x$
takes on either of the two values $-(n+1)$ or $n+1$, then there is a
single solution, with $y = 0$.  If $x$ takes on one of the $2n+1$
values in the range $-n, \ldots, n$, then there are two solutions, one
with $y = n + 1 - |x|$ and one with $y = -(n + 1 - |x|)$.  Thus, there
are $2 + 2 \cdot (2n + 1) = 4n + 4$ solutions to the equation and $2
n^2 + 2n + 1$ solutions to the tighter inequality, giving $2 n^2 + 6n
+ 5$ solutions in all, as desired.  Therefore, $P(n)$ implies
$P(n+1)$, and the claim is proved by induction.
\end{proof}

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


\problem The 6.042 mascot, Theory Pig, made a startling discovery while
playing with his prized collection of unit squares over the weekend.
Here is what happened.

First, Theory Pig put his favorite unit square down on the floor as in
diagram (a) of Figure~\ref{fig:squares}.  He noted that the length of
the periphery of the resulting shape was 4, an even number.  Next, he
put a second unit square down next to the first so that the two
squares shared an edge as in diagram (b).  He noticed that the length
of the periphery of the resulting shape was now 6, which is also an
even number.  (The periphery of each shape in the figure is indicated
by a thicker line.)  Theory Pig continued to place squares so that
each new square shared an edge with at least one previously-placed
square and no squares overlapped.  Eventually, he arrived at the shape
in diagram (c).  He realized that the length of the periphery of this
shape was 36, which is again an even number.

Our plucky porcine pal is perplexed by this peculiar pattern.  Use
induction on the number of squares to prove that periphery length is
always even, no matter how many squares Theory Pig places or how he
arranges them.

\begin{figure}[htbp]
\centerline{\resizebox{!}{2.0in}{\includegraphics{figs/f98ps2.eps}}}
\caption{Some shapes that Theory Pig created.} \label{fig:squares}
\end{figure}

\bigskip

\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that the
periphery length is even after $n$ squares are placed.  In the base
case, $P(1)$ is true because the periphery of a single square has
length 4, which is even.

In the inductive step, assume that the periphery length is even after
$n$ squares are placed to prove that the periphery length is even
after $n+1$ squares are placed.  The $(n+1)$-st square could share 1,
2, 3, or 4 edges with previously-placed squares.

\begin{itemize}

\item If the new square shares 1 edge with a previously placed square,
then this one edge is removed from the periphery, but three edges of
the new square are added to the periphery.  Overall, the periphery
length increases by two and thus remains even.

\item If the new square shares 2 edges with previously placed squares,
then these two edges are removed from the periphery, but two edges of
the new square are added.  The periphery length is unchanged and thus
remains even.

\item If the new square shares 3 edges, then these three edges are removed
from the periphery, but one edge is added.  The periphery length
decreases by two and remains even.

\item If the new square shares 4 edges, then these four edges are removed
from the periphery and none are added.  The periphery length decreases
by four and remains even.

\end{itemize}

In all cases, the length of the periphery remains even.  Therefore,
for all $n \geq 1$, $P(n)$ implies $P(n+1)$ and the claim is proved by
induction.
\end{proof}

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

\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}

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

\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}

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

\problem Suppose that the sequence $x_1, x_2, x_3, \ldots$ is defined
as follows.  The first term, $x_1$, is equal to 1.  For $n \geq 1$,
the term $x_{n+1}$ is equal to $x_n$ if $n+1$ is odd and is equal to
$1 + x_{(n+1)/2}$ if $n+1$ is even.  Use strong induction on $n$ to
prove that for all $n \geq 1$, the number of digits in the binary
representation of $n$ is equal to $x_n$.

\bigskip

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition there
are $x_n$ digits in the binary representation of $n$.  In the base
case, $P(1)$ is true because there is a single digit in the binary
representation of 1.  In the inductive step, for $n \geq 1$, assume
$P(1), \ldots, P(n)$ to prove $P(n+1)$.  There are two cases to
consider.

\begin{enumerate}
\item If $n+1$ is odd, then the binary representation of $n+1$ is the
binary representation of $n$ with the least significant digit changed
from a zero to a one.  By the induction hypothesis, there are $x_n$
digits in the binary representation of $n$.  Therefore, there also are
$x_n = x_{n+1}$ digits in the binary representation of $n+1$.

\item If $n+1$ is even, then the binary representation of $n+1$ is the
binary representation of $(n+1)/2$ with a zero appended.  By the
induction hypothesis, there are $x_{(n+1)/2}$ digits in the binary
representation of $(n+1)/2$.  Therefore, there are $1 + x_{(n+1)/2} =
x_{n+1}$ digits in the binary representation of $n+1$.
\end{enumerate}

This shows that $P(1), \ldots, P(n)$ imply $P(n+1)$, and the claim is
proved by induction.
\end{proof}


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

\problem Suppose that $x_0 = 0$, $x_1 = \frac{1}{2}$, and the
following equation holds for all $n \geq 1$:

\begin{eqnarray*}
x_{n+1} + x_{n-1} = \sqrt{3} x_{n}
\end{eqnarray*}

Use strong induction to prove that $x_n =
\sin(\frac{n \pi}{6})$ for all $n \geq 0$.

\bigskip

\begin{proof}
The proof will make use of the trignometric identity for a sum of sines,

\begin{eqnarray*}
\sin A + \sin B & = &   2 \cos\frac{A-B}{2} \sin\frac{A+B}{2}.
\end{eqnarray*}

In particular, the following form of the identity will be needed:

\begin{eqnarray*}
\sin A          & = &   2 \cos\frac{A-B}{2} \sin\frac{A+B}{2} - \sin B
\end{eqnarray*}

The proof is by strong induction.  Let $P(n)$ be the proposition that
$x_n = \sin \frac{n \pi}{6}$.  In the base cases, $P(0)$ is true
because $x_0 = 0 = \sin 0$, and $P(1)$ is true because $x_1 =
\frac{1}{2} = \sin \frac{\pi}{6}$.  In the inductive step, for $n \geq
1$ assume $P(0), \ldots, P(n)$ to prove $P(n+1)$.  That is, we want to
prove that $x_{n+1} = \sin \frac{(n+1) \pi}{6}$.  The equation stated
in the problem can be rewritten as follows:

\begin{eqnarray*}
x_{n+1}
        & = &   \sqrt{3} x_{n} - x_{n-1} \\
        & = &   \sqrt{3} \sin \frac{n \pi}{6} -
                        \sin\frac{(n - 1) \pi}{6} \\
        & = &   \sin \frac{(n+1) \pi}{6}
\end{eqnarray*}

The second equation follows from the induction hypothesis, and the
third equation follows from the sum-of-sines identity with $A =
\frac{(n + 1) \pi}{6}$ and $B = \frac{(n - 1) \pi}{6}$.  Therefore,
$P(0), \ldots, P(n)$ imply $P(n+1)$, and the claim is proved by strong
induction.
\end{proof}

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

\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

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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: spring00 ps1
Find a closed-form formula for 
\[
\frac{1}{1*2} + \frac{1}{2*3} + \frac{1}{3*4} + \ldots + \frac{1}{n(n+1)}
\]
by examining the values of this expression for small values of $n$.
Use mathematical induction to prove your formula holds for all natural
numbers.

\textbf{Solution:}
Let $s(n) = \frac{1}{1*2} + \frac{1}{2*3} + \frac{1}{3*4} + \ldots + \frac{1}{n(n+1)}$. 
For small values of $n$, we have:
\begin{center}
\begin{tabular}{l|c}
$n$ & $s(n)$ \\
\hline
$0$ & $0$ \\
$1$ & $1/2$ \\
$2$ & $2/3$ \\
$3$ & $3/4$ 
\end{tabular}
\end{center}
So we guess that $s(n) = n/(n+1)$. 

\solution{
Let $P(n)$ be the proposition that $s(n) =  n/(n+1)$.
We want to prove, by induction, $\forall n \in \mathbb{N}\;P(n)$.

\begin{enumerate}

\item (Base case: Prove $P(0)$.)  The base case is established by the table
above. 

\item (Inductive case: Prove $\forall n \in \mathbb{N}\;(P(n) \implies
P(n+1))$.) Substituting our definition of $P(n)$, we must show 
$s(n) = \frac{n}{n+1} \implies s(n+1) = \frac{n+1}{n+2}$ 
for all natural numbers $n$.  
\begin{tabbing}
XXXXXXti\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
 1. Fix $n \geq 0$.\\
 2. Assume $s(n)= \frac{n}{n+1}$\\ 
 3. $s(n+1)$ 
\>  $ = s(n) +  \frac{1}{(n+1)(n+2)}$
  \>   (definition of $s(n)$) \\[.5ex] 

\>  $=\frac{n}{n+1}+\frac{1}{(n+1)(n+2)}$
  \>  (inductive hypothesis) \\[.5ex]  
\>  $=\frac{(n+1)^2}{(n+1)(n +2)}$            
  \>  (algebra)\\[.5ex]   
\>  $=\frac{(n+1)}{(n+2)}$
  \>  (division, note: $n+1 \not = 0$)\\ 
 4. QED 
\>\>  (implication)
\end{tabbing}

\item QED (induction)
\end{enumerate}
}

\problem %source: spring00 ps1
% ordinary induction 
Suppose you take a piece of paper and draw a bunch of straight lines,
each in its own arbitrary direction, that completely cross the paper.
This divides the paper up into polygonal regions.  Prove by induction
that you can always color the various regions using only \emph{two}
colors, so that any two regions that share a boundary line are
different colors.  Note that this need not be true of regions that
share only a boundary point.

\solution{

  We assume that all lines are straight and completely cross the
  paper.  Also, when we say that the regions are colored, we always
  mean they are colored using at most two colors, \eg red and green.
  We say that two regions are \emph{adjacent} if they share a boundary
  line.  Note that two regions cannot share two distinct boundary
  lines.

  Let $P(n)$ be the predicate that the regions formed by any set of
  $n$ distinct lines can be colored so that (two) adjacent regions are
  colored with different colors.  We prove that $P(n)$ holds for all
  $n \in \mathbb{N}$ by induction on $n$.

\begin{description}

\item[Base case:] The base case is $P(0)$.  There is only one region,
  and thus there are no adjacent regions.  So this case is trivially
  true.  The region may be colored either red or green.

\item[Inductive step:] We must show that for all $n \in \nats$ it is
  the case that $(P(n) \implies P(n+1))$; that is, if the regions
  formed by any $n$ distinct lines can be colored so that adjacent
  regions have different colors, then the regions formed by any $n+1$
  distinct lines can be colored so that adjacent regions have
  different colors.

\begin{enumerate}

\item 
Fix $n \in \mathbb{N}$.

\item
Assume that the regions formed by any $n$ distinct lines 
can be colored so that adjacent regions have different colors. 

\item 
The regions formed by any $n+1$ distinct lines 
can be colored so that adjacent regions have different colors. 
\begin{enumerate}

\item
Fix a set of $n+1$ lines. 
These lines divide the paper into a set $X$ of regions. 

\item
Select any line $l$ from that set. 
There are $n$ other lines, 
which divide the paper into a set $Y$ of regions, 
such that every region in $X$ is either a region in $Y$ 
or else it is part of a region in $Y$ that is split by $l$. 

\item
By the inductive hypothesis, 
the regions in $Y$ can be colored 
so adjacent regions are different colors. 
This also gives a coloring for the regions in $X$. 
Call this coloring of the regions in $X$ the ``original coloring.''

\item Line $l$ splits the paper into two sides.  Select one of the
  sides and flip all the colors of the regions on that side.  Call
  this coloring of the regions in $X$ the ``new coloring.''  We prove
  that, using the new coloring, any adjacent regions in $X$ have
  different colors.
\begin{enumerate}

\item Fix any two adjacent regions in $X$.  
\begin{description}

\item[Case 1:\ ] The regions share boundary line $l$.  The two regions
  had the same color in the original coloring.  The two regions are on
  opposite sides of $l$.  Therefore, the color in exactly one of the
  two regions was flipped and they have different colors in the new
  coloring.

\item[Case 2:\ ] The regions do not share boundary line $l$.  The two
  regions had different colors in the original coloring, and they are
  on the same side of $l$.  Thus, the color of either none or both
  regions was flipped and the two regions have different colors in
  the new coloring.

\end{description}

\item QED (universal generalization over adjacent regions)

\end{enumerate}

\item QED (universal generalization over sets of $n+1$ lines)

\end{enumerate}

\item QED (implication)

\end{enumerate}

\item QED (induction)

\end{description}
}

\problem %source: spring00 ps2, Parmenter p. 173
% ordinary induction

Prove by induction that $\forall\; n \geq 1$, the quantity $n^3 +
(n+1)^3 + (n+2)^3$ is divisible by~$9$.

\solution{
  Let $P(n)$ be the predicate that $n^3 + (n+1)^3 + (n+2)^3$ is
  divisible by $9$, \ie $P(n) = 9 | (n^3 + (n+1)^3 + (n+2)^3)$.  We
  prove that $P(n)$ holds for all $n \geq 1$ by induction on $n$.  In
  fact, the predicate $P(n)$ is also true for $n = 0$.

  \begin{description}\itemsep 0\baselineskip
  \item[Base Case:~~] $P(1)$ \mbox{} \\
    $P(1) = 9 | (1^3 + 2^3 + 3^3) = 9 | 36 = \True$ 

  \item[Inductive Step:~~] For all $n \geq 1$, $P(n) \implies P(n+1)$
    \begin{enumerate}\itemsep 0ex
    \item Fix $n \geq 1$.

    \item From the inductive hypothesis $P(n)$ holds, \ie $9 | (n^3 +
      (n+1)^3 + (n+2)^3)$.

    \item We must show that $P(n+1)$ holds, \ie $9 | ((n+1)^3 +
      (n+2)^3 + (n+3)^3)$.
          
      \begin{enumerate}\itemsep 0ex
      \item $(n+1)^3 + (n+2)^3 + (n+3)^3 = n^3 + (n+1)^3 + (n+2)^3 + 9
        (n^2 + 3n +3)$
        
      \item From the inductive hypothesis, $9 | (n^3 + (n+1)^3 + (n+2)^3)$.
        
      \item Also, it is simple to see that $9 | (9 (n^2 + 3n +3))$.

      \item Since $9$ divided both terms, it divides their sum.

      \item QED
          
      \end{enumerate}

    \item QED (implication and UG)

    \end{enumerate}

  \end{description}
}

\problem %source: spring00 ps2, fall96
% strengthen inductive hypothesis

The C.I.A. wants you to design plans to build, for an arbitrary $k
\geq 1$, a $2^k \times 2^k \times 2^k$ cubic foot granite cube that is
solid except for a missing single cubic foot that is one of the eight
cubic feet nearest the center of the cube.  It will have one of its
corners exactly at the center of the large cube.  The C.I.A. is not
telling you what is to be placed inside the cube.

You are to build this by cementing together {\em basic blocks} that
are 2-foot $\times$ 2-foot $\times$ 2-foot cubes, with one one-foot
cube missing from its corner~---~as shown in the diagram below.

\begin{figure}[h]
\centerline{\psfig{figure=figs/cube.ps,height=1in}}
\end{figure}

Describe your method for doing this.  Your plans should be described
recursively on $k$.

\solution{
    Let an $2^n \times 2^n \times 2^n$ cube with an arbitrary one-foot
    cubic block missing be denoted as an $n$-cube.  Moreover,
    throughout this problem, we assume that the one-foot block that is
    missing from any $n$-cube is at a lattice point, \ie at an
    integral number of feet from each side.

    \begin{theorem*} 
      For any positive integer $n$, any $n$-cube can be build out of
      $1$-cubes.
    \end{theorem*}
    \begin{proof} 
      Let $P(n)$ be the predicate that an $n$-cube can be build out of
      $1$-cubes.  We prove that $P(n)$ holds for any positive integer
      $n$ by induction on $n$.
      
      \begin{description}\itemsep 0ex
      \item[Base Case:~~] $P(1)$ is true since a $1$-cube is what we
        need to build.  This is precisely what we are given as a basic
        block.
 
      \item[Inductive Step:~~] We must show that for any positive
        integer $n$, $P(n)$ implies $P(n+1)$.  Consider an
        $(n+1)$-cube.  This block can be built using eight $n$-cubes
        as follows: build seven $n$-cubes such that they are all
        missing one of their corner blocks, arrange them so that their
        missing corner blocks meet in the center of the $(n+1)$-cube,
        fill up the gap with a $1$-cube such that the corner
        corresponding to the eighth $n$-cube is left empty, and,
        finally, build the eighth $n$-cube such that the appropriate
        one-foot cubic block is missing.  Notice, that the eight
        $n$-cubes can be build as desired because of the inductive
        hypothesis; that is, that any $n$-cube can be build out of
        $1$-cubes.
      \end{description}
    \end{proof}

    Now, we can state the following corollary.

    \begin{corollary*}
      For any positive integer $n$, an $n$-cube with any one-foot
      cubic block missing from its center can be build out of
      $1$-cubes.
    \end{corollary*}
    \begin{proof}
      $n$-cubes of this particular form, \ie with any one-foot cubic
      block missing from their center, is a particular case of what we
      showed in the above Theorem.  Thus, we know that $n$-cube with
      any one-foot cubic block missing from its center can be build
      out of $1$-cubes.  The construction of such a block can be done
      as outlined in the above theorem, with the exception that the
      missing one-foot block is missing from the center of the
      $(n+1)$-cube.
    \end{proof}
  }

\problem %source: spring00 ps2
% multi base cases, strong induction

One 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.

\bparts 

\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.

\eparts

\solution{
  \bparts 

  \ppart 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$.

  \ppart 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.

  \ppart 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
}

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

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{
  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}
}

\problem %source: spring00 ps2
% 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{
  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}

}

\problem %source: spring00 ps4
Attached to this problem set are some students' solutions
from a previous problem set.  Mark up these solutions, indicating
things that are incorrect or unclear, and if possible show how the
solution can be made completely correct and clear.

\clearpage%
\problempart Problem Set 2, Problem 1

\centerline{\resizebox{\textwidth}{!}{\includegraphics{figs/bad3.ps}}}

\omitsolution{
\begin{solution}
A number of different answers are acceptable here.  To guarantee full
credit, however, you should point out the inherent hand-waviness going
on with the statement ``and imposes constraints on.''  Correctly
understanding the constraints imposed on regions was critical to the
correct solution of the problem.  This was not addressed by the two
cases presented.

Saying that the proof had ``buildup error'' is another reasonable
answer, but does not address the point above.
\end{solution}
}

%\clearpage%
\problempart Problem Set 2, Problem 4

\centerline{\resizebox{\textwidth}{!}{\includegraphics{figs/bad1.ps}}}
%\clearpage
\centerline{\resizebox{\textwidth}{!}{\includegraphics{figs/bad4.ps}}}

%\clearpage%

\omitsolution{
\begin{solution}
The cases covered in the proof are not exhaustive.  Does he/she cover
the case when the added square has 7 neighboring squares?  Of course,
this doesn't really matter if one talks about the number of adjacent
edges, but this was not the approach taken here.

Another reasonable partial answer is that it was never clearly stated
where the inductive hypothesis was being used.
\end{solution}
}

\problempart Problem Set 2, Problem 8

\centerline{\resizebox{\textwidth}{!}{\includegraphics{figs/bad2.ps}}}

\omitsolution{
\begin{solution}
There are a number of correct answers for this problem.  There were
several cases where variables were defined haphazardly (like Q), or
incorrectly (like R=ricky is a set).  Also, the final answer is stated
without a real logical argument from the preceding step.

In part (b) there is no clear mention of a locally fair ranking (among other things).
\end{solution}
}

%END   Joe's problems

%BEGIN Ray's problems


%%%%%%%%%%%%%%%%%  S99 ps2

\problem 
Use mathematical induction to prove that 3 divides $n^3 + 2n$ whenever 
$n$ is a nonnegative integer.

\noindent
{\bf Solution:}

\noindent
We are proving a predicate $P(n)=\mbox{``$3\,|\,(n^3+2n)$''}$ for
$n\geq{0}$.

\medskip
\noindent 
%
{\em Base case:} $P(0)$ is true because $3\,|\,(0^3+2*0)=0$.  As a reminder,
we say $n\,|\,m$, i.e. that $n$ divides $m$, if $\exists {k\in{\sf
Z}}$ s.t. $m=kn$.

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some nonnegative integer.  Assume $P(n)$,
i.e.  that $3\,|\,(n^3+2n)$.  It follows that there is some integer
$k$ s.t. $n^3+2n=3k$.  We prove $P(n+1)$, i.e. that $3$ divides
$(n+1)^3+2(n+1)$ as follows:
$$(n+1)^3+2(n+1)=(n^3+2n)+3(n^2+3n+1)=3k+3(n^2+3n+1)=3k'$$
where $k'=k+(n^2+3n+1)$, and consequently, 
since $k'$ is an integer, $3$ divides $(n+1)^3+2(n+1)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
\problem 
Prove using mathematical induction that for all integers $n \geq 1$,
it is the case that $2^{n - 1} \leq 2^n - 1$.

\noindent
{\bf Solution:}

\noindent
We are proving a predicate $P(n)=\mbox{``$2^{n - 1} \leq 2^n - 1$''}$ for
$n\geq{1}$.

\medskip
\noindent 
%
{\em Base case:} $P(1)$ is true because $2^0=1\leq{1}=2^1-1$.

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some integer $n\geq{1}$.  Assume
$P(n)$, i.e. that $2^{n - 1} \leq 2^n - 1$.  We prove $P(n+1)$,
i.e. that $2^n \leq 2^{n+1} - 1$ as follows:
$$2^{n}=2^{n-1}*2\leq(2^n-1)*2=2^{n+1}-2\leq{}2^{n+1}-1$$



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

%Problem 6
\problem 
Which amounts of money can be formed using coins of denominations
11\$ and 13\$?  Prove your answer using a form of mathematical induction.

\noindent
{\bf Solution:}

\noindent
It is true that there for every ``big enough'' integer $n$, there
exists nonnegative integers $a,b$ s.t. $n=a*11+b*13$.  The following
could serve as an intuition for why this should be true: 

\noindent
Assume that some number $n$ can be represented as
\[
n=a*11+b*13
\]
for some nonnegative integers $a,b$.  Note that since $gcd(11,13)=1$,
then 
\[
1=k_1*11-m_1*13
\]
for some positive integers $k_1,m_1$.  It is also true that
\[
1=-k_2*11+m_2*13
\]
for some other positive integers $k_2,m_2$.  Therefore, if
$n=a*11+b*13$ is big enough, then, if $b\geq{m_1}$ then
\[
n+1=(a*11+b*13) + (k_1*11-m_1*13) = (a+k_1)*11 + (b-m_1)*13
\]
or, if $a\geq{k_2}$ then
\[
n+1=(a*11+b*13) + (-k_2*11-m_2*13) = (a-k_2)*11 + (b+m_2)*13
\]
If neither $a\geq{k_2}$ nor $b\geq{m_1}$ then $n=a*11+b*13$ is smaller
than $k_2*11+m_1*13$, and we will call such $n$ ``not big enough''.


First then, we have to find the $k_1,k_2,m_1,m_2$ above.  By doing gcd
computation, we get
\begin{eqnarray*}
6*11-5*13&=&1\\
-7*11+6*13&=&1\\
\end{eqnarray*}
In other words, $k_1=6, m_1=5, k_2=7, m_2=6$.  Now we see that we can
rephrase the above arguments into the inductive proof of a predicate
$P(n)=$``$n$ can be represented as $a*11+b*13$ for some nonnegative
integers $a,b$'', for $n\geq{142}$, because
$k_2*11+m_1*13=77+65=142$.

\medskip
\noindent 
%
{\em Base case:} $P(142)$ is true because, as noted above,
$142=7*11+5*13$.

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some integer greater or equal to
$142$.  Assume $P(n)$, i.e. that $n=a*11+b*13$ where $a,b$ are some
nonnegative integers.  We prove $P(n+1)$ as follows: First note that
either $a\geq{7}$ or $b\geq{5}$.  Otherwise, as noted above, $n$ would
be smaller than $142$.  In both cases we show that $n+1$ can be
represented as $a'*11+b'*13$ for some nonnegative integers $a',b'$: If
$a\geq{7}$ than $n+1=(a-7)*11+(b+6)*13$.  If $b\geq{5}$ than
$n+1=(a+6)*11+(b-5)*13$.  This completes the proof of $P(n+1)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
\problem 
Use mathematical induction to prove that for a positive integer $m$, 
if $a$ and $b$ are integers with $a \equiv b \pmod{m}$, then 
$a^k \equiv b^k \pmod{m}$
whenever $k$ is a nonnegative integer. 



\noindent
{\bf Solution:}

\noindent
We are proving a predicate $P(k)=$``for all positive integers $m$ and
all integers $a,b$, if $a \equiv b \pmod{m}$, then $a^k \equiv b^k
\pmod{m}$'' for $k\geq{0}$.

\medskip
\noindent 
%
{\em Base case:} $P(0)$ is true because $a^0=b^0=1$ for all $a,b$.

\medskip
\noindent 
%
{\em Inductive case:} Let $k$ be some integer $k\geq{0}$.  Assume
$P(k)$.  We prove $P(k+1)$ as follows: Let $m$ be a positive integer
and let $a,b$ be some integers s.t. $a \equiv b \pmod{m}$.  Then by
assumption $P(k)$ it follows that $a^k \equiv b^k\pmod{m}$.
Therefore we have that $a^{k+1}=a*a^k\equiv b*b^k=b^{k+1}\pmod{m}$,
which proves $P(k+1)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem Let the function $f$ applied to nonnegative integers be
defined by the recursive definition
\[f(x) = \left\{ \begin{array}{ll} 
                     0  & \mbox{if $x=0$} \\
                     2f(x-1) + 2 & \mbox{otherwise}
                  \end{array}
                  \right. \]
Prove by induction that the closed form definition for 
$f$ is $f(n) = 2^{n+1} - 2$. 


\noindent
{\bf Solution:}

\noindent
Here we are proving a predicate $P(n)=$``$f(n)=2^{n+1}-2$'' for
$n\geq{0}$.
\medskip
\noindent 
%
{\em Base case:} $P(0)$ is true because $f(0)=0=2^{0+1}-2$

\medskip
\noindent 
%
{\em Inductive case:} Let $n$ be some integer $n\geq{0}$.  Assume
$P(n)$.  Then $P(n+1)$ is true as well, because we have that
\[
f(n+1)=2f(n)+2=2(2^{n+1}-2)+2=2^{n+2}-2
\]
The first equality follows from the inductive definition of $f(\cdot)$
since $n+1\neq{0}$.  The second equality follows from the inductive
assumption $P(n)$.


%END   Ray's problems

%BEGIN Ivan's problems (spring '98)

%%%%%%%%
%pset2 problem1 from spring98 (variant of F97)

\problem

Prove by induction:
For all $x, n \in \naturals : x+1|x^{2n+1}+1$.

%%%%%%%% SOLUTION
%pset2 problem1 from spring98 (variant of F97)

\solution{
Prove: For all $x, n \in \naturals : x+1|x^{2n+1}+1$.

\bigskip
Proof by induction on $n$ with
\[P(n) ::\equiv \forall x \in \naturals: x+1|x^{2n+1}+1.\]
{\em Base Case:} $n=0$.  Then $2n+1=1$ and $P(0)$ is true since
$x+1|x^1+1$.

{\em Inductive Step:} Assume $P(n)$, so $x^{2n+1}+1 = p(x+1)$ for some
integer $p$.  We need to show that $x+1|x^{2(n+1)+1}+1$.
\begin{eqnarray*}
x^{2(n+1)+1}+1&=&x^2x^{2n+1}+1\\
&=&x^2(x^{2n+1}+1)-x^2+1\\
&=&x^2p(x+1)-(x-1)(x+1)\\
&=&(x^2p-(x - 1))(x+1).
\end{eqnarray*}
So $x+1$ is indeed a factor of $x^{2(n+1)+1}+1$. \qed
} %solution

%%%%%%%%
%pset2 problem2 from spring98 (from F96)

\problem
Prove that $1 \cdot 1! + 2 \cdot 2! + ... + n \cdot n! = (n+1)! - 1$
for all $n \in \naturals$.

%%%%%%%% SOLUTION
%pset2 problem2 from spring98 (from F96)

\solution{
Prove that
\[1 \cdot 1! + 2 \cdot 2! + ... + n \cdot n! = (n+1)! - 1,\]
for all $n \in \naturals$.

\bigskip
Proof by induction on $n$.

{\em Base Case:} $n = 0$. True since $\mbox{L.H.S.} = 0 = \mbox{R.H.S}$.

{\em Inductive Step:} Assuming the inductive hypothesis, we have
\begin{eqnarray*}
1\cdot 1!+2\cdot 2!+...+n\cdot n!+(n+1)\cdot (n+1)!&=&(n+1)!-1+(n+1)\cdot (n+1)!\\                                                &=&(n+1)!(1+n+1)-1\\
                                                   &=&(n+2)!-1
\end{eqnarray*}
as desired.
} %solution

%%%%%%%%
%pset2 problem3 from spring98

\problem
For $n \in \naturals$, define numbers $u_n$ by the equations:
\[u_0 = 2, u_1=3, u_{n+2} = 3u_{n+1}-2u_{n}.\]

Guess a general formula for $u_n$ and use mathematical induction to prove
your answer.

%%%%%%%% SOLUTION
%pset2 problem3 from spring98

\solution{
For $n \in \naturals$, define numbers $u_n$ by the equations:
\[u_0 = 2, u_1=3, u_{n+2} = 3u_{n+1}-2u_{n}.\]

Guess a general formula for $u_n$ and use mathematical induction to prove
your answer.


\bigskip

We claim, $u_n=2^n+1$ for all $n\in\naturals$.  We can prove it by strong
induction on $n$.

{\em Base Cases:} $n=0,1$. Then $u_0=2=2^0+1$ and $u_1 = 3 = 2^1+1$ as required.

{\em Inductive Step:} We may assume $n\geq 1$ and $u_k=2^k+1$ for all
$k\leq n$.  We shall show $u_{n+1}=2^{n+1}+1$.  Since $n-1 \geq 0$, the
value of $u_{n+1}$ is determined by the recurrence formula, namely,
\begin{eqnarray*}
u_{n+1}&=&3u_n-2u_{n-1}\\
&=&3(2^n+1)-2(2^{n-1}+1)\\
&=&3\cdot2^n-2\cdot2^{n-1}+1\\
&=&3\cdot2^n-2^n+1\\
&=&2\cdot2^n+1\\
&=&2^{n+1}+1
\end{eqnarray*} \qed
} %solution

%%%%%%%%
%pset2 problem4 from spring98 (from Rosen 3.3, prob 50)

\problem
A set of lines in the plane is said to be in {\em general position} when
no two of the lines are parallel, and no three intersect at a common
point.  Let $R_n$ be the number of regions into which $n$ lines in general
position divide the plane.  For example, $R_0 = 1, R_1 = 2, R_2 = 4$.
Explain, informally but clearly, why $R_{n+1} = R_n + (n+1)$.  Find a
simple formula for $R_n$ and prove your result by induction.


%%%%%%%% SOLUTION
%pset2 problem4 from spring98 (from Rosen 3.3, prob 50)

\solution{
A set of lines in the plane is said to be in {\em general position} when
no two of the lines are parallel, and no three intersect at a common
point.  Let $R_n$ be the number of regions into which $n$ lines in general
position divide the plane.  For example, $R_0 = 1, R_1 = 2, R_2 = 4$.
Explain, informally but clearly, why $R_{n+1} = R_n + (n+1)$.  Find a
simple formula for $R_n$ and prove your result by induction.


\bigskip
A set of $n$ lines in a general position divides the plane into $R_n$
regions.  When the $(n+1)^{st}$ line is added to the plane such that the
resulting set of lines is in a general position, the new line has to
intersect the previous $n$ lines, splitting in two each region above a
point of intersection, and also splitting in two the region below the
lowest point of intersection.  This splits $n+1$ regions into $2(n+1)$
regions, with a net increase of $n+1$ regions.  Therefore
$R_{n+1}=R_n+(n+1)$.

A general formula for $R_n$ is $\frac{n(n+1)}{2}+1$, as we prove by
induction.

{\em Base Case:} $n=0$.  There is one region, namely the whole plane, and
so thew number of regions equals $R_0$.

{\em Inductive Step:} Assuming $R_n=\frac{n(n+1)}{2}+1$, we need to show
that $R_{n+1}=\frac{(n+1)(n+2)}{2}+1$.

\begin{eqnarray*}
R_{n+1}&=&R_n+(n+1)\\
&=&\frac{n(n+1)}{2}+1+(n+1)\\
&=&(n+1)(\frac{n}{2}+1)+1\\
&=&\frac{(n+1)(n+2)}{2}+1
\end{eqnarray*}

as desired.
} %solution


%%%%%%%%
%pset2 problem5 from spring98 (adapted from unused F97 pset2)
%It seems this one may have been deleted for some reason...maybe don't use

%DELETED: Example 8 of Rosen, section 3.2, shows that every set of $n$
%elements contains $2^n$ subsets.
\problem  Prove that any finite set
of size $n>0$ has exactly $2^{n-1}$ subsets of even size.  For example,
$\{1,2\}$ has two subsets of even size: $\emptyset$ and $\{1,2\}$.  {\em
Hint}: Let $e$ be an element of a set $S$ of size $n+1$.  An even size
%revised ``is a'' into ``corresponds to''
subset of $S$ which does not contain $e$ corresponds to an even size
subset of $S - \{e\}$; an even size subset of $S$ which does contain $e$
corresponds to an odd size subset of $S - \{e\}$.
%SENTENCE ADDED:
So $\mbox{Even}(n+1) =
\mbox{Even}(n) + \mbox{Odd}(n)$.


%%%%%%%% SOLUTION
%pset2 problem5 from spring98 (adapted from unused F97 pset2)
%It seems this one may have been deleted for some reason...maybe don't use

\solution{
Prove that any finite set
of size $n>0$ has exactly $2^{n-1}$ subsets of even size.  For example,
$\{1,2\}$ has two subsets of even size: $\emptyset$ and $\{1,2\}$.  {\em
Hint}: Let $e$ be an element of a set $S$ of size $n+1$.  An even size
subset of $S$ which does not contain $e$ corresponds to an even size
subset of $S - \{e\}$; an even size subset of $S$ which does contain $e$
corresponds to an odd size subset of $S - \{e\}$.
So $\mbox{Even}(n+1) = \mbox{Even}(n) + \mbox{Odd}(n)$.

\bigskip
(Proof by induction.)  Let $\mbox{Even}(n)$ be the number of even-size
subsets of a set of size $n$.  Then we have to show $\forall n>0 :
\mbox{Even}(n)=2^{n-1}$.  To do this, we let $\mbox{Odd}(n)$ be the number
of odd-size subsets of a set of size $n$, and we prove by induction a
somewhat stronger fact:

{\em Induction hypothesis}: $P(n)::\equiv [\mbox{Even}(n)=2^{n-1} \wedge
\mbox{Odd}(n)=2^{n-1}]$.

{\em Base Case:} $n=1$.  There is one even-size subset, namely the empty
set, and one odd-size subset, namely the whole set.  So
$\mbox{Even}(1)=\mbox{Odd}(1)=1=2^{1-1}$.  So $P(1)$ is true.

{\em Inductive Step:} Let $A$ be a set of size $n+1$.  Let $e$ be an
element of $A$.  The number of even-size subsets in $A$ which do not
contain $e$ is equal to the number of even-size subsets in $A-\{e\}$.
Also, the number of even-size subsets of $A$ which do contain $e$ is equal
to the number of odd-size subsets in $A-\{e\}$.  Since the set $A-\{e\}$
is of size $n$, we have the following recurrence
\[\mbox{Even}(n+1)=\mbox{Even}(n)+ \mbox{Odd}(n).\]

Similarly, the number of odd-size subsets of $A$ which do not contain $e$
is equal to the number of odd-size subsets in $A-\{e\}$, and the number of
odd-size subsets of $A$ which do contain $e$ is equal to the number of
even-size subsets of $A-\{e\}$, so
\[\mbox{Odd}(n+1)=\mbox{Odd}(n)+ \mbox{Even}(n).\]

By induction we have that $\mbox{Even}(n)=2^{n-1}$ and
$\mbox{Odd}(n)=2^{n-1}$.  So
\[\mbox{Even}(n+1)=2^{n-1} +2^{n-1} = 2^n,\]
and
\[\mbox{Odd}(n+1)=2^{n-1} +2^{n-1} = 2^n,\]
which proves $P(n+1)$. \qed
} %solution

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

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

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

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

\ppart %SEE THE SOLUTION FOR A REFINED VERSION OF THIS PROBLEM:
Claim 2: For any positive integers $p, n, x_1, x_2,\ldots, x_n$, if
$p|x_1x_2\ldots x_n$, then $p|x_i$ for some $1\leq i\leq n$.

Proof by induction on $n$.

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

Induction hypothesis:
Now assuming the claim holds for $n$, we must prove it holds for $n+1$.

So suppose $p|x_1x_2\ldots x_{n+1}$.  If $p|x_1\ldots x_n$, then by the
inductive hypothesis we know that $p|x_i$ for some $1\leq i\leq n$, and we
have the desired $i$.  Otherwise, $p|x_{n+1}$, so $i = n+1$ will do. \qed

\eparts


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

\solution{
Pinpoint, and illustrate with a counterexample, {\em exactly} where the
following proofs go awry.

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

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

\bigskip

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|x_1x_2\ldots x_n$, then $p|x_i$ for some $1\leq i\leq n$.

\textbf{(Refined 2/27/98 by ARM)}:

Proof by strong induction on $n$.

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

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

So suppose $p|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|x_i$ for some $i < n$, then we have the
desired $i$.  Otherwise $p|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 | x_i$ for some $i = n$ or $i = n+1$. \qed
\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
} %solution


%%%%%%%%
%pset2 problem7 from spring98

\problem Define {\em constant-free one-occurrence} Boolean formulas,
{\em 1BF}'s for short,
inductively as follows:
\begin{itemize}
\item a variable is a 1BF.
\item if $F$ is a 1BF, then so is $\neg F,$
\item if $F$ and $G$ are 1BF's with no variables in common, then
%TYPO FIXED: changed \leftrightarrow to \implies:
$F \wedge G  \mbox{ and } F \implies G$ are 1BF's.
\end{itemize}

A {\em Boolean assignment}, $A$, is a mapping from variables to truth
values.  The {\em complement} of assignment $A$ is the assignment $B$ such
that $B(x) = \neg A(x)$ for all variables $x$ in the domain of $
A$.

Prove by induction that for all 1BF's, $F$, there is a Boolean
assignment $A$ for the variables of $F$ such that $F$ is true under
assignment $A$ and false under the complement of $A$.


%%%%%%%% SOLUTION
%pset2 problem7 from spring98

\solution{
Define {\em constant-free one-occurrence} Boolean formulas,
{\em 1BF}'s for short, inductively as follows:
\begin{itemize}
\item a variable is a 1BF.
\item if $F$ is a 1BF, then so is $\neg F,$
\item if $F$ and $G$ are 1BF's with no variables in common, then
$F \wedge G  \mbox{ and } F \rightarrow G$ are 1BF's.
\end{itemize}

A {\em Boolean assignment}, $A$, is a mapping from variables to truth
values.  The {\em complement} of assignment $A$ is the assignment $B$ such
that $B(x) = \neg A(x)$ for all variables $x$ in the domain of $A$.

Prove by induction that for all 1BF's, $F$, there is a Boolean
assignment $A$ for the variables of $F$ such that $F$ is true under
assignment $A$ and false under the complement of $A$.

\bigskip

We prove the theorem by strong induction on the length of the 1BF $F$, with
induction hypothesis $P(n)$:
\[\forall F:  \mbox{length}(F) = n \Rightarrow
[\exists A : (F \mbox{ is true under } A) \wedge (F \mbox{ is false under}
\overline{A})]\]
where $F$ ranges over 1BF's and $A$ ranges over Boolean assignments.  Here
we use the notation $\overline{A}$ for the complement of assignment $A$.

{\em Base Case:} $n=1$.  If $F$ is a 1BF of length 1 it must be a
variable.  Then the desired assignment is any $A$ such that
$A(F)=\mbox{true}$.

{\em Inductive Step:} Now assume $P(k)$ for all $k\leq n$.  To show
$P(n+1)$, let $F$ be a length $n+1$ 1BF for $n\geq 1$.  There are three
cases:

\begin{enumerate}
\item $F=\neg G$, where $G$ is a 1BF with length $\leq n$.  By inductive
hypothesis, there is an assignment $A_0$ such that $G$ is true under $A_0$ and
false under $\overline{A_0}$.  Then the desired assignment $A$ will be
$\overline{A_0}$.

\item $F=G\wedge H$, where $G$ and $H$ are formulas of length $\leq n$.
By inductive hypothesis there is an assignment $A_0$ such that $G$ is true
under $A_0$ and false under $\overline{A_0}$.  Also, there is an
assignment $A_1$ such that $H$ is true under $A_1$ and false under
$\overline{A_1}$.  Now let $A$ be the assignment which agrees with $A_0$
on the variables of $G$ and with $A_1$ on the variables of $H$.  Such an
$A$ exists because $F$ is a 1BF, so no variable occurs in both $G$ and
$H$.  Now under $A$ both $G$ and $H$ are true, and therefore $G\wedge H$
is true.  Likewise, $\overline{A}$ makes $G\wedge H$ false as required.

\item $F=G\rightarrow H$, where $G$ and $H$ are formulas of length $\leq
n$.  As in the previous case, there is an assignment $A_0 (A_1)$ such that
$G (H)$ is true under $A_0 (A_1)$ and false under $\overline{A_0}
(\overline{A_1})$.  So this time we let $A$ be the assignment which
agrees with $\overline{A_0}$ on the variables of $G$ and with $A_1$ on the
variables of $H$.  Now under $A$, $G$ is false and $H$ is true, so
$G\implies H$ is true; under $\overline{A}$, $G$ is true and $H$ is false, so
$G\implies H$ is false, as required.
\end{enumerate}
\qed
} %solution

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%55
%pset2 problem8 new spring01

\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   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\problem
% Ordinary induction, sum of series
Rosen 3.2, exercise 16.

\solution{
\medskip
\textbf{Solution:}
The proof is by induction.
Let $P(n)$ be the proposition that $1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + 
\ldots + n(n+1)(n+2) = \frac {n(n+1)(n+2)(n+3)}{4}$. \\
Base case: $n=1. 1 \cdot 2 \cdot 3 = 6; \frac {1(2)(3)(4)}{4} = 6.$ \\
Inductive step: By our inductive hypothesis, $1 \cdot 2 \cdot 3 + \ldots + 
n(n+1)(n+2) = \frac {n(n+1)(n+2)(n+3)}{4}$. Adding $(n+1)(n+2)(n+3)$ yields\\ 
\begin{eqnarray*}
\lefteqn{1 \cdot 2 \cdot 3 + \ldots + n(n+1)(n+2) +
(n+1)(n+2)(n+3)}\hspace{1.5in}  \\ 
& \mbox{}& \\
& = & \frac {n(n+1)(n+2)(n+3)}{ 4} + (n+1)(n+2)(n+3)\\
& = &\frac {n(n+1)(n+2)(n+3)}{4} + \frac {4(n+1)(n+2)(n+3)}{4}\\
& = &\frac {(n+4)(n+1)(n+2)(n+3)}{4}
\end{eqnarray*}
Hence $P(n) \implies P(n+1)$. QED. 
}  
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\problem
% Ordinary induction, divisibility
Velleman 6.1, problem 7
\solution{
\medskip

\textbf{Solution:}
The proof is by induction.
Let P(n) be the proposition that $64 | 9 ^ {n}-8n-1$.\\
Base case: $n = 1$. $9^n-8n-1=9-8-1=0$. $64 | 0$.\\
Inductive step: We must prove that $64 | 9 ^{n+1} -8(n+1)-1$.\\
\begin{eqnarray*}
9 ^{n+1} - 8(n+1) -1 & = & 9 ^{n+1} - 8n -9\\
& = & 9 (9 ^{n} -1) -8n\\
& = & 9 (9 ^{n} -1) -72n + 64n\\
& = & 9 (9 ^{n} -8n -1) + 64n\\
\end{eqnarray*}
Clearly, $64 | 64n$, and we know $ 64 | 9 ^{n} -8n -1$ from the 
inductive hypothesis. Hence 

\[ 64 | 9 ^{n+1} -8(n+1)-1 .\] 

So $P(n) \implies P(n+1)$. QED.
}
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\problem
% Ordinary induction, tiling
Velleman 6.2, problem 6
% Sorry -- I have no program handy to draw proper diagrams for this problem,
% and I don't know how to insert them in a LaTeX document.
% If someone could insert some properly drawn figures, I think that
% is pretty much essential to understanding the solution.
\solution{
\medskip

\textbf{Solution:}
The proof is by induction.\\
Let P(n) be the proposition that any equilateral triangle, that is cut into 
$4^n$ congruent equilateral triangles with one corner removed, can be tiled 
using tiles composed of three of the smaller congruent triangles.\\
Base case: $n=1$. With one corner removed, a single tile can be used to cover
the remaining area.\\
%\mbox{\epsfbox{figures/ps2P5BaseCase.ps}}
Inductive step: Consider a triangle, called T, cut into $4^{n+1}$ congruent equilateral
triangles. We can think of this triangle as being cut into four smaller 
equilateral triangles, which are each then cut into $4^n$ equilateral 
triangles. Remove the top corner of T. We know that we can tile the triangle
that contains the removed corner by the inductive hypothesis. Note that the
remaining area contains three triangles, who have corners that meet in the same
place; namely, the bottom of T, directly below the removed corner. If we
consider each of these triangles with the touching corners removed, then the
inductive hypothesis says that we can tile each one separately. To complete
the tiling, simply use a single tile to cover the three adjacent removed 
corners. See Figure 1.
\begin{figure}
\centering
\mbox{\epsfbox{figures/ps2P5inductive.ps}}
\caption{\textbf{Figure 1:} The original triangle T. Dark lines indicate borders of the four smaller triangles; light lines indicate borders of the $4^n$ triangles that the smaller triangles are cut into. The black triangle is the removed corner; the gray triangles indicate the corners that are removed from the smaller triangles in order to apply the inductive hypothesis, which are then covered by a single tile.}
\end{figure}
\\
\\
\\
}
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
  
\problem
% Strong induction 
\ppart What is the smallest natural number $h$ such that towers of all heights
greater than or equal to $h$ can be built out of blocks of height 5,
6, and 9?

\solution {
\medskip
\textbf{Solution:}
14.} 
\ppart Prove that $h$ is the smallest such number.

\solution{
\medskip
\textbf{Solution:}
 This question has two parts: prove that $h$ satisfies the requirement, and
 prove that no smaller number also satisfies the requirement. The first part
 is asked in part c. To prove the second part, we show that a tower
 of height 13 cannot be made with our given blocks, via a case
 analysis.  Observe that if there were a way to build a tower of
 height 13, then this tower could have at most two blocks of heights 5
 or 6.  If there were more blocks of these heights, then the tower
 would be too long.  Similarly, any valid solution can have at most
 one block of height 9.  We can enumerate all the possible
 configurations consisting of at most two blocks of height 5 or
 6, and at most one block at height 9, and check that none of them add
 up to thirteen.  We can actually eliminate many of these cases.   

 Hence no natural number
 equal to or less than 13 satisfies the given requirements. Therefore, if 14
 does satisfy the requirements, it must be the smallest such number.}
\ppart Prove that all heights $h$ or greater can be built of of blocks
of height 5, 6, and 9.

\solution{
\medskip
\textbf{Solution:}
 The proof is by strong induction.
 Let P(n) be the proposition that all natural numbers,
 starting with our smallest base case, going up to and including n, can be 
 formed by adding 5, 6, and 9.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Base cases: 14 is formed by 5+9.\\
 \> 15 is formed by 6+9 (or 5+5+5).\\
 \> 16 is formed by 5+5+6.\\
 \> 17 is formed by 5+6+6.\\
 \> 18 is formed by 9+9 (or 6+6+6).\\
\end{tabbing}
Inductive step: Assume P(n) to prove P(n+1). Note that we have proved P(n) 
true for five consecutive base cases. Hence, by our inductive hypothesis, 
we can always create a tower of height n+1-5. We can then simply add a block 
of height 5 to that tower, creating a tower of height n+1. P(n) $\implies$ P(n+1). QED.
}
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  


\problem
% Strong induction, recursive definitions (Fibonacci)
Velleman 6.4, problem 5 (a) (d) \\
{Note:} By convention, the book considers $F_1$ to be 1, $F_2$ to be 1, $F_3$
to be 2, and so on. In other places, you may see $F_0 = 1, F_1 = 1, F_2 = 2$,
etc.
\\

\solution{
\medskip
\textbf{Solutions:}\\
\textbf{(a)} The proof is by induction. 
Let $P(n)$ be the proposition that $\sum_{i=0}^n F_i = F_{n+2} - 1$.\\ 
Base case: $n=1$. 
\begin{eqnarray*}
\sum_{i=0}^1 F_i & = & F_0 + F_1\\
        & = & F_1\\
        & = & 1\\
        & = & 2 - 1\\
        & = & F_3 - 1\\
        & = & F_{1+2} -1\\
\end{eqnarray*}
Inductive step: We must prove $\sum_{i=0}^{n+1} F_i = F_{n+3} - 1$.
\begin{eqnarray*}
\sum_{i=0}^{n+1} F_i & = & \sum_{i=0}^n F_i + F_{n+1}\\
& = & F_{n+2} - 1 + F_{n+1} \mbox {    by the inductive hypothesis}\\
& = & F_{n+3} - 1 \mbox {    by the definition of $F_n$}\\
\end{eqnarray*}

$P(n) \implies P(n+1)$. QED.

\iffalse  %% COMMENTS OUT EVERYTHING UNTIL THE \fi COMMAND%%

\textbf{(c)}  The proof is by induction.
Let $P(n)$ be the proposition that $\sum_{i=0}^n F_{2i+1} = F_{2n+2}$.\\
Base case: $n = 1.$ 
\begin{eqnarray*}
\sum_{i=0}^1 F_{2i+1} & = & F_1 + F_3\\
        & = & 1 + 2 \\
        & = & 3\\
        & = & F_4\\
\end{eqnarray*}
Inductive step: We must prove $\sum_{i=0}^{n+1} F_{2i+1} = F_{2n+4}$.
\begin{eqnarray*}
\sum_{i=0}^{n+1} F_{2i+1} & = & \sum_{i=0}^n F_{2i+1} + F_{2n+3}\\
& = & F_{2n+2} + F_{2n+3} \mbox {    by the inductive hypothesis}\\
& = & F_{2n+4} \mbox {    by the definition of $F_n$}\\
\end{eqnarray*}
$P(n) \implies P(n+1)$. QED.

\fi
%% STOP COMMENTING EVERYTHING OUT.

\textbf{(d)}  We can construct the following table:
\begin{eqnarray*}
n & F_n & \sum_{i=0}^n F_{2i}\\
1 & 1   & 1\\
2 & 1    & 4\\
3 & 2    & 12\\
4 & 3    & 33\\
5 & 5    \\
6 & 8    \\
7 & 13   \\
8 & 21   \\
9 & 34   \\
\end{eqnarray*}
Hmm. It looks like $\sum_{i=0}^n F_{2i}$ might be $F_{2n+1} -1$. So let's take
a crack at proving that.\\

The proof is by induction.\\
Let $P(n)$ be the proposition that $\sum_{i=0}^n F_{2i} = F_{2n+1} - 1$.\\
Base case: n = 1. 
\begin{eqnarray*}
\sum_{i=0}^n F_{2i} & = & F_0 + F_2\\
        & = & F_2\\
        & = & 1\\
        & = & 2 - 1\\
        & = & F_3 - 1\\
\end{eqnarray*}
Inductive step: We must prove $\sum_{i=0}^{n+1} F_{2i} = F_{2n+3} - 1$.
\begin{eqnarray*}
\sum_{i=0}^{n+1} F_{2i} & = & \sum_{i=0}^n F_{2i} + F_{2n +2}\\
& = & F_{2n+1} -1 + F_{2n+2} \mbox {    by the inductive hypothesis}\\
& = & F_{2n+3} -1 \mbox {    by the definition of $F_n$}\\
\end{eqnarray*}
$P(n) \implies P(n+1)$. QED.

\iffalse  %% START COMMENTING OUT EVERYTHING UNTIL \fi command %%

\textbf{(e)}  The proof is by strong induction on n. (surprise!)\\
Let $P(n)$ be the proposition that $F_{m+n} = F_{m-1}F_n + F_mF_{n+1}$ for all
natural numbers $\leq$ n.\\
Base case: n = 1.
\begin{eqnarray*}
F_{m+n} & = & F_{m+1}\\
    & = & F_{m-1} + F_m \mbox {    by the definition of $F_n$}\\
    & = & F_{m-1}(1) + F_m(1)\\
    & = & F_{m-1}F_1 + F_mF_2\\
\end{eqnarray*}
Inductive step: We must prove $F_{m+n+1} = F_{m-1}F_{n+1} + F_mF_{n+2}$.
\begin{eqnarray*}
F_{m+n+1} & = & F_{m+n} + F_{m+n-1} by the definition of F_n\\
& = & (F_{m-1}F_n + F_mF_{n+1}) + (F_{m-1}F_{n-1} + F_mF_{n}) \mbox {     by the inductive hypothesis}\\
& = & F_{m-1}(F_n + F_{n-1}) + F_m(F_{n+1} + F_{n})\\
& = & F_{m-1}F_{n+1} + F_mF_{n+2} \mbox {    by the definition of $F_n$}\\
\end{eqnarray*}
$P(n) \implies P(n+1)$. QED.
}

\fi
%%  END COMMENTING OUT.
%%%%%%%%%%%%%%%%%%%%%%%%% Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\problem  
\textbf{Induction and Recursive Algorithms}
\bparts
\ppart Rosen \S 3.4, Exercise 18\\
Devise a recursive algorithm to find the $n$th term of the sequence
defined by $a_0 = 1, a_1 = 2, a_2 = 3$, and $a_n = a_{n-1} + a_{n-2} + a_{n-3}$,
for $n=3,4,5,\ldots$.\\
\solution{


\medskip
\textbf{Solution:}\\


\textbf{procedure} \textit{sum-sequence} ($n$:nonnegative integers)\\
\textbf{if} (n$<$3) \textbf{then} \textit{sum-sequence}($n$):=$n+1$;\\
\textbf{else} \textit{sum-sequence}($n$):=\textit{sum-sequence}($n-1$)+
\textit{sum-sequence}($n-2$)+\textit{sum-sequence}($n-3$)\\
}
\eparts                        
\problem  
\textbf{Induction and Recursive Algorithms}
\bparts
\ppart Rosen \S 3.4, Exercise 18\\
Devise a recursive algorithm to find the $n$th term of the sequence
defined by $a_0 = 1, a_1 = 2, a_2 = 3$, and $a_n = a_{n-1} + a_{n-2} + a_{n-3}$,
for $n=3,4,5,\ldots$.\\
\solution{


\medskip
\textbf{Solution:}\\


\textbf{procedure} \textit{sum-sequence} ($n$:nonnegative integers)\\
\textbf{if} (n$<$3) \textbf{then} \textit{sum-sequence}($n$):=$n+1$;\\
\textbf{else} \textit{sum-sequence}($n$):=\textit{sum-sequence}($n-1$)+
\textit{sum-sequence}($n-2$)+\textit{sum-sequence}($n-3$)\\
}
\eparts      
%%%%%%%%%%%%%%%%%%%%%%%%% END Fall00 Problem Set 3%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%% Spring 01 Tutorial 4 %%%%%%%%%%%%%%%%%%%%%%%%%%5
\renewcommand{\labelenumi}{\alph{enumi})}
 
%from fall00
\problem \textbf{Well-ordering}
 
%\textbf{Rosen 3.2, Ex. 58:} 
The well-ordering property can be used to show that there is a unique
greatest common divisor of two positive integers. Let $a$ and $b$
be positive integers, and let $S$ be the set of positive integers of the
form $as+bt$, where $s$ and $t$ are integers.
\begin{enumerate} \setlength{\itemsep}{0pt} \item Show that $S$ is nonempty.
\item Use the well-ordering property to show that $S$ has a smallest
  element $c$.
\item Show that if $d$ is a common divisor of $a$ and $b$, then $d$ is
  a divisor of $c$.
\item Show that $c \mid a$ and $c \mid b$. (Hint: First, assume that
  $c \nmid a$.  Then $a=qc+r$, where $0<r<c$. Show that $r \in S$,
  contradicting the choice of $c$.)
\item Conclude from (c) and (d) that the greatest common divisor of
  $a$ and $b$ exists. Finish the proof by showing that this greatest
  common divisor of two positive integers is unique.
\end{enumerate}

\renewcommand{\labelenumi}{\alph{enumi})}
\solution{
\medskip
\textbf{Solutions:}\\

\begin{enumerate} \setlength{\itemsep}{0pt}
\item For example, just set $s=1$, and $t=1$.  Then $as+bt = a+b$,
  which is a positive integer by our definitions of $a$ and $b$.
\item The Well Ordering Property states that every non-empty set of
  non-negative integers has a smallest member.  Since we just showed
  in part a that the set $S$ is non-empty, it must have a smallest
  member, which we may call $c$.
\item If $d$ divides $a$ and $b$, then $d$ divides $as$ and $bt$ for
  any positive integers $a$ and $b$.  Therefore, $d$ also divides the
  sum $as+bt$.  Since $c \in S$, c must be such a sum, by our
  definition of membership in $S$.  Therefore, $d$ can divide $c$.
  
  
\item We will just show $c \mid a$, as the argument is identical to
  show $c \mid b$.\\
  Proof by Contradiction.\\
  Assume for the purpose of contradiction that $c \nmid a$.\\
  If $c$ does not evenly divide into $a$, then we can write the expression $a = qc + r$, for some postive integer $r$, where $0<r<c$.\\
  We can rewrite this in terms of $r$: $r=a-qc$.\\
  Now, since $c \in S$, we know that $c$ is of the form $c=as+bt$, for some integral values of $s$ and $t$.  Rewriting our expression for $r$ again, we get:\\
  $r=a-qc = a-q(as+bt)=a-aqs-qbt=a(1-qs)+b(-qt).$ But now we are done,
  because we have expressed the positive integer $r$ as a linear
  combination with integer coefficients of $a$ and $b$.  This means
  that $r \in S$, which we know is not possible since $r<c$.  Thus, we
  have a contradiction, and our assumption that $c \nmid a$
  must be wrong, so we can conclude that $c \mid a$.
  
\item Finally, by part (d), $c$ is a divisor of both $a$ and $b$.
  Furthermore, from part (c) we know that any divisor of both $a$ and
  $b$ is also a divisor of $c$.  This means that every common divisor
  of $a$ and $b$ is no greater than $c$, and so $c$ is the greatest
  common divisor of $a$ and $b$.  To see that the greatest common
  divisor of a number is unique, one just needs to note that it makes
  no sense to have two numbers, each of which is greater than the
  other.
\end{enumerate}
}                                  




           
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
















%END   George's problems

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

%BEGIN Tina's problems
%Fall 99

%%%%%%%%%%%%%%%%%%
%problem set 1, problem 4

\problem \textbf{Simple Induction}
\bparts

\ppart \S 3.2, Exercise 18.

\solution{The base case, $n=2$, is the true statement that $5/4$ is less than $6/4$.
Assume the inductive hypothesis. Then we have
\begin{eqnarray*}
1+\frac{1}{4}+\ldots+\frac{1}{n^2}+\frac{1}{(n+1)^2}& < & 2-\frac{1}{n}
             +\frac{1}{(n+1)^2}\\
& = & 2 - \left(\frac{1}{n} - \frac{1}{(n+1)^2}\right)\\
& = & 2 - \left(\frac{n^2 + 2n + 1-n}{n(n+1)^2}\right)\\
& = & 2 - \frac{n^2 + n}{n(n+1)^2}-\frac{1}{n(n+1)^2}\\
& = & 2 - \frac{1}{n+1} - \frac{1}{n(n+1)^2}\\
& < & 2 - \frac{1}{n+1}.
\end{eqnarray*}}

\ppart \S 3.2, Exercise 32.

\solution{The answer is that we can form all multiples of $5$ cents greater than
or equal to $20$ cents, as well as $10$ cents. (The fact that $5$ cents and
$15$ cents cannot be obtained is clear.) To prove this by induction, we
check the base case, that $20$ cents can be formed (with two
dimes). Next assume the inductive hypothesis, that we can form $5k$
cents (where $k\ge 4$); we need to show how to obtain $5(k+1)=5k+5$ cents. If
a quarter is used to form $5k$ cents, then we can replace it by three
dimes, increasing the amount of money by the desired $5$ cents. On the
other hand, if a quarter is not used, then at least two dimes must be
used (since $5k\ge 20$), so we can replace two dimes by a quarter, again
increasing the amount of money by the desired $5$ cents.}

\ppart \S 3.2, Exercise 34.

\solution{We proceed by induction. The base case is true, since
$1\cdot 2^1 = (1-1)2^{1+1}+2$. We assume the inductive hypothesis, that
\[
\Sigma_{k=1}^{n}k\cdot 2^k = (n-1)2^{n+1}+2,
\]
and try to prove that 
\[
\Sigma_{k=1}^{n+1}k\cdot 2^k = n\cdot 2^{n+2}+2.
\]
Splitting the left-hand side into its first $n$ terms followed by its
last term and invoking the inductive hypothesis, we have
\begin{eqnarray*}
\Sigma_{k=1}^{n+1}k\cdot 2^k & = & \left(\Sigma_{k=1}^{n}k\cdot 2^k \right)+
        (n+1)2^{n+1}\\
& = & (n-1)2^{n+1} + 2 + (n+1) 2^{n+1}\\
& = & 2n\cdot 2^{n+1}+2\\
& = & n\cdot 2^{n+2}+2,
\end{eqnarray*} 
as desired.}

\eparts

% problem set 2, problem 5

\problem \textbf{Induction}

Do the following problems from Rosen :

\bparts

\ppart \S 3.2, Exercise 40.

\solution{We prove this by induction on $k$. The base case $k=0$ is the 
trivial statement that $1\equiv 1 \pmod{m}$. Suppose that the statement
is true for $k$. We must show it for $k+1$. So let $a\equiv b \pmod{m}$. By
the inductive hypothesis we know that $a^k\equiv b^k \pmod{m}$. Then we
apply Theorem 7 from Section 2.3 to conclude that $a\cdot a^k\equiv b\cdot 
b^k \pmod{m}$, which by definition says that $a^{k+1}\equiv b^{k+1} \pmod{m}$,
as desired.
}

\ppart \S 3.3, Exercise 22(c).

\solution{There are several ways to do this.  One that is suggested by
Horner's method is as follows.  We will assume that the variable for these
polynomials is the letter $x$.  All integers are in $S$ (this base case
gives us all the constant polynomials); if $p(x)\in S$ and $n$ is any
integer, then $x p(x)+n$ is in $S$.  Another method constructs the
polynomials term by term.  Its base case is to let $0$ be in $S$; and its
inductive step is to say that if $p(x)\in S$, $c$ is an integer, and $n$
is a nonnegative integer, then $p(x)+c x^n$ is in $S$.
}

\eparts

%problem set 2, problem 7

\problem \textbf{Induction}\label{ax+by:induct}
Suppose $a,b \in \naturals$ and $a>0$.  Prove by induction on $a$ that for
all $b\leq a$, there are $x,y \in \integers$ such that $ax+by= \gcd
(a,b)$.

\solution{The proof is actually by strong induction.
{\bf Inductive Hypothesis:} 
\[P(a)::= \forall b\le a \exists x,y\in Z(\gcd(a,b)=a x +b y).
\]

\begin{proof}
{\bf Base Case:} $a=1$.  So $b=0$ or $b=1$.  In either case,
$\gcd(a,b)=a$, so letting $x=1$, $y=0$, proves $P(a)$.

{\bf Inductive Step:} We want to prove $P(a+1)$ assuming $P(n)$ holds for
all $n \leq a$.

If $b=0$ or $b=a+1$, then $P(a+1)$ holds as in the base case, so we may
assume $0<b\leq a$.  Since $b>0$, we can find the quotient, $q$, and
remainder, $r$, of $a+1$ divided by $b$, namely, $a+1 =qb + r$ for some
$q,r \in \integers, 0 \leq r < b \leq a$.

Now we know from the discussion in the text of Euclid's GCD algorithm that
$\gcd(b,r)=\gcd(a+1,b)$.  By induction hypothesis, $P(b)$, there are
integers $x',y'$ such that $gcd(b,r)=b x' + r y'$.  Therefore
\begin{eqnarray*}
\gcd(a+1,b) & = & \gcd(b,r)\\
     & = & b x' + r y'\\
& = & b x' + ((a+1)-q b) y'\\
& = & (a+1) y' + b (x' - q y').
\end{eqnarray*}
So letting $x=y'$ and $y = (x' - q y')$ proves $P(a+1)$.
\end{proof}
}

%END   Tina's problems


%%Example from Spring99, tutorial 2
\subsubsection*{Well-Ordering Example}

\problem The well-ordering principle gives an alternate proof of the following
familiar fact.

\begin{mytheorem}
The square root of 2 is irrational.
\end{mytheorem}

\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that the square root of 2 is rational.  Then $\sqrt{2}$
is equal to $m / n$ for some integers $m$ and $n > 0$.

Let $S$ be the set of all positive integers $k$ such that $k
\sqrt{2}$ is an integer.  The set $S$ is non-empty, because it
contains $n$.  Thus, by the well-ordering principle, the set $S$
contains a smallest element $k_0$.

Now consider the number $k_0 (\sqrt{2} - 1)$.  This is an integer,
since it is equal to $k_0 \sqrt{2} - k_0$, and both of these terms are
integers.  Furthermore, it is positive, since it is equal to
$k_0 \cdot 0.414\ldots$.  Finally, multiplying this number by
$\sqrt{2}$ gives $2 k_0 - k_0 \sqrt{2}$, which is again an integer
because both terms are integers.  Therefore, the number $k_0 (\sqrt{2}
- 1)$ is an element of $S$ that is smaller than $k_0$.  This is a
contradiction, and so $\sqrt{2}$ must be irrational.
\end{proof}

\textbf{Class Exercise}: How could this argument be generalized to prove
that the square root of an every non-square is irrational?  Why does this
generalized argument not prove that $\sqrt{4}$ is irrational?

\emph{Answer}: Instead of arguing with $\sqrt{2}$, make the argument with
$\sqrt{n}$.  The main trick is that the second paragraph should begin,
``Now consider the number $k_0 (\sqrt{n} - \lfloor \sqrt{n} \rfloor)$''.
If $n$ is a perfect square, then the proof breaks down in the next
sentence; the number $k_0 (\sqrt{n} - \lfloor \sqrt{n} \rfloor)$ is not
positive in this case, but zero.

%from Spring99 tutorial

\problem I recently went to a party with my Significant Other; there
were $12$ other couples there.  A lot of handshaking happened, but of
course no one shook hands with their Significant Other.  At the end,
it turned out that for every $k$ from $0$ to $22$, someone other than
me had shaken hands with exactly $k$ people.  How many people did I
shake hands with?  Prove your answer.

\textbf{Solution}:
We will prove the following for a set of $n$ couples:
\begin{theorem}
Suppose at a party for $n$ couples (total) it turns out that
someone other than me has shaken $k$ hands for every $k$ from $0$ to $2n-2$. 
Then I must have shaken $n-1$ hands.
\end{theorem}

\begin{proof}
By induction on $n$.

\emph{Base case, $n=1$}: There are no other couples. My wife has shaken
$0$ hands (can't shake with me). I have shaken $0$ hands ($=n-1$). (some
party!)

\emph{Induction case}: Assume $P(n-1)$ is true for some $n>1$. To prove
$P(n)$, consider a party with $n$ couples.

Someone has shaken $2n-2$ hands, i.e., with everyone in the room except
themselves and their spouse. Therefore everyone else but this couple has
shaken hands at least once. So the one who hasn't shaken hands at all must
be this person's spouse. $2n-2$ is paired with $0$.  Consider the subparty
of the remaining $n-1$ couples. I must be in this group since there cannot
be two people who shook hands $2n-2$ times or $0$ times. Consider the
number of times this group of people has shaken hands among themselves,
i.e., not counting handshakes with the $2n-2, 0$ couple. Then the number
of handshakes I see is every number between $0$ and $2n-4$. This is
because this group of people has original handshake counts of
$1,2,3,\ldots, 2n-3$. Since everyone shakes the $2n-2$ person's hand once,
we are left with handshake counts of $0,1,\ldots,2n-4$.  This is exactly
the premise of $P(n-1)$. So by the I.H. I must have shaken $n-2$ hands
within this group. Adding the one handshake with the $2n-2, 0$ couple, I
must have shaken a total of $n-1$ hands.

\end{proof}

Note that there are 24 people (12 couples)in this case.  So $n=12$, and
the answer is that I shook 11 hands.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%------------------------------------------------
% source: pset fall00
% topic: structural induction, strings, proofs
% last used: karger s01 pset3
% Added by Jaime

\problem We define the family $\T$ of number search trees as follows:
\begin{enumerate}
\item
  Any single number $x$ is in $\T$.
\item If $T$ is in $\T$, and $x$ is a number greater than any number
  in $T$, then the structure formed by pointing an arrow
  labelled ``left'' from $x$ to $T$ is also in $\T$.
n\item If $T$ is in $\T$, and $x$ is a number smaller than any number
  in $T$, then the structure formed by pointing an arrow
  labelled ``right'' from $x$ to $T$ is also in $\T$.
\item If $T$ and $T'$ are in $\T$, and a number $x$ is larger than
  every number in $T$ but smaller than every number in $T'$, then the
  structure formed by attaching an arrow labelled ``left'' from $x$
  to $T$ and an arrow labelled ``right'' from $x$ to $T'$ is also in
  $\T$.
\end{enumerate}
In all cases above, the number $x$ is called the \emph{root} of the
tree that is formed.  Since the descriptions above are wordy, you may
wish to introduce some notation, like makeleft$(T,x)$ to denote the
thing built up according to the first recursive rule.  Likewise,
makeright$(x,T)$, makeboth$(T,x,T')$.

\ppart How many different number search trees with four nodes will be
in $\T$ if our domain consists of the numbers 1, 2, 3 and 4?  Give an
example of how one such tree might be constructed using the structural
definition.

\solnospace{Consider the number search tree with each number at the
root.  If 1 is at the root, 2, 3 and 4 must be to its right.  There
are five different number search trees that can be made with 2, 3 and
4, so there are three different trees that can be made with 1 at the
root.  If 2 is at the root, 1 must be to its left, and 3 and 4 to its
right.  Since there are two different number search trees that can be
made with 3 and 4, there are two different trees that can be made with
2 at the root.  When 3 is at the root, the case is very similar to 2,
and when 4 is at the root, the case is very similar to 1.  This means
there are 14 number search trees that can be made containing all of
the numbers 1, 2, 3 and 4.
\begin{center}
\begin{picture}(60,80)
\put(7,45){1}
\put(10,40){\circle*{3}} \put(10,40){\line(1,1){20}}
\put(27,65){2}
\put(30,60){\circle*{3}} \put(30,60){\line(1,-1){20}}
\put(47,45){4}
\put(50,40){\circle*{3}} \put(50,40){\line(-1,-2){10}}
\put(30,20){3}
\put(40,20){\circle*{3}}
%\put(10,40){\circle*{3}} %\put(10,40){\line(2,3){20}}
%\put(30,10){\circle*{3}}
\end{picture}\\
An example of a number search tree for the numbers 1, 2, 3 and 4.
\end{center}
}

Now consider the following recursive algorithm for checking whether a
certain number is present in a tree $T$.
\begin{tabbing}
else\=else\=else\=else\=\kill

Algorithm Member$(q,T)$\\
\\
\>Let $x$ be the root of tree $T$\\
\> {\bf if} $x=q$ {\bf then}\\
\> \> {\bf return} YES\\
\> {\bf else} \\
\> \> {\bf if} $q<x$ {\bf and} $x$ has a ``left'' arrow to tree $T'$ {\bf
  then}\\
\> \> \> {\bf return} Member$(q,T')$\\
\> \> {\bf else if} $q>x$ {\bf and} $x$ has a ``right'' arrow to tree $T'$ 
{\bf
  then}\\
\> \> \> {\bf return} Member$(q,T')$\\
\> \> {\bf else}\\
\> \> \> {\bf return} NO\\
\end{tabbing}

\ppart Prove that a call to member$(q,T)$ returns YES if and only if
$q$ is a number in the number search tree $T$.

\newcommand{\membern}{\hbox{member}}
\newcommand{\makeleft}{\hbox{makeleft}}
\newcommand{\makeright}{\hbox{makeright}}
\newcommand{\makeboth}{\hbox{makeboth}}

\solution{ We use structural induction. We use $x<T$ to mean
  $x<\mbox{all numbers in }T$, and define $x>T$ similarly. We get four
  cases, one for each production rule.
\begin{enumerate}
\item
For a single-node tree $T$ with root $x$, if $q\in T$, $q=x$ and 
$\hbox{member}(q,T)$ returns YES. If $q\notin T$, since there are no 
arrows
from $x$, the final else is taken and $\hbox{member}(q,T)$ returns NO.
\item
Fix $T$, and assume $\forall q$, $\hbox{member}(q,T)$ returns YES iff 
$q\in T$.
We need to show that $\forall q,\forall x>T$,
$\membern(q,\makeleft(T,x))$ returns YES iff $q\in\makeleft(T,x)$.
If $q\in\makeleft(T,x)$, $q=x$ or $q\in T$. If $q=x$,
$\membern(q,\makeleft(T,x))$ immediately returns YES. If $q\in T$, $q<x$
and since $x$ has a left arrow to $T$, $\membern(q,T)$ is returned,
which is YES by inductive assumption. If $q\notin\makeleft(T,x)$, then
$q\ne x$ and $q\notin T$, so either the final else is taken and NO
returned or $\membern(q,T)$ is returned, returning NO by inductive
assumption.
\item
Similar to 2.
\item
Fix $T$, $T'$ and assume $\forall q$, $\membern(q,T)$ returns YES iff
$q\in T$ and $\membern(q,T')$ returns YES iff $q\in T'$. We need to
show that $\forall q$, $\forall x\suchthat x>T\wedge x<T'$,
$\membern(q,\makeboth(T,x,T'))$ returns YES iff
$q\in\makeboth(T,x,T')$. If $q\in\makeboth(T,x,T')$, there are 3
cases. Case 1: $q=x$, so member returns YES. Case 2: $q\in T$, so
$q<x$, $x$ has a left arrow to $T$, and $\membern(q,T)$ is returned,
which is YES by inductive assumption. Case 3: $q\in T'$, by similar
reasoning YES is returned. If $q\notin\makeboth(T,x,T')$, then $q\ne
x$, $q\notin T$, and $q\notin T'$, so either NO is returned
immediately or $\membern(q,T)$ or $\membern(q,T')$ is returned, which
are NO by inductive assumption.
\end{enumerate}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%------------------------------------------------
% source: spring 99, pset 3
% topic: structural induction, list
% last used: karger spring 01 tut3

%\ignore'd by Joe 2/18--this could be a good problem
%but I think needs reworking. If we really want to make
%it correspond to the ``structural induction'' and recurs. structure
%definition stuff then the definition of the game tree should be more 
%formal with base cases and combination rules. Also, the way it's
%described now, since nodes correspond to situations in the game,
%it is a directed graph, not a tree.

\problem Many two-person games in which players alternate moves---like
chess, checkers, and tic-tac-toe---can be represented abstractly by
\emph{game trees}.

The root of a game tree has children labeled with each of the possible
initial moves by the first player.  For example, in the game tree for
tic-tac-toe, the root has nine children corresponding to the nine
boxes that the first player could mark with an~X.  Each of these
nodes has eight children corresponding to the eight remaining boxes
which the second player could mark with an~O, and so on.

In general, each node corresponds to a situation in the game, and its
children correspond to each of the possible moves by the player whose
turn it is in that situation.  The leaves of the tree correspond to
situations where no moves are possible---the game is over.  The leaves
are labelled with \emph{win}, \emph{lose}, or \emph{draw}, indicating
the outcome for the first player.  (A win for one player is a loss for
the other---no ``everybody wins''-type games at MIT. \texttt{:-)})

A \emph{strategy} for a player in a game specifies which move the
player should make in any situation where it is that player's turn to
move.  A \emph{winning} stategy ensures that the player will win no
matter what moves the other player makes.  Similarly, a
\emph{non-losing} stategy ensures that the player will \emph{win or
  draw} no matter what moves the other player makes.

For example, most elementary school children figure out non-losing
strategies in tic-tac-toe for \emph{both} the first and second players.
There is no winning strategy in tic-tac-toe for either player.  No one
knows if any player has a winning strategy for chess or checkers.
However, on general principles, we can be sure that at least one player
has a non-losing strategy.

More formally, let's define a family of Game Trees $T$ as follows:

1.  A single ``root'' node labeled with \emph{win}, \emph{lose}, or 
\emph{draw} is 
in $T$.

2.  An unlabelled root node connected to each element of a set of mutually 
disjoint
 game trees (not containing the root node either) called the ``immediate 
subgames''
 of the game tree is in $T$.


\ppart Prove that for any two-person game with a finite game
tree, at least one of the players has a non-losing strategy.

\solnospace{
\begin{proof}
The proof is by structural induction on the game tree.
Let $P(T)$ be the proposition that for a game tree, $T$, at least one
of the players has a non-losing strategy.

{\bf Base case:}
For the base case of a single-node tree, the node is labeled \emph{win},
\emph{lose}, or \emph{draw}.  If the node is labeled \emph{win} or
\emph{draw}, then the first player has a non-losing strategy.  If
the node is labeled \emph{draw} or \emph{lose}, then the second
player has a non-losing strategy.  In both cases, there is a player with
a non-losing strategy.

{\bf Structural Induction Step:} In the inductive step, we want to prove
that for any game tree, $T$, if $P(T')$ holds for each immediate
subgame, $T'$, of $T$, then $P(T)$ holds.

So suppose $T$ is a game tree and there is a non-losing strategy for at
least one of the players for every immediate subgame, $T'$, of $T$.

Let $A$ be the player who moves first in the game defined by $T$, and
let $B$ be the player who moves second.  If player $B$ has a non-losing
strategy for \emph{every} subgame, $T'$, of $T$, then $B$ also has a
non-losing strategy for the full game tree $T$: no matter what move
player $A$ makes, player $B$ simply follows his non-losing strategy for
the immediate subgame determined by $A$'s move.

On the other hand, suppose there is some immediate subgame, $T_0$, of
$T$, for which player $B$ does not have a non-losing strategy.  
Since, by induction hypothesis, \emph{some} player has a non-losing
strategy for $T_0$, it must be player $A$ that the non-losing strategy
for this subgame.  But then player $A$ has a non-losing strategy for the
full game tree $T$: namely, make the move that leads to subgame $T_0$
and then pursue the non-losing strategy for that subgame.

In either case, at least one of the players has a non-losing strategy.
This completes the proof of the induction step, and thus the whole proof
by structural induction.

We conclude that $P(T)$ holds for all games trees, $T$.
\end{proof}
}

\ppart Conclude that either one player has a winning strategy or both
players have non-losing strategies.

\solnospace{Call the players $C$ and $D$, and suppose neither one has a
winning strategy for the game, $T$.  We want to show that then \emph{both}
players have non-losing strategies for $T$.

The proof is based on the simple observation that in a game with no draws,
a non-losing strategy must be a winning strategy.  So in a game with no
draws, we conclude from part (a) that there is always a player with a
winning strategy.

\begin{proof}
To prove that $C$ has a non-losing strategy for the game, $T$, let's
consider another game, $T_C$, identical to $T$ except that draws are
considered wins for player $C$.  Since there are no draws in $T_C$, we
conclude that either $C$ or $D$ has a winning strategy for $T_C$.  But a
winning strategy for $D$ in the $T_C$ game would also be a winning
strategy for $D$ in the original game, $T$, because wins for $D$ are the
same in both games.  But we assumed that $D$ has no winning strategy for
$T$, so it doesn't have one for $T_C$.

That means that $C$ must have the winning strategy for $T_C$.  But a
winning strategy for $C$ in $T_C$ would also be a non-losing strategy for
$C$ in the original game, $T$, because wins for $C$ in $T_C$ are always
wins for $C$ or draws in $T$.  So we conclude that $C$ has a non-losing
strategy for $T$.

Notice that we haven't assumed that $C$ is the first or second
player, so the preceding argument applies equally well to show that $D$
also has a non-losing strategy for $T$, as required.
\end{proof}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%---------------------------------------------------------
% source: spring00 ps4
% topic: bipartite, tree, 2 coloring
% redone to add structral induction

\problem A 2-colorable graph is called {\em bipartite}.  Prove by
induction that every unordered unrooted tree is bipartite. The set of
{\em unordered unrooted} trees $T$ is defined recursively as follows:

1.  A single node is in $T$.

2.  If $t_1$ and $t_2$ are two disjoint trees in $T$, then the tree
    $t'$ formed by adding an edge from any vertex $v$ of $t_1$ to any
    vertex $u$ of $t_2$, is also in $T$.

\solnospace{
\begin{proof}
We want to prove that a tree is 2-colorable.  If we do this, then we
have shown that a tree is bipartite.  We will prove this using
structural induction.

{\bf Base case:} The base case is trivially true.  A single node can be
colored with just one color, meaning that it is two-colorable, and
therefor bipartite.

{\bf Structural Induction Step:}
Using rule 2 in the definition of an unordered,
unrooted tree, any tree is constructed out of two smaller trees, $t_1$
and $t_2$. Each of these trees, by our inductive hypothesis, is 
2-colorable.
Can we join $u$ from $t_1$ and $v$ from $t_2$ in a way such that our
new tree is also 2-colorable?  To do this, $u$ and $v$ must be
different colors.

Consider a 2-coloring of each of the smaller trees.  If vertex $v$
is a different color from $u$, then we can connect the
two trees to form the larger tree, and we are done.  If they are
different colors, then switch the coloring in $t_2$.  Now $u$ and $v$
are different colors, and can be connected.  Thus all possible trees
that can be constructed using the recursive definition must be 
2-colorable.
\end{proof}
}

\end{problems}

\end{document}
