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

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{2}{September 12, 1995}{Start of Class, September 19}

{\bf Reading:} Sections 3.1 to 3.3 of {\it Discrete Mathematics and
its Applications} by Kenneth H. Rosen.

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 3.2 - 7
\problem 
%Problem 7 from Section 3.2, pg 198 of Rosen.
Show that $1^2 + 2^2 +\cdots + n^2 = n(n+1)(2n+1)/6$ whenever $n$ is a
positive integer.

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


\problem Give a recursive definition of the multiplication function 
$m\times n = mn$ in terms of the addition function $+$. Use your
definition and the laws of addition to prove by induction that
$m\times (n+p) = (m\times n) + (m\times p)$. 

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

\problem A {\em full binary tree} consists of either a {\em leaf node}
with no children or an {\em internal node} with left and right
subtrees that are full binary trees.  Prove that a full binary tree on $n$
nodes has $(n+1)/2$ leaves. 

An example of a full binary tree is provided below:

\vspace*{1.5in}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem $n$ football teams participate in a {\em tournament}. In a 
tournament every pair of teams plays against each other, once. There
are no ties. A {\em chain} is an ordering of the teams so that each
team beats the one directly following it in the order. Prove that
every tournament has a chain. (It may be useful to prove the following
lemma as a step in the overall proof: in any sequence of $n$ zeroes and
ones that begins with a zero and ends with a one, there is a zero
immediately preceding a one somewhere in the sequence.  

Does this mean the first team in
the order always beat all the other teams?  Prove or give a counterexample.

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

\problem Find the fallacies in the ``proofs'' of the following ``theorems:''
\begin{problemparts}

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

\problempart
%Problem 44 from Section 3.2, pg 200 of Rosen.
{\em Theorem:}  Whenever $a$ is a nonzero real number, we have $a^n =
1$ for all natural numbers $n$. \\
{\em BASIS STEP:} $a^0 = 1$ is true by the definition of $a^0$.\\
{\em INDUCTIVE STEP:} Assume that $a^k = 1$ for all nonnegative integers 
$k$ with $k \leq n$. Then note that
\[ a^{n+1} = \frac{a^n\cdot a^n}{a^{n-1}} = \frac{1\cdot 1}{1} = 1.\]

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

\problempart
{\em Theorem} Every natural number is either a prime or a perfect
square.\\
{\em BASIS STEP:} 1 is a perfect square.\\
{\em INDUCTIVE STEP} Assume the theorem true for all $k < n$ and show
it for $n$.  If $n$ is prime, we are done.  Otherwise, since $n$ is
composite, it can be factored as $rs$ for $r,s<n$.  By inductive
hypothesis, $r$ and $s$ are squares, say $r=u^2$ and $s=v^2$.  Then
\[
n = rs = (u^2)(v^2) = (uv)^2
\]
showing that $n$ is a perfect square.

\problempart
{\em Theorem:} Every positive integer can be described in fewer than
fourteen words.\\ {\em Proof:} Let $S$ be the set of all numbers that
cannot be so described. It contains a least element. This element is
``the smallest number that cannot be described in less than fourteen
English words.'' But this is a thirteen-word description, a
contradiction. Thus $S$ must be empty, implying the theorem.
\end{problemparts} 

\problem Prove that every third Fibonacci number is
even. ($F_0 = 1, F_1 = 1, F_{i+2} = F_{i+1} + F_i, \forall i \geq 0$.
The series of third Fibonacci numbers is $F_2, F_5, \ldots$.)

\end{problems} 
\end{document}
