\documentstyle[12pt,twoside]{article}
\input{macros-course}

\begin{document}
\pset{2}{February 11, 1997}{Start of Tutorial, Tuesday, February 18}

\begin{problems}

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

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

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

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

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

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

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

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


\problem {\bf (Optional).}  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.

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.

\end{problems}

\end{document}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
% LocalWords:  Peano
