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

\begin{document}
\pset{2}{September 9, 1997}{Tuesday, September 16}

{\bf Reading assignment: }Finish reading the {\it Nuts and Bolts of Proofs}.
Read 3.2 of Rosen.

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
\problem 
Prove by induction that for every $n \in \naturals$, 
either $4 | n^2$ or $4 | (n^2-1)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
\problem Use mathematical induction to prove that $\forall n \geq 4$,
$n^2 \leq 2^n$ 
({\it Note: If you use a fact such as $n^2 \geq 2n+1$ for $n \geq 4$,
don't forget to prove it})

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\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 a correct proof.

\begin{problemparts}

\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 
{\em Claim}: $\log_3 n = \log_2 n$ for all natural numbers $n$.

Proof by strong induction:

The inductive hypothesis is $P(n) = ``\log_3 n = \log_2 n''$.
 

{\em base case}: 
$\log_3 1 = 0 = \log_2 1$ is true.

{\em inductive step}: Assume that $\log_3 k = \log_2 k$ for all natural numbers
$k \leq n$, and show it is true for $n+1$. Write $n+1$ as a product of 
two natural numbers $p$ and $q$ so that we have:  
\[
\log_3 (n+1) = \log_3 (pq) = \log_3 p +\log_3 q = \log_2 p + \log_2 q =
\log_2 (pq) = log_2 (n+1)  
\]
which is true by inductive hypothesis.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
%3.2-16
\problem
Use mathematical induction to prove that 

$$
1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 +\ldots +n(n+1)(n+2) = 
n(n+1)(n+2)(n+3)/4.
$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem
%Simple inductive proof based on Fibonacci recursive definition.
%Also, a sum of series.
%Section 3.3-10

Define the {\em Nifobacci numbers} $N_i$, by

$N_0 = 0$

$N_1 = 1$

$N_{n+1} = {N_n}^2+{N^2}_{n-1}$.

Prove that $N_{n}$ is even if and only if $3 | n$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\problem
% well ordering

The National Bank of Aldouria produces coins with denominations of  either
4 or 7 Aldourian pounds.  A sum of money is called {\it round} if
it can be made up with Aldourian coins.

\bparts
\ppart Characterize the Aldourian round sums.

\ppart 
Prove that any amount of money exceeding 17 is round using induction.

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
\problem
For what values of $m$ and $n$ can 
you tile an $n \times m$ courtyard if you are given tiles that are 
$3 \times 1$ and $2 \times 2$?  Prove that your answer is
correct.

({\em Note: $3 \times 1$ tiles can be rotated to form $1 \times 3$ tiles}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
%\problem 
%Is the following proof correct? Why or why not?

%{\em Claim:}

%There exists a constant $c > 0$ such that 
%$\forall n \in \naturals$, $\sum_{i=1}^n i \leq cn$.

%{\em Proof:} The proof is by induction on $n$. 

%If $n=1$, then the summation evaluates to $1$, which can be bounded
%above by $c$ times~$1$, where $c$ is any constant greater than or
%equal to~$1$.

%Assume that the statement is true for $n=k$, that is, that
%\begin{eqnarray*}
%\sum_{i=1}^k i \le ck
%\end{eqnarray*}
%for some constant~$c\geq 1$.  Adding $k+1$ to both sides, we obtain
%\begin{eqnarray*}
%\sum_{i=1}^{k+1} i & \le & ck + (k+1)\\
%& \le & (c+1)(k+1)\ .
%\end{eqnarray*}
%Since $c$ is a constant greater than or equal to 1, so is~$c+1$.  For
%$n=k+1$, therefore, the sum $\sum_{i=1}^{n} i$ is also bounded above
%by a constant times~$n$.  Consequently, by induction this property
%holds for every natural number $n\geq 1$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 8
\problem 
Use induction to prove that $\forall n \in \naturals$ and any $n$ sets
$A_1, A_2, \ldots A_n$, 

$$
(A_1 \cup A_2 \cup \ldots A_n)^c = A_1^c \cap A_2^c \cap \ldots A_n^c
$$



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\problem Verify or falsify the following proof that there exists a
%natural number $x\leq 1000$ such that $91 | (x-1)$
%and $143 | (x+1)$.  
%\begin{quotation}
%Define
%\[
%S = \set{n\in\naturals : 91 | (n-1) \mbox{ and } 143 | (n+1)}\ ,
%\]
%and let $x = \min(S)$.  Suppose for the purpose of contradiction that
%$x\geq 1001$.  Then, consider $y=x-1001$.  We have $91 | (x-1)$
%and $91 | 1001$, which implies that $91 | (y-1)$.
%Similarly, $143 | (y+1)$.  Consequently, we must have $y\in S$,
%contradicting the minimality of~$x$, and thus, $x\leq 1000$.
%\end{quotation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem
Prove that $k! | n(n+1)(n+2)\cdots(n+k-1)$ for all $k,n\in\nat$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 10
\problem 

An {\em $n$-player tournament} is a collection of two-player games such that
each of the $n$ players competes with each of the other players exactly once.
(Thus there are $n(n-1)/2$ games).  A player can either win or lose in a 
single game (there are no ties).  

Prove that in any $n$-player tournament, 
if there is no player that wins all his/her matches,
then there is a collection of players $p_1,p_2, \ldots, p_k$ 
(for some $k \leq n$), such that player $p_i$ beats player
$p_{i+1}$ for $1 \leq i < k$, and player $p_k$ beats player
$p_1$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\problem 
%Example 8 of section 3.2 shows that every set of $n$ elements
%contains $2^n$ subsets.  Prove by induction that any set containing
%$n>0$ elements has exactly $2^{n-1}$ subsets of even size (for
%example, $\{1,2\}$ has two subsets of even size:  $\emptyset$ and $\{1,2\}$).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%This is a hard problem. It requires an induction to show f(n) < f(n+k) 
%and well-ordering to establish a contradiction.  
%It also requires some careful reasoning, but it doesn't require any special
%knowledge of functions.
%Maybe we should make it worth two problems or use it as a tutorial problem

%\problem 
%Consider a function $f: \naturals \rightarrow \naturals$ satisfying the conditions

%\begin{itemize}
%\item $\forall n \in \naturals,f(n) < f(n+1)$
%\item $\forall n \in \naturals,f(f(n)) = f(n)$
%\end{itemize}

%Use well ordering to show that $\forall n \in \naturals,f(n) = n$

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







