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

\begin{document}
\psol{2}{September 19, 1997}


\begin{problems}

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

\bigskip

Let $P(n)$ = ``$4 | n^2$ or $4 | (n^2-1)$''

We will use strong induction.

{\bf Base case:} $P(0)$= ``$4 |0$'' is true. 

{\bf Inductive step: } Assume that $P(0) \wedge ... \wedge P(n)$ is true 
in order to show that $P(n+1)$ is true. We will show $P(n-1) \rightarrow 
P(n+1)$. The case for $P(1)$ must be checked separately.
$P(1)$ is indeed true because $4 | (1^2-1) = 0$.

We write

\begin{equation}\label{eq1}
(n+1)^2 = (n-1)^2+4(n-1)+4
\end{equation}

By the inductive hypothesis, there are $2$ cases:
 
\begin{description}

\item[Case 1:] $4 | (n-1)^2$

Then $4$ divides the right hand side of (\ref{eq1}), so $4 | (n+1)^2$.

\item[Case 2:] $4 | (n-1)^2-1$

From (\ref{eq1}), $(n+1)^2 -1 = (n-1)^2-1+4(n-1)+4$, so $4 | (n+1)^2-1$.

\end{description}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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})

\bigskip

{\em Lemma:}
$2^n \geq 2n+1$ for $n \geq 4$

\begin{proof}

We will prove the lemma by induction.

Let $P(n) = ``2^n \geq 2n+1$''.

{\bf Base case:} $n = 4$. 
$P(4)$ is true since $2^4 = 16 > 9 = 2\cdot 4+1$.

{\bf Inductive step:} 
Assume $P(n)$ is true in order to show that $P(n+1)$ is true.
We have that for $n \geq 4$

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

\end{proof}

Now we are ready to prove that  $\forall n \geq 4, n^2 \leq 2^n$.

Let $P(n) = ``n^2 \leq 2^n$''
  
{\bf Base case:} $n = 4$. $P(4)$ is true since $4^2 = 16  = 2^4$.

{\bf Inductive step:} 
Assume $P(n)$ is true in order to show that $P(n+1)$ is true.

We have:

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

The proof is complete.

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

\bigskip

The statement ``by the inductive hypothesis, $r$ and $s$ are perfect
squares'' is incorrect.  The inductive hypothesis states that a natural number is a perfect square {\em or} a prime.  So $r$ and $s$ could be primes.


\problempart 
{\em Claim}: $\log_3 n = \log_2 n$ for all natural numbers $n$.

Proof:

The inductive hypothesis is $P(n) = ``\forall n \in \naturals, 
\log_2 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.

\bigskip

If $n+1$ is prime it can only 
be factored as 1 times itself, so the inductive hypothesis does not apply.

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

\bigskip


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

{\bf Base case: } $n=1$

$$
1 \cdot 2 \cdot 3 = 6 = \frac{1 \cdot 2 \cdot 3 \cdot 4}{4}
$$

{\bf Inductive step:}
Assume that $P(n)$ is true in order to show that $P(n+1)$ is true.

\begin{equation*}
\begin{split}
1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 +\ldots +n(n+1)(n+2) + (n+1)(n+2)(n+3) \\
 = \frac{n(n+1)(n+2)(n+3)}{4} + (n+1)(n+2)(n+3) \\
 =  \frac{(n+1)(n+2)(n+3)(n+4)}{4}\\
\end{split}
\end{equation*}

We have shown that $P(n) \rightarrow P(n+1)$, so the induction is complete.


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

\bigskip

We will use strong induction to prove that
$P(n) = ``2 |N_n \leftrightarrow 3|n''$.

{\bf Base case:}  
$P(0)$ is true because $3|0$ and $N_0 = 0$ is even.
$P(1)$ is true because $3 \not | 1$ and $N_1 = 1$ is odd.


{\bf Inductive step:}
Suppose $P(k)$ is true for $0 \leq k \leq n$ in order to show that $P(n+1)$ 
is true.

There are three cases:

\begin{enumerate}

\item $(n+1) \mod 3 = 0$.

In this case, $3$ does not divide $n$ and $n-1$ so by the inductive hypothesis,
$N_n$ and $N_{n-1}$ are odd.  Therefore, $N_n^2$ and $N_{n-1}^2$ are also odd,
 so $N_{n+1}$ is even, being the sum of two odd numbers.

\item $(n+1) \mod 3 = 1$.

If $n = 0$, we obtain the base case $P(1)$ that we have already checked.

For $n > 0$ (and therefore $n \geq 3$) we have that
$3 | n$, but $3 \not | n-1$.  By the inductive hypothesis
$N_n$ (and $N_n^2$) is even and $N_{n-1}$ (and $N_{n-1}^2$) is odd.
So $N_{n+1}$ is odd.

\item $(n+1) \mod 3 = 2$.

Then $3 | n-1$, but $3 \not | n$.  By the inductive hypothesis
$N_n$ (and $N_n^2$) is odd and $N_{n-1}$ (and $N_{n-1}^2$) is even.
So $N_{n+1}$ is odd.

\end{enumerate}

We have shown that if $3 | (n+1)$ then $N_{n+1}$ is even, and
if $3 \not | (n+1)$, then $N_{n+1}$ is odd.  The proof is complete.


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

\bigskip

The Aldourian round sums are the numbers in the following set

$$
S = \{ n \in \naturals | n = 0,4,7,8,11,12,14,15,16 \text{ and }  n \geq 18 \}
$$

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


\bigskip

$P(n) = $ ``$n$ is an Aldourian round sum''

The proof is by strong induction.

{\bf Base case: }
The base case if for $n=18$.

$18 = 2 \cdot 7 + 4$, so it is a round sum.

%It is easy to check that 19,20, and 21 are also Aldourian round sums.

{\bf Inductive step:} 

Assume $P(n)$ is true in order to show that $P(n+1)$ is true. 

We can write $n+1 = n-3 + 4$.  $n-3$ is an Aldourian round sum if 
$n-3 \geq 18$ or equivalently $n \geq 21$.  So by the inductive hypothesis,
if $n \geq 21$, $n+1$ is an Aldourian round sum.


Now we check that if $18 < n+1 < 22$, then $n+1$ is also an Aldourian sum.

We have already checked the case $n+1 =18$ so there are three cases to verify.

\begin{itemize}
\item $19 = 4+4+4+7$
\item $20 = 4+4+4+4+4$
\item $21 = 7+7+7$
\end{itemize}

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


First we prove a series of Lemmata.

{\bf Lemma 1:} A $1 \times n$ and $n \times 1$ courtyard can be tiled 
if and only if $n$ is a multiple of $3$.  \\

\begin{proof}

Let $P(n) = $ ``An $n \times 1$ courtyard can be tiled if and only if $3|n$''.

{\bf Base case:} $1 \times 1$ and $2 \times 1$ courtyards cannot be tiled.

{\bf Inductive step:}
Assume $P(k)$ is true for $1 \leq k < n$.  Take an $n \times 1$ courtyard.
If $n=3$, then it can be tiled by one tile.
If $n > 3$, Place a $3 \times 1$ tile. 
If $3|n$, then $3|n-3$, so by the inductive 
hypothesis the remaining $(n-3) \times 1$ courtyard can be tiled.
If $3 \not | n$, then  $3 \not |n-3$, so by the inductive hypothesis the 
remaining courtyard (and therefore the whole courtyard) cannot be tiled.
 
\end{proof}

{\bf Lemma 2:}
Any  $2 \times n$ (and $n \times 2$) courtyard with $n > 1$  can be tiled.

\begin{proof}
The proof is by strong induction: \\

{\bf Base case:} 

A $2 \times 2$ courtyard can be tiled by one tile.
while a $2 \times 3$ courtyard can be tiled by two tiles. \\

{\bf Inductive step:} $n \geq 4$. \\

Take an $2 \times n$ courtyard and place a $2 \times 2$ tile.
What remains is  $2
\times (n-2)$, where $n - 2 > 3$.
So by strong inductive hypothesis, we can tile the rest of the courtyard. \\
\\

\end{proof}

{\bf Lemma 3:}
Any $3 \times n$ (and $n \times 3$) courtyard can be tiled\\

\begin{proof}

{\bf Base case:} A $3 \times 1$ courtyard can be tiled by 1 tile,

{\bf Inductive step:} Given a $n \times 3$ courtyard, the first row can
be tiled by Lemma 1.  The remaining is a $3 \times n-1$ courtyard that
can be tiled by the inductive hypothesis.

\end{proof}


$P(m) =$ ``Every $n \times m$ courtyard with $n \geq 4, m \geq 4$
can be tiled with the given tiles''.

We distinguish the following cases.

\begin{description}

\item[Cases 1] $m$ even, $m \geq 4$

Then the first two rows are $2 \times n$, $n \geq 4$, can be tiled by
Lemma 2. \\
Remove the first two rows.Then we have a $(m - 2) \times n$ courtyard. \\
If $m-2 = 2$ then it can be tiled by Lemma 2. \\
Otherwise $m - 2 \geq 4$, so it can be tiled by the inductive hypothesis. \\


\item[Case 2] $m$ odd, $m \geq 4$

So $m \geq 5$. \\

Then first three rows can be done, by Lemma 3. \\
Remove the first three rows to get a $(m - 3) \times n$ courtyard.\\
If $m - 3 = 2$ then we can do the rest by Lemma 2. \\
Else $m - 3 \geq 4$, then we can do rest by the inductive hypothesis.

Therefore every courtyard but the $n \times 1$ and $1 \times n$ 
with $n \not \equiv 0 \text{ mod } 3$ can be tiled.


\end{description}

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

{\bf Base case:}
The base case for $n=2$ is just DeMorgan's law.

{\bf Inductive step:}

\begin{eqnarray*}
(A_1 \cup A_2 \cup \ldots A_n \cup  A_{n+1})^c & = & 
(A_1 \cup A_2 \cup \ldots A_n)^c \cap A_{n+1}^c \\
& = &  A_1^c \cap A_2^c \cap \ldots A_n^c \cap A_{n+1}^c \\
\end{eqnarray*}

where the first step is from the base case, and the second step by the
inductive hypothesis.

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

\bigskip

This is a tricky problem, but one with a lot of solutions.
Here are some of them.

\begin{description}

\item[Solution 1]
We can use a change of variables to convert to the problem solved in the 
tutorial.  Let $m = n+k-1$ (Then $m \in \nat$ as long as not both $n$ and
$k$ are $0$.  However, the case for $n=k=0$ can be seen to hold since 
$0! | 0$).

Then you have to show that
$k! | m(m-1)\cdots(m-k+1)$ for all $k,m\in\nat$ which is just the problem 
solved in tutorial.

\item[Solution 2]
We can also solve this problem by a simple induction.
  
Let $P(n,k) = ``k! | n(n+1) \ldots (n+k-1)$''.

Note that if both $P(k-1,n)$ and $P(k,n-1)$ are true, then $P(k,n)$ is true
since 

\begin{equation}\label{eq2}
n(n+1) \ldots (n+k-1) = (n-1)n \ldots (n+k-2) + kn(n+1)\ldots(n+k-2)
\end{equation}

In particular, $P(k,n-1)$ implies that $k!$ divides the first term in the
right hand side of (\ref{eq2}), and $P(k-1,n)$ implies that $k!$ divides
the second term.

How do we convert this into a simple induction?  Well, we could use the
following as an inductive hypothesis.

$Q(r) = ``\forall k,n \in \nat$ such that $k+n=r$, $P(k,n)$ is true''.

{\bf Base case:}
$Q(0)$ is true since $r=0$ only if $k=n=0$ and $P(0,0)$ is true because
$0! | 0$.

{\bf Inductive step:}
Assume that $Q(r)$ is true in order to show that $Q(r+1)$ is true.
Notice that if $k+n = r+1$, then $k+n-1 = r$, so in particular,
by the inductive hypothesis, $P(k-1,n)$ and $P(k,n-1)$ are true 
(for $k>0, n>0$).
But we have noted earlier that if both $P(k-1,n)$ and $P(k,n-1)$ are
true, then $P(k,n)$ is also true.  Therefore $Q(r)$ is true.

Now we treat the special cases $k=0$ or $n=0$.  Note that $P(0,n)$ is
true $\forall n \in \nat$, because $0!  = 1$ divides all the naturals.
$P(k,0)$ is also true  $\forall k \in \nat$ since $0$ is divided by all
nonzero natural numbers.


\item[Solution 3]

Lastly, we could use a nested induction, although this is very tricky and 
is not recommended. Here is what the argument might look like.

First we define the proposition

(IH1)	$P(k) = ``\forall n \in \naturals, k! | n(n+1) \ldots(n+k-1)$''.

We want to prove $\forall k \in \naturals, P(k)$

{\bf Base case: } $k=0$.  

$P(0)$ is true since $0! = 1$ divides every natural number.

{\bf Inductive step: } 
Assume $P(k)$ is true.  We will show 

$P(k+1)= ``\forall n \in \naturals, (k+1)! n(n+1)\ldots(n+k)$''.

We will prove $P(k+1)$ by induction on $n$.
Let 

\begin{indent}
(IH2)	$Q(n) = ``(k+1)! | n(n+1)\ldots(n+k)$.''

{\bf Base case: } $Q(1) = ``(k+1)! | 1\cdot 2 \ldots (k+1)$''.

This is obviously true by the definition of $(k+1)!$.

{\bf Inductive step: }  Assume $Q(n)$ is true.  We will show 

$Q(n+1) = ``(k+1)! | (n+1)(n+2) \ldots (n+k+1)$''.

We expand the right hand side

\begin{eqnarray*}
(n+1)(n+2)\ldots (n+k+1) & = & n(n+1)\ldots (n+k) + 
(n+1)(n+2) \ldots (n+k)(k+1).
\end{eqnarray*}

\end{indent}

Now, by the inductive hypothesis (IH2), 
$(k+1)! | n(n+1)\ldots(n+k)$, while by the inductive hypothesis
(IH1) (used for $n+1$), $k! | (n+1)(n+2)\ldots(n+k) \rightarrow
(k+1)! | (n+1)(n+2)\ldots(n+k)(k+1)$.

The proof is complete.

\end{description}

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


\bigskip

We will use induction.  The inductive statement is

$P(n)=$ ``In an n-player tournament where there is no player that beats 
everybody else, there exists a natural number $k \leq n$ and a collection
of players $p_1, \ldots ,p_k$ such that $p_i$ beats $p_{i+1}$ and $p_k$ beats
$p_1$''. 

{\bf Base case:}
The base case for $n=2$ is true since there is always a player who beats 
everyone else.

{\bf Inductive step:}
Assume that $P(n)$ is true in order to show that $P(n+1)$ is true.

Consider a (n+1)-player tournament where there is no player that beats everybody else.
Take any player out (call him/her $p_1$) and consider the remaining $n$-player 
tournament.  There are two cases:

1) There is no player that beats everybody else.

2) There is some player that beats everybody else.

If the case is (1), then by the inductive hypothesis there is a cycle of
players so we are done.

If the case is (2), then there is some player (say $p_2$)
 that beats everybody else in the $n$-player tournament.  Then, because of the
hypothesis that no one beats everybody in the ($n+1$)-player tournament, 
we have
that $p_1$ beats $p_2$.  Also, because of the same hypothesis, there is some 
player (call him/her $p_3$) that beats $p_1$.  Furthermore $p_3$ is beaten 
by $p_2$.  So we have found a number $k = 3$ and a cycle 
$p_1 \rightarrow p_2 \rightarrow p_3 \rightarrow p_1$ of players that
satisfy the inductive statement.

Note that what we have proved here is the somewhat stronger statement that in 
any tournament where there is no player that beats everybody, there exist
a set of three players $p_1,p_2,p_3$, such that $p_1$ beats $p_2$,
$p_2$ beats $p_3$, and $p_3$ beats $p_1$.
\end{problems}

\end{document}








