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

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial2}{Problems for Tutorial 2}{February 18, 1997}

\section{Warmup}

{\it 
Prove by induction on $k$ that 
$$
5 \mid  (3^{2k} + 4^{k+1})
$$
for any integer $k\geq 0$. 
}

Inductive Hypothesis(k): $5 \mid  (3^{2k} + 4^{k+1})$.

BASE CASE: k=0 \\
$3^{2 \cdot 0} + 4^{0+1} = 1+4=5$ which is divisble by 5.

INDUCTIVE STEP: $H(k) \rightarrow H(k+1)$ \\

By the inductive hypothesis, $5 \mid  3^{2k} + 4^{k+1}$, so
$3^{2k} + 4^{k+1} = 5q$

\begin{eqnarray*}
3^{2(k+1)} + 4^{(k+1)+1} &=& 3^{2k+2} + 4^{k+1+1} \\
&=&9 \cdot 3^{2k} + 4 \cdot 4^{k+1}  \\
&=&10 \cdot 3^{2k} + 5 \cdot 4^{k+1} - (3^{2k} + 4^{k+1}) \\
&=5 (2 \cdot 3^{2k} + 4^{k+1}) - 5q \\
&=&5 (2 \cdot 3^{2k} + 4^{k+1}  - q)\\
\end{eqnarray*}
So $5 \mid 3^{2(k+1)} + 4^{(k+1)+1}$.

\section{Peano Strikes Back}

{\em
Recall that addition was defined by:

D1)  $ \forall n \in \naturals, n+0 = 0+n=0$ 

D2)  $ \forall n,m \in \naturals, n+m' = (n+m)'$

Prove by induction the cancelation law of addition. 

$$
 \forall n,m,k \in \naturals, n+k = m+k \implies n = m
$$ 
}

Induct over $k$ \\
BASE CASE: $k=0$ \\
$\forall n,m \in \naturals, n+0 = m+0 \implies n = m$ by D1.

INDUCTIVE STEP: $H(k) \rightarrow H(k+1)$ \\
$\forall n,m \in \naturals, n+k' = m+k' \implies $ \\
$\forall n,m \in \naturals, (n+k)' = (m+k)' \implies $  (by D2)\\
$\forall n,m \in \naturals, (n+k) = (m+k) \implies $  (by Peano's axioms)\\
$\forall n,m \in \naturals, n = m$  (by the inductive hypothesis).





\section{Handshaking Problem}

{ \em I recently went to a party with my spouse; there were 11 other
married couples there.  A lot of handshaking happened (but of course
no one shook hands with their spouse).  At the end, it turned out that
for every $k$ from $0$ to $22$, someone other than me had shaken hands
with exactly $k$ people.  How many people did I shake hands with?
Prove it. }

Note that there are 24 people (12 couples).

Think of this problem as couples taking turns walking around and shaking 
people's hands, and then leaving the room.  Number the couples $0$ through $11$.

Our inductive hypothesis, $H(n)$, is that when the $n$th couple shakes hands,
one spouse shakes hands $n$ times, and the other shakes hands $22-n$ times.
Furthermore, everyone who hasn't walked around yet has shaken hands $n+1$
times.

BASE CASE: $n=0$ \\
If someone has shaken hands 22 times, they shook hands with everyone
except themselves and their spouse.  Since someone had to shake hands 0
times, their spouse had to have shaken hands with noone.  Furthermore,
everyone else has shaken hands once, since the first spouse shook hands
with 22 different people.

INDUCTIVE STEP: $H(n) \rightarrow H(n+1)$

When the next couple walks around to shake hands with everyone who's left, 
everyone has shaken hands $n+1$ times by the inductive hypothesis.  
Since someone must shake hands exactly
$n+1$ times, (and since, by our hypothesis, we don't know who this is 
yet, but we do know who's shaken hands $0$ thru $n$ times), 
one of the spouses doesn't shake hands with anyone.  Since someone
must shake hands exactly $22-n$ times, the other spouse, who has shaken
hands $n$ times already, must shake hands with all of the remaining $22-2n$
people for a total of $22-n$ times, otherwise no one will be able to shake
hands $22-n$ times because there won't be enough people left.  All the
remaining people have now shaken hands one additional time, for a total
of $n+2$ times. 

This shows that $H(n) \rightarrow H(n+1)$, since one spouse shakes hands
$22-n$ times, another $n$ times, and the total number of handshakes done
by everyone left is $n+2$.

Since we know that no one can shake hands more than 22 or less than 0 times,
the speaker must shake hands the same number of times as someone else.
Examining the inductive hypothesis, we realize that the extra person must
shake hands $11$ times, since two people shake hands $11$ times (when $n=11$).

\bigskip


\end{document}

 






