\documentstyle[12pt,twoside,psfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{2}{February $20$, 1997}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Prove by induction that $n^5-n$ is a multiple 
of $5$ for every integer $n$.\\

Let $P(n)$ = ``$n^5 - n$ is divisible by 5''

{\em Proof:} By cases.
\begin{enumerate}
\item
{\bf Case 1:  $n\ge 0$.} Proof by induction.

{\em Base Case:} $n = 0$. $P(0)$ is true since $0^5 - 0 = 0$ is divisible by 5.\\
{\em Inductive Hypothesis:} For $n=k$ assume $P(n=k)$ is true, that is, ``$k^5 - k$ is divisible by 5''\\
{\em Inductive Step:}
 For $n = k+1$ prove P(n=k+1):
\begin{eqnarray*}
(k+1)^5 - (k+1) &=& (k^5 + 5k^4 + 10k^3 +10k^2 + 5k +1) - (k+1)\\                        &=& (k^5 - k) + (5k^4 + 10k^3 +10k^2 + 5k) \\
                &=& (k^5 - k) + 5(k^4 + 2k^3 + 2k^2 + k)\\ 
\end{eqnarray*}
This sum is also divisible by 5 since both terms in the sum are divisible by 5.  The first term is divisible by 5 by the inductive hypothesis and the second term is a multiple of 5.

\item
{\bf Case 2: $n\le 0$.} Proof by induction.

{\em Base Case:} $n = 0$. $P(0)$ is true since $0^5 - 0 = 0$ is divisible by 5.\\
{\em Inductive Hypothesis:} For $n=k$ assume $P(n=k)$ is true, that is, ``$k^5 - k$ is divisible by 5''\\
{\em Inductive Step:}
 For $n = k-1$ prove P(n=k-1):
\begin{eqnarray*}
(k-1)^5 - (k-1) &=& (k^5 - 5k^4 + 10k^3 - 10k^2 + 5k - 1) - (k-1)\\                        &=& (k^5 - k) + (-5k^4 + 10k^3 -10k^2 + 5k) \\
                &=& (k^5 - k) + 5(-k^4 + 2k^3 - 2k^2 + k)\\ 
\end{eqnarray*}
This sum is also divisible by 5 since both terms in the sum are divisible by 5.  The first term is divisible by 5 by the inductive hypothesis and the second term is a multiple of 5.
\end{enumerate}


{\bf NOTE:} The proof by cases could have been embedded in the inductive
step.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Determine and prove which Fibonacci numbers are divisible by 3. 

Notice that $f_8$ and $f_9$ are the same , modulo 3, as $f_0$ and
$f_1$.  The sequence of ``$f_n$ mod $3$'' numbers repeats after this
point.  Therefore, the pattern has period 8.  Note, also, that for $n
\equiv 0 \mbox{ or } 4 \pmod{8}, f_n$ is divisible by 3.

\begin{figure}[htb]
 \centerline{\psfig{figure=PS2prob2.ps,height=1.5in,width=6in}}
  \caption{Problem 2}
  \label{}
\end{figure}


We can formulate a definition for $f_n$ divisible by $3$ as follows:

\begin{eqnarray*}
f_n & \equiv & 0 \pmod{3} \mbox{ if } n \equiv 0 \mbox{ or } 4 \pmod{8}  \\
f_n & \equiv & 1 \pmod{3} \mbox{ if } n \equiv 1, 2 \mbox{ or } 7 \pmod{8}\\
f_n & \equiv & 2 \pmod{3} \mbox{ if } n \equiv 3, 5 \mbox{ or } 6 \pmod{8}\\
\end{eqnarray*}

{\em Proof:} Prove the above conjecture by strong induction:

{\bf Base Case:} There are two bases cases $n=0$ and $n=1$. \\ 
The conjecture is true for $n=0$ since $n \equiv 0 \pmod{8}$ and $f_0
\equiv 0 \pmod{3}$.\\
The conjecture is true for $n=1$ since $n \equiv 1 \pmod{8}$ and $f_1
\equiv 1 \pmod{3}$.

{\bf Inductive Hypothesis:} Assume the conjecture is true for all
values $\le n$.

{\bf Inductive Step:} Prove the conjecture for $(n+1)$.  There are
eight cases depending on the value of $(n+1) \bmod 8$.  We will carry
out one of them; the other seven cases are similar.

 
{\em Case 1:} $(n+1) \equiv 1 \pmod{8}$
similar to case 5.
 
{\em Case 2:} $(n+1) \equiv 2 \pmod{8}$
similar to case 5.
 
{\em Case 3:} $(n+1) \equiv 3 \pmod{8}$
similar to case 5.
 
{\em Case 4:} $(n+1) \equiv 4 \pmod{8}$
similar to case 5.
 
{\em Case 5:} $(n+1) \equiv 5 \pmod{8}$

\[\begin{array}{lcll}
f_{n+1} &=& f_n + f_{n-1} &  \mbox{by the definition of Fibonacci numbers} \\
 &=& f_{n \equiv 4 \pmod{8}} + f_{(n-1) \equiv 3 \pmod{8}} & \mbox{since }
(n+1) \equiv 5 \pmod{8} \\
 &{ }& &\mbox{then } n \equiv 4 \pmod{8} \mbox{ and } (n-1) \equiv 3
\pmod{8} \\
 &=& 0 + 2 \pmod{3} & \mbox{by the inductive hypothesis,}\\
 &{ }& & f_n  \equiv 0 \pmod{3} \mbox{ and } f_{n-1}  \equiv 2
\pmod{3}\\
 &=& 2 \pmod{3} & \mbox{as desired.}
\end{array}\]

 
{\em Case 6:} $(n+1) \equiv 6 \pmod{8}$
similar to case 5.
 
{\em Case 7:} $(n+1) \equiv 7 \pmod{8}$
similar to case 5.
 
{\em Case 8:} $(n+1) \equiv 0 \pmod{8}$
similar to case 5.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Find a 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 result.


Prove that ${{1}\over {1*2}} + {{1}\over {2*3}} + ... +{{1}\over
{n*(n+1)}} =  {{n}\over {n+1}}.$ \\

{\em Proof by induction.}\\
Let $P(n)$ be ``${{1}\over {1*2}} + {{1}\over {2*3}} + ... +{{1}\over
{n*(n+1)}} =  {{n}\over {n+1}}.$'' \\

{\bf Base Case:} $n = 1$. $P(1)$ is true since ${{1}\over {1*2}} = {1
\over {(1+1)}}$.

{\bf Inductive Hypothesis (I.H.):} For $n=k$ assume $P(n=k)$ is true, that is, ${{1}\over {1*2}} + {{1}\over {2*3}} + ... +{{1}\over
{k*(k+1)}} =  {{k}\over {k+1}}.$ 

{\bf Inductive Step:}
 For $n = k+1$ prove $P(n=k+1)$:
\begin{eqnarray*}
{{1}\over {1*2}} + {{1}\over {2*3}} + ... +{{1}\over
{(k+1)*((k+1)+1)}} &=& {{1}\over {1*2}} + {{1}\over {2*3}} + ...{{1}\over
{k*(k+1)}} + {{1}\over
{(k+1)*((k+1)+1)}} \\
&=&  {{k}\over {k+1}} + {{1}\over {(k+1)*((k+1)+1)}}
\mbox{ true by {\bf I.H.}}\\
&=&{{k*(k+2)} \over {(k+1)*(k+2)}} + { 1 \over {(k+1)*(k+2)}}\\
&=&{{k^2 + 2k +1} \over {(k+1)(k+2)}}\\
&=& {{(k+1)}^2 \over {(k+1)(k+2)}} \\
&=& {{k+1}\over {k+2}} \\
&=& {{k+1}\over {(k+1)+1}} 
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Use mathematical induction to prove that $\forall n \geq 4$,
$n^2 < n!$.

Prove that $\forall{n \ge 4} \mbox{  } n^2 < n!$.\\

{\em Proof by induction.}

{\bf Base Case:} True for $n=4$ since $16 < 24$.

{\bf Inductive Hypothesis (I.H.):} For $n=k$ assume $n^2 < n!$ is true.\\

{\bf Inductive Step:}
Prove for $n = k+1$:

\[\begin{array}{lcll}
(n+1)^2 &=& n^2 + 2n + 1 & \mbox{ }\\
&<& n! + 2n + 1 &\mbox{ true by {\bf I.H.}}\\
&<& n! + 2n + n = n! + 3n &\mbox{ a valid upper bound } 1<n\\
&<& n! + n*n = n! + n*n*1 &\mbox{ a valid upper bound } 3<n\\
&<& n! + n*n^2 &\mbox{ a valid upper bound } 1<n\\
&<& n! + n*n!& \mbox{ true by {\bf I.H.}}\\
&=& (n+1)n! &\mbox{ }\\
&=& (n+1)! &\mbox{ }
\end{array}\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Define a new propositional operator $\oplus$ as follows: for
propositions $p$ and $q$, $p \oplus q$ is true if exactly one of $p$
and $q$ is true.  
\begin{problemparts}
\problempart Write $p \oplus q$ in terms of the standard operators
$\vee,\wedge,\neg$. 
\problempart
Let $P_1,\ldots,P_n$ be $n$ propositions and 
$Q_n$ the proposition
$P_1\oplus P_2\oplus \cdots \oplus P_n$.
Prove by induction on $n$ that $Q_n$ is 
true if and only if the number of true propositions
among $P_1,\ldots,P_n$ is odd.
\end{problemparts}
 

\bparts

\ppart $p \otimes q = (p \vee q) \wedge \neg(p \wedge q)$
\ppart
{\em Proof by induction on n.}

Let S(n) = ``$ Q_n$ is true $\iff$ the number of true propositions $P_1 ... P_n$ is odd.

Notation: $Q_n$ is true(false) can also be written as $Q_n = 1(0)$.

{\bf Base Case:} $S(n)$ is true for $n=1$. Since $Q_1 = P_1$, $Q_1$ is made up of an odd number of propositions $P$, and $Q_1$ is true $\iff$ $P_1$ is true.


$S(n)$ is true for $n=2$.  Since $Q_2 = P_1 \otimes P_2 = (P_1 \vee P_2) \wedge \neg(P_1 \wedge P_2)$ one can trivially fill in the truth table to show that $S(2)$ is true.

\begin{figure}[htb]
 \centerline{\psfig{figure=PS2prob5.ps,height=1.5in}}
  \caption{Problem 5}
  \label{}
\end{figure}


{\bf Inductive Hypothesis (I.H.):} For $n$ assume that ``$Q_n$ is true $\iff$ the number of true propositions $P_1 ... P_n$ is odd'', ie. that $S(n)$ is true.

{\bf Inductive Step:}
Prove $S(n+1)$
\begin{eqnarray*}
Q_{n+1} &=& P_1 \otimes P_2 \otimes ...\otimes P_n \otimes P_{n+1} \\
        &=& Q_n \otimes P_{n+1}
\end{eqnarray*}

We have now reverted to a $n=2$ scenario where there are 4 cases as
seen in Figure 2.

{\em Proof by cases:}\\
{\em Case 1:} $Q_n = 0$ and $ P_{n+1}=0$.

 Thus $Q_{n+1}$ is False.
$Q_{n+1}$ also has an even number of true propositions since $Q_n$ has
an even number of true propositions (true by {\bf I.H.}).

{\em Case 2:} $Q_n = 0$ and $P_{n+1}=1$.

 Thus $Q_{n+1}$ is true. A true
$P_{n+1}$ plus an even number of true propositions in $Q_n$ (true by
{\bf I.H.}) equals an odd number of true propositions for $Q_{n+1}$.

{\em Case 3:} $Q_n = 1$ and $P_{n+1}=0$.

 Thus $Q_{n+1}$ is true. A false
$P_{n+1}$ plus an odd number of true propositions in $Q_n$ (true by
{\bf I.H.}) equals an odd number of true propositions for $Q_{n+1}$.

{\em Case 4:} $Q_n = 1$ and $P_{n+1}=1$.

Thus $Q_{n+1}$ is false. A true
$P_{n+1}$ plus an odd number of true propositions in $Q_n$ (true by
{\bf I.H.}) equals an even number of true propositions for $Q_{n+1}$.


Therefore, $Q_{n+1}$ is true $\iff$ an odd number of $P_1 ... P_{n+1}$ are true
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
What are the fallacies in the following arguments? Don't just
explain why the claim is wrong; rather, explain how the argument
violates the notion of correct proofs.
\begin{problemparts}
\problempart Claim: Every integer is nonnegative.  Proof: $0$ is
nonnegative.  Assuming $n$ is nonnegative, $n+1$ is certainly
nonnegative.

\problempart Claim: Every natural number is a prime or a perfect
square.  Proof: as the inductive hypothesis, use $P(n)=$``every number
less than or equal to $n$ is a prime or a perfect square.''  $P(1)$ is
certainly true.  Now consider $n$.  If $n$ is prime we are done.
Otherwise, $n$ can be factored as $n=rs$ with $r$ and $s$ less than or
equal to $n-1$.  By the inductive hypothesis, $r$ and $s$ are perfect
squares, $r=u^2$ and $v=s^2$.  Then $n=rs=u^2v^2=(uv)^2$.

\problempart Claim: no quantity of homework problems is too many.
Proof: Base case:  Clearly 0 homework problems is not too many.
Inductive step: if $n$ homework problems are not too many, then
certainly $n+1$ homework problems is not too many. 

\end{problemparts}


\bparts

\ppart

The claim is for all integers but the proof only checks the natural numbers.

\ppart

The proof does not consider the case when $r$ and/or $s$ are primes. It also
neglects to prove anything about zero.

\ppart

``Too many'' is an ill-defined relation. {\bf OR} asserting the conclusion.

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
 Using only the Peano Axioms, prove
\[
\neg(\exists x,y) (x=y' \wedge y=x')
\]
(recall that $x'$ is the successor of $x$).

Peano's Axioms define the natural numbers $\naturals$. 
We use two primitive symbols: $0$ and $'$ (successor).
\begin{enumerate}
\item $0 \in \naturals$
\item $(\forall x \in \naturals),\ x' \in \naturals$
\item $\forall x,y \in \naturals,\ x'=y' \Longrightarrow x = y$ (no two
numbers have same successor)
\item $\neg\exists x \in \naturals$ such that $0 = x'$  (equivalently, 
$\forall x \in \naturals, x' \ne 0$)
\item (Induction) $\forall S \subseteq \naturals$, if $0 \in S$ and $\forall
x \in \naturals ,(x \in S \Longrightarrow x' \in S)$, then $S = \naturals$.
\end{enumerate}


{\bf Theorem}
Prove $\neg (\exists x, y) (x = y\prime \wedge y = x\prime)$.

{\em Proof}

 $\neg (\exists x, y) (x = y\prime \wedge y = x\prime) \iff (\forall
x,y) \neg (x = y\prime \wedge y = x\prime)$.

Substituting $y = x\prime$ into $x=y\prime$, then $(x = y\prime \wedge y = x\prime) \Longrightarrow (x = (x')').$

The contrapositive of the above is $\neg(x = (x')') \Longrightarrow
\neg(x = y\prime \wedge y = x\prime)$. Thus,

$(\forall x,y) \neg(x = y\prime \wedge y = x\prime) \iff (\forall
x) \neg(x=(x')')$.

Let $S=\{x \mid x\ne (x')'\}$. Must show $S = \naturals$.

{\bf Basis Step}  $0 \in S$, since $0 \ne x''$ by the 4 Axiom.  

{\bf Inductive Step:} Assume  $x \in S$.

\begin{eqnarray*}
x \in S &\Longrightarrow &x \ne x''\\
&\Longrightarrow &x' \ne x'''\\
&\Longrightarrow &x' \in S
\end{eqnarray*}
(In the second implication we apply the contrapositive of axiom 3,
taking $y=x''$).

Thus (by the syllogism inference rule and universal generalization)
$x \in S \Longrightarrow x' \in S$.  Thus, by the induction axiom, $S =
\naturals$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Give a recursive definition of multiplication of natural
numbers in terms of addition.  Using standard facts about addition
(associativity, commutativity, etc) as axioms, prove that
$x(y+z)=xy+xz$ and $(x+y)z = xz+yz$.
 
Axioms of addition:
\begin{itemize}
\item $n+k' = (n+k)'$
\item $(x + y) + z = x + (y + z)$
\item $n+0 = n$ (implicit universal quantification)
\end{itemize}
We define multiplication:
\begin{itemize}
\item $n*0 = 0$ (implicit universal quantification)
\item $n*k' = n*k + n$
\end{itemize}
This is a {\em recursive} definition: it lets us compute $n*k$ for any
$n, k$.  For example, 
\begin{eqnarray*}
3*2 &= &3*1 + 3\\ 
&= &(3*1) + 3\\ 
&= &(3*0 + 3) + 3\\ 
&= &(0 + 3) + 3\\ 
&= &(3) + 3\\ 
&= &3+2' \\
&= &(3+1')'\\
&= &(3+1)')'\\
 &= &(3+0')')'\\
 &= &((3+0)')')'\\ 
&=&(3')')'\\ 
&= &(4')'\\ 
&= &5'\\ 
&= &6.
\end{eqnarray*}



{\bf Theorem:} $x(y+z) = xy + xz$.

{\em Proof:} 
Let $S=\{ z | \forall(x,y) \ x(y+z) = xy + xz \}$. Must show $S = \naturals$.
(By induction on z.)
{\bf Basis Step:} $0 \in S$ (means true for $z=0$) since,
\begin{eqnarray*}
x(y + 0) &=& x(y) \mbox{ axiom 3 of addition} \\
&=& xy + 0 \mbox{ axiom 3 of addition} \\
&=& xy + x0 \mbox{ definition 1 of multiplication} 
\end{eqnarray*}

{\bf Inductive Hypothesis (I.H.):} Suppose $z \in S$. (Assume that $x(y+z) = xy + xz$ is true for $z.$)

{\bf Inductive Step:}
Prove for $(z')$:

\begin{eqnarray*}
x(y + (z')) &=& x((y + z)') \mbox{ by axiom 1 of addition}\\
&=& x(y+z) + x \mbox{ by definition 2 of multiplication} \\
&=& xy + xz + x \mbox{ by {\bf I.H.}} \\
&=& xy + x(z') \mbox{ definition 2 of multiplication} 
\end{eqnarray*}

{\bf Theorem:} $(x+y)z = xz + yz$.

{\em Proof:} 
Let $S=\{ z | \forall(x,y) \ (x+y)z = xz + yz \}$. Must show $S = \naturals$.
(By induction on z.)
{\bf Basis Step:} $0 \in S$ (means true for  $z=0$) since,
\begin{eqnarray*}
(x+y)*0 &=& 0 \mbox{ by definition 1 of multiplication} \\
&=& 0 + 0 \mbox{ axiom 3 of addition} \\
&=& x0 + y0 \mbox{ definition 1 of multiplication} 
\end{eqnarray*}

{\bf Inductive Hypothesis (I.H.):} Assume $z \in S$ (Assume that $(x+y)z = xz + yz$ is true for z.)

{\bf Inductive Step:}
Prove for $(z')$:

\begin{eqnarray*}
(x+y)*(z') &=& (x+y)z + (x+y) \mbox{ by definition 2 of multiplication} \\
&=& xz + yz + x + y \mbox{ by {\bf I.H.}} \\
&=& x(z') + y(z') \mbox{ definition 2 of multiplication} 
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
A disgraceful disease strikes a monastery.  The
monks are informed that at least one of them has the disease.  All
monks are ordered to leave the monastery as soon that they are certain
that they are infected.  The disease demonstrates itself by a mark on
the forehead (all sick people get the mark).  Unfortunately in this
monastery there are no mirrors and the monks are not allowed any form
of communication.  Monks gather to pray every morning so they can all
see each other.  If they become certain that they are infected they
depart during that night.

{\em Proof.} Let $m$ be the number of infected monks.
We know that $m\geq 1$.
We claim that all and only the infected monks will leave, 
and they will leave the night of the $m^{th}$ day.
More formally, we will prove by strong induction on $n$ the 
following statement:
the night of the $n^{th}$ day monk $M$ will depart 
if and only if $M$ is infected and the number of infected 
monks $m$ is equal to $n$.

{\bf Base Case (n=1):}
We distinguish three cases:
\begin{itemize}
 \item If monk $M$ is sick, and the number of infected monks is $m=1$,
  $M$ is the only infected monk and he cannot see any monk with 
  the mark on the forehead.
  Since he knows that at least one monk is infected, he will
  be certain that he is infected and will depart during the night 
  of the first day.
 \item If monk $M$ is sick, but the number of infected monks is $m>1$,
  $M$ can see $m-1\geq 1$ monks with the mark on the forehead.
  Since, as far as $M$ knows, the number of infected monks could be 
  $m-1$ as well as $m$, he does not know if he is infected or not, 
  and therefore he won't leave.
 \item If monk $M$ is not sick, he can see $m$ monks with the mark 
  on the forehead.
  Since, as far as $M$ knows, the number of infected monks could be 
  $m$ as well as $m+1$, he does not know if he is infected or not, 
  and therefore he won't leave.
\end{itemize}

{\bf Inductive Case ($n\geq 2$):}
If $m<n$ then by induction hypothesis 
the infected monks departed the monastery on the $m^{th}$ day,
and all remaining monks will know that they are not infected
and will stay in the monastery on the $n^{th}$ day.
Otherwise, $m\geq n$ and no monk departed the monastry 
before the $n^{th}$ day. 
Since the monks are rational, on the $n^{th}$ day they will know that 
the number of infected monks is at least $n$ and that all monks 
are aware of that.
 
We now distinguish three cases:
\begin{itemize}
 \item If monk $M$ is sick, and the number of infected monks is $m=n$,
  $M$ will know he is infected because he can see only
  $m-1$ monks with the mark on the forehead.
  So, he will depart the monastry that same night.
 \item If monk $M$ is sick, but the number of infected monks is $m>n$,
  $M$ can see $m-1\geq n$ monks with the mark on the forehead.
  Since, as far as $M$ knows, the number of infected monks could be 
  $m-1$ as well as $m$, he does not know if he is infected or not, 
  and therefore he won't depart the monastry on that night.
 \item If monk $M$ is not sick, he can see $m$ monks with the mark 
  on the forehead.
  Since, as far as $M$ knows, the number of infected monks could be 
  $m$ as well as $m+1$, he does not know if he is infected or not, 
  and therefore he won't depart the monastry on that night.
\end{itemize}

\iffalse
Use an inductive argument to show that if the monks are rational and
there are $n$ {\bf infected} monks then they will all depart the monastery
by the $n^{th}$ day.
 
There is at least 1 infected monks.

{\bf Theorem} If no monks leave by the arrival of the $n^{th}$ day
then every monk will know that there are at least $n$ monks that are
infected.  If there are n monks that are infected then on the $n^{th}$
day all monks that only see $n-1$ infected monks will leave.

{\em Proof:} By induction on  $n$.

{\bf Basis Step:} True for $n=1$ since:
Since no monk left by the arrival of the $1^{st}$ day
then every monk will know that there are at least $1$ monk that is
infected.  Also true by problem definition.

The infected monk will not see anyone else infected and leave the first
day. All monks that see 1 infected monk will not leave.


{\bf Inductive Hypothesis (I.H.):} Assume true for all values $\le n$:

If no monks leave by the arrival of the $n^{th}$ day
then every monk will know that there are at least $n$ monks that are
infected.

If there are exactly $n$ infected monks then all monks that see $n-1$
infected monks  will leave the $n^{th}$ day.

{\bf Inductive Step:} 

If no monks have left by (n+1) day then no monks left by the n day
therefore there are not exactly n infected monks. Since there are not
exactly n infected monks and by the strong inductive hypothesis then there
are at least (n+1) infected monks.

Then on the $(n+1)^{st}$ day, all monks will know that at least (n+1)
are infected.

Since there are at least $(n+1)$ monks that are infected then any monk
that sees $n$ other infected monks will consider himself infected and
all infected monks will leave that day.  Any monk that sees $n+1$
monks that are infected will choose not to leave the $n+1$ day.



%If there are $(n+1)$ monks that are infected then no monks will leave
%on the $n^th$ day since every infected monk will see $n$ other
%infected monks not counting themselves.  Then on the $(n+1)^{st}$ day, all
%monks will know that at least n+1 are infected.  All infected monks
%will leave that day since any monk that sees $n$ other infected monks
%will consider himself infected and leave. Any monk that sees $n+1$
%monks that are infected will choose not to leave the $n+1$ day.

\fi

\end{problems}
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

The max or min of one number is itself. max$(a_1,a_2)=a_1 \bigvee a_2$
if $a_1\geq a_2$, and $a_1<a_2$ respectively. Also, min$(a_1,a_2)=a_1
\bigvee a_2$ if $a_2\geq a_1$ and $a_2<a_1$ respectively.  For $n\geq 2$
we define
\[
max(a_1,a_2,...,a_{n+1}) = max(max(a_1,a_2,...,a_n),a_{n+1})
\]
and
\[
min(a_1,a_2,...,a_{n+1}) = min(min(a_1,a_2,...,a_n),a_{n+1})
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

First, we prove the follwing theorem:

\begin{theorem} Let $n$ be a positive integer. Show that a $2^n \times
2^n \times 2^n$ cube, (an {\em $n$-cube}) with one arbitrary cubic
foot removed can be built with basic blocks of size $2\times 2\times
2$ ({\em $1$-cube}) with one of its cubic foot missing.
\end{theorem}
\begin{proof} Let $P(n)$ be the statement that any {\em $n$-cube}
with one arbitrary cubic foot missing can 
be built using {\em $1$-cubes} with one cubic foot removed.
We use mathematical induction to prove $P(n)$
is true for all positive integers $n$.

{\bf Basis Step} $P(1)$ is true since a {\em $1$-cube} with one
missing cubic foot is already provided as basic block by CIA.

{\bf Inductive Step:} Assume that $P(n)$ is true. We show that
$P(n+1)$ is true. Construct $8$ {\em $n$-cubes} in such a way that $7$
of them are missing one cubic foot from one of their $8$ corners, and
the {\em $8$th} one is missing an arbitrary cubic foot. We can do this
by the induction hypothesis. We construct an {\em $(n+1)$-cube} as
follows: Put the $7$ corner-missing {\em $n$-cubes} together so that all of
their missing corners meet in the center. Then fill up the gap with a
basic block.  Now add the {\em $8$th}
{\em $n$-cube} with an arbitrary cubic foot missing to get an
{\em $(n+1)$-cube} with an arbitrary cubic foot removed.
\end{proof}

Now we are in good shape to prove the master theorem.
\begin{theorem}
Prove that an {\em $(n+1)$-cube} with one cubic foot missing from its
center (the {\bf CIA} cube) can be built using {\em $1$-cubes} with one
cubic foot missing.
\end{theorem}
\begin{proof}
The {\bf CIA} cube can be built by following the steps in the proof of
{\bf Theorem $0.1$} except that when building the {\em $8$th} cube, we
choose the arbitrary missing cubic foot to be one of the $8$ possible
{\em $1$-cubes} in the center of the {\em $8$th} {\em $n$-cube}.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Let $E$ denote the number of edges, and $N$ be the number of nodes in
a {\em $3,4$-tree}. Then: 
\bparts
\ppart $E = N-1$.
\ppart \begin{theorem} In a {\em $3,4$-tree}, $E = N-1$.
\end{theorem}
\begin{proof} By Structural Induction.

{\bf Basis Step:} Let $N=1$. This it is clearly true since there are no
edges in a one-node tree.

{\bf Inductive Step:} Assume this is true for $k\leq n$. We need to
show that it is also true for a tree with $N+1$ nodes. Let's break this
into two cases.

{\em Case 1:} Root of the tree has $3$ childeren, where every such
subtree is a {\em $3,4$-tree} by definition. By the induction
hypothesis, for every such subtree the number of edges is one less
than the number of nodes in the subtree.  Hence, for a tree with $N+1$
nodes, there are total of $N$ nodes and $N-3$ edges in the $3$
subtrees.  The root-node adds one more node and $3$ edges connecting
to the $3$ subtrees, making it a total of $N+1$ nodes and $N$ edges as
desired.

{\em Case 2:} Root of the tree has $4$ childeren, where every such
subtree is a {\em $3,4$-tree} by definition. By the induction
hypothesis, for every such subtree the number of edges is one less
than the number of nodes in the subtree.  Hence, for a tree with $N+1$
nodes, there are total of $N$ nodes and $N-4$ edges in the $4$
subtrees.  The root-node adds one more node and $4$ edges connecting
to the $4$ subtrees, making it a total of $N+1$ nodes and $N$ edges as
desired.
\end{proof}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts
\ppart $Pink = \{x : x \in \naturals,~ \mbox{and}~ x \geq 24\}$.
\ppart \begin{theorem} Every natural number $\geq 24$ can be expressed
as the sum of, not necessarily distint, perfect squares of numbers $\geq 2$.
\end{theorem}
\begin{proof} By Contradiction: Define the set $Blue=\{x: x\in
\naturals, x\geq 24,~ \mbox{and $x\not\in Pink$}\}$.

Then by the well-ordering property, $Blue$ has a smallest element,
$s$. Now let $4pinks=\{24, 25, 26,27\}$. Then $x\in 4pinks
\longrightarrow x\in Pink$, since we can write:
\begin{eqnarray*}
24&=&6\cdot 4\\
25&=&4^2+9\\
26&=&2 \cdot 4+2\cdot 9\\
27&=&3\cdot 9
\end{eqnarray*}
So, $s$ must be $\geq 28$.
Since $s$ is the smallest element in {\em Blue}, we have $s' =  s-4 \geq 24$, 
and $s' \in Pink$. But, 
\[
~~s' \in Pink~~ \longrightarrow ~~ s' + 4 \in Pink ~~\longrightarrow s\in Pink
\]
since $s'+4$ is the sum of 
perfect squares $\geq 2$. But it cannot be that $s\in Blue$, and $s\in Pink$,
since {\em Blue $\cap$ Pink $=\emptyset$}. Contradiction!  
Hence, {\em Blue} is indeed empty, and so every natural number $\geq 24$ is 
{\em pink}.
\end{proof}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts
\ppart We do not have enough base cases to support the claim. The proof
breaks down when we assume $2^1=3^1$ by the induction hypothesis, which
had to be shown to be true as a base case.
\ppart The inductive hypothesis is involed wrongly in the inductive
step. $n+1$ need not be composite; it could very well be a prime.
\eparts

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

\end{problems}

\begin{center}
\large \bf Some common mistakes in your solutions
\end{center}

{\bf Problems 1 and 2:} 
\begin{itemize} 
\item some students gave extraneous base cases.
\item a few forgot to argue the base case.
\item a few refered to $P(n)$ without defining it.
\end{itemize}
{\bf Problem 3:} 
\begin{itemize}
\item several people forgot the $a_1=a_2$ case.
\item a few people forgot to define a base case.
\end{itemize}
{\bf Problem 4:} 
\begin{itemize}
\item almost everyone used circular reasoning.
\item a few assumed that a $2^n\times 2^n\times 2^n$ block with one 
cubic foot missing could be built without
offerring any proof of it.
\end{itemize}
{\bf Problem 5:} 
\begin{itemize}
\item several students just gave a few examples and didn't use induction.
\item some people forgot the base case.
\item several people identified steps that violated the {\em $3,4$-tree} 
property as valid construction steps in their inductive argument.
\end{itemize}
{\bf Problem 6:} 
\begin{itemize}
\item a few people just gave a few examples but didn't prove it.
\item a few displayed a fundamental lack of understanding of 
the well-ordering principle.
\end{itemize}
{\bf Problem 7:} 
\begin{itemize}
\item some people said ``the math was wrong'', {\em i.e.}, $2^1\not = 3^1$,
$\log_2{n}\not = 0$ if $n\not = 0$, therefore the proof was false.
\item several people showed that the theorem was false, not that the
proof was invalid.
\end{itemize}

\end{document}





