\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\newcommand{\mod}{ \mbox { mod }}

\begin{document}

\section*{Tutorial 2}

We'll look at several more examples of proof by induction.  Aside from
the induction method, these examples demonstrate some math that comes
up a lot in computer science: sets, Boolean variables, and modular
arithmetic.  After that, we'll look at some variations on induction
and wrap up with some team problems.

\section{Examples of Proof by Induction}
\begin{theorem} (Distributive Law)
Let $A, B_1, B_2, \ldots, B_n$ be sets where $n \geq 1$.  Then

$$A \cap (B_1 \cup B_2 \cup \ldots \cup B_n) =  (A \cap B_1) \cup \ldots \cup (A \cap B_n).$$
\end{theorem}

We saw a special case of this theorem last week in tutorial.  In
particular, we looked at the case of $n = 2$, i.e. $A \cap (B_1 \cup
B_2) = (A \cap B_1) \cup (A \cap B_2)$.  This was proven by showing
that each of set contains the other.  We will actually use this result
in the proof below of the more general theorem.

Here is the game plan for the proof.  We'll take the induction
hypothesis directly from the theorem statement.  This means that in
the inductive step, we will have to show that $A \cap (B_1 \cup B_2
\cup \ldots \cup B_n \cup B_{n+1})$ is equal to $(A \cap B_1) \cup
\ldots \cup (A \cap B_n \cup (A \cap B_{n+1})$.  We can almost do
this; by induction, we can transform the almost-as-big expression $A
\cap (B_1 \cup B_2 \cup \ldots \cup B_n)$ into something good.  All
that remains is to handle that extra term, $B_{n+1}$.  We'll do this
by using the $n=2$ result from last week.

This basic strategy, proving something for $n = 2$ and then
generalizing with induction, is very common.  In fact, we'll use
exactly the same approach in the next example as well.

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

{\em Induction hypothesis: } Let $P(n)$ be the predicate

$$A \cap (B_1 \cup B_2 \cup \ldots \cup B_n) =  (A \cap B_1) \cup \ldots \cup (A \cap B_n).$$

{\em Base case: } $P(0)$ is true because both sides of the equation
are equal to $A$.

{\em Inductive step: } For all $n \geq 0$, assume

$$A \cap (B_1 \cup B_2 \cup \ldots \cup B_n) =  (A \cap B_1) \cup \ldots \cup (A \cap B_n)$$

in order to prove

$$A \cap (B_1 \cup B_2 \cup \ldots \cup B_n \cup B_{n+1}) = (A \cap
B_1) \cup \ldots \cup (A \cap B_n) \cup (A \cap B_{n+1}).$$

Let $C = B_1 \cup B_2 \cup \ldots \cup B_n$.  Then we can rewrite the
left side of $P(n+1)$ as follows:

\begin{eqnarray*}
A \cap (B_1 \cup B_2 \cup \ldots \cup B_n \cup B_{n+1})
	& = & A \cap (C \cup B_{n+1}) \\
	& = & (A \cap C) \cup (A \cap B_{n+1}) \\
	& = & (A \cap (B_1 \cup B_2 \cup \ldots \cup B_n))
		\cup (A \cap B_{n+1}) \\
	& = & (A \cap B_1) \cup \ldots \cup (A \cap B_n)
		\cup (A \cap B_{n+1}) \\
\end{eqnarray*}

In the first step, we replace a bunch of terms with the variable $C$.
This simplifies the original expression enough so that we can use the
result from last week, which gives the second equality.  In the third
step, we substitute that bunch of terms back for $C$ so that in the
last step, we can use the induction hypothesis.  This proves that for
all $n \geq 0$, $P(n) \Rightarrow P(n+1)$.  \qed

Last week in lecture we saw DeMorgan's Law, $\overline{A \cup B} =
\overline{A} \cap \overline{B}$ where $A$ and $B$ are sets.  Now, this
is going to be confusing, but there is a closely related law about
Boolean variables that is also called DeMorgan's Law!  DeMorgan's Law
for boolean variables is $\overline{x \vee y} = \overline{x} \wedge
\overline{y}$ where $x$ and $y$ are Boolean variables.  We can prove
this with the truth table method:

\[
\begin{array}{c|c|c|c}
x & y & \overline{x \vee y} & \overline{x} \wedge \overline{y}\\ \hline
T & T & F & F \\
T & F & F & F \\
F & T & F & F \\
F & F & T & T 
\end{array}
\]

By inspection of the truth table, $\overline{x \vee y} = \overline{x}
\wedge \overline{y}$ in all cases.

The next theorem generalizes DeMorgan's Law to an arbitrary number of
boolean variables in much the same way that the previous theorem
generalized the distributive law to an arbitrary number of sets.

\begin{theorem} (DeMorgan's Law)
For Boolean variables $x_1,x_2,\ldots,x_n$ and $n \geq 1$,
$$\overline{(x_1 \vee x_2 \vee \ldots \vee x_n)} = \overline{x_1}
\wedge \overline{x_2} \wedge \ldots \wedge \overline{x_n}.$$
\end{theorem}

We will follow the same strategy as before.  $P(n)$ and $P(n+1)$ are
very similar except that $P(n+1)$ contains one more variable.  We will
bridge this gap between $P(n)$ and $P(n+1)$ with the two-variable
special case of the theorem proven above.

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

{\em Induction hypothesis: }  Let $P(n)$ be the predicate:

$$\overline{(x_1 \vee x_2 \vee \ldots \vee x_n)} = \overline{x_1} \wedge
  \overline{x_2} \wedge \ldots \wedge \overline{x_n}$$
 
{\em Base case: } The predicate $P(1)$ true because both sides are
equal to $\overline{x_1}$.

{\em Inductive step: }
For all $n \geq 1$ assume

$$\overline{(x_1 \vee x_2 \vee \ldots \vee x_n)} = \overline{x_1}
\wedge \overline{x_2} \wedge \ldots \wedge \overline{x_n}$$

in order to prove

$$\overline{(x_1 \vee x_2 \vee \ldots \vee x_n \vee x_{n+1})} =
\overline{x_1} \wedge \overline{x_2} \wedge \ldots \wedge \overline{x_n}
\wedge \overline{x_{n+1}}.$$

Let $y = (x_1 \vee x_2 \vee \ldots \vee x_n)$. Then we can rewrite the
left side of $P(n+1)$ as follows:

\begin{eqnarray*}
\overline{(x_1 \vee x_2 \vee \ldots \vee x_n \vee x_{n+1})}
	& = & \overline{(y \vee x_{n+1})} \\
	& = & \overline{y} \wedge \overline{x_{n+1}} \\
	& = & \overline{x_1 \vee x_2 \vee \ldots \vee x_n} \wedge
\overline{x_{n+1}} \\
	& = & \overline{x_1} \wedge \overline{x_2} \wedge \ldots
\wedge \overline{x_n} \wedge \overline{x_{n+1}}
\end{eqnarray*}

The rationale for each step exactly parallels the previous proof.  In
the first step, we replace a bunch of terms with the variable $y$.
This simplifies the original expression so that we can use the two
variable result.  This gives the second equality.  In the third step,
we substitute the bunch of terms back for $y$.  Finally, we use the
induction hypothesis.  This proves that for all $n \geq 0$, $P(n)
\Rightarrow P(n+1)$.  \qed

\subsection*{A Review of Modular Arithmetic}

Recall the funny $\equiv$ and $\bmod$ notation from lecture: $x \equiv
y \pmod{q}$ iff $q \: | \: (x-y)$.  In words, this says $x$ is
``congruent'' to $y$ ``mod'' $q$ if and only if $q$ evenly divides $x
- y$.  For example, $15 \equiv 3 \pmod{6}$ since $6$ evenly divides
$15 - 3 = 12$.

While $x \equiv y \pmod{q}$ is a statement, like an equation, the
similar-looking notation $a \bmod b$ stands for a quantity, like $a /
b$.  In particular, $a \bmod b$ is the remainder when $a$ is divided
by $b$.  More precisely, this is the number $r$ such that $a = bq+r$
where $q$ is an integer and $0 \leq r < b$.  The number $b$ is
required to be at least 1.  For example, $15 \bmod 6$ is equal to 3
because $15 = 6 \cdot 2 + 3$.

\begin{theorem}
If $n$ is an positive odd integer, then $n^2 \equiv 1 \pmod{8}$.
\end{theorem}

This theorem is a little different in that we are not required to
prove a result for all positive $n$, but just for positive {\em odd}
$n$.

There are two ways to handle this problem.  One approach is to
reformulate the theorem: if $k \geq 0$, then $(2k+1)^2 \equiv 1 \pmod
8$.  It is easy to see that this is equivalent to the original
theorem, since the expression $2k+1$ will take on all positive odd
values as $k$ takes on all non-negative values.  Now an ordinary
prooby by induction on $k$ will work.

A second approach is to use a variant of induction.  Suppose that we
prove proposition $P(1)$ and prove that for all positive odd integers
$n$, $P(n) \Rightarrow P(n+2)$.  Then we should believe that $P(1),
P(3), P(5), \ldots$ are all true for the same reason that we believe
ordinary induction works.  In effect, we introduce a new axiom just as
credible as the original induction axiom.  We will use this second
approach in the proof.

Introducing new induction-like axioms all the time might not seem like
a good idea.  But all of these little variants on induction can be
proven from the simple, original axiom.  So there is no great harm.
The key point is that there must be a chain of implications extending
from each predicate back to the base case (or cases).

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

{\em Induction hypothesis: } Let $P(n)$ be the predicate $n^2 \equiv 1
\pmod{8}$.

{\em Base case: } $P(1)$ is true because $1^2 \equiv
1 \pmod{8}$.

{\em Inductive step: } For all $n \geq 1$ assume that $n^2 \equiv 1
\pmod{8}$ and $n$ is a positive odd integer to show that $(n+2)^2
\equiv 1 \pmod{8}$.  Since $n$ is an odd integer, $4n + 4 \equiv 0
\pmod{8}$.  Adding this to the induction hypothesis implies $n^2 + 4n
+ 4 \equiv 1 + 0 \pmod{8}$.  Rewriting the left side gives $(n+2)^2
\equiv 1 \pmod{8}$.  Therefore for all positive odd $n$, $P(n)
\Rightarrow P(n+2)$.  \qed

This proof contains a little mystery.  Where did the magic term $4n +
4$ come from?  Here is the reasoning that one might follow to discover
the inductive step in this proof.  We want to prove that $(n+2)^2
\equiv 1 \pmod{8}$, and we can assume that $n^2 \equiv 1 \pmod{8}$.
To go from the assumption to the desired result, we need to add a
little bit to the left side, changing $n^2$ to $(n+2)^2$.  The value
of this little bit is $(n+2)^2 - n^2 = 4n + 4$.  We lucked out
because, it is not hard to see that this is always a multiple of 8
when $n$ is odd.  Arranging these observations into a straight line of
reasoning gives the proof.

\section{Proving Statements with Two Variables}

Sometimes the statement of a theorem involves two natural-valued
variables.  In such situations, panicking is not strictly necessary,
but sometimes unavoidable.  Here is an example:

\begin{theorem}
For all $n$ and $k$ such that $n \geq k \geq 0$, $k!$ divides
$n(n-1)(n-2) \ldots (n-k+1)$.
\end{theorem}

First a notation clarification.  If $k = 0$, then the expression
$n(n-1)(n-2) \ldots (n-k+1)$ is a product with no terms, which we
define to be $1$.  If $k=1$, then the expression is $n$.

There are several ways to approach this problem.  One way is to define
a sort of two-dimensional array of predicates $Q(n, k)$.  Then we
could prove sufficient base cases and implications so that every
predicate $Q(n, k)$ followed from some proven bases cases through a
chain of proven implications.  The theorem would then follow from a
fancy variant of the induction axiom.

A second approach is to eliminate a variable and use ordinary
induction.  Eliminating a variable may not be easy.  The next two
theorems will demonstrate different ways that sometime work.

The first way is to introduce a quantifier into the induction
hypothesis.  In this example, we can use the hypothesis, ``For all $k$
such that $n \geq k \geq 0$, $k! \mid n(n-1) \ldots (n-k+1)$.  If we
prove this statement for all $n \geq 0$, then we have proven the
theorem.  Though the induction hypothesis contains two variables, we
only need to induct on $n$; you never have to induct on a quantified
variable.  In effect, we will prove a whole row of $Q(n, k)$
predicates in each step of the proof.

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

{\em Induction hypothesis: } Let $P(n)$ be the predicate that for all
$k$ such that $n \geq k \geq 0$, $k! \mid n(n-1) \ldots (n-k+1)$.

{\em Base case: } $P(0)$ is true because $k$ is then restricted to be
0, and $0! = 1$ divides every integer.

{\em Inductive step: } Assume that for all $k$ such that $n \geq k
\geq 0$, $k! \mid n(n-1) \ldots (n-k+1)$ in order to prove that for
all $k$ such that $(n+1) \geq k \geq 0$, $k! \mid (n+1)n(n-1) \ldots
(n-k+2)$.

There are three cases to check.  If $k = 0$, then the statement is
true because $0! \mid 1$.  If $k = n+1$, then the statement is true
because $(n+1)! \mid (n+1)n(n-1) \ldots (1)$.

All that remains is to prove that $k! \mid (n+1)n(n-1) \ldots (n-k+2)$
for $k$ in the range $n \geq k > 0$.  By induction we know:

\begin{eqnarray*}
& & k! \mid n (n-1) \ldots (n-k+1) \\
& & (k-1)! \mid n (n-1) \ldots (n-k+2)
\end{eqnarray*}

(We need to use these two facts, and this is the reason why $k = 0$
and $k = n+1$ are treated as special cases.  If $k = n + 1$, then the
first fact does not follow by induction.  If $k = 0$, then the second
fact does not follow.)

If we multiply both sides of the second fact by $k$, and then add both
facts together, we obtain:

\begin{eqnarray*}
&  & k! \mid n (n-1) \ldots (n-k+1) + k n (n-1) \ldots (n-k+2) \\
& \Rightarrow & k! \mid ((n-k+1) + k) n (n-1) \ldots (n-k+2) \\
& \Rightarrow & k! \mid (n+1) n (n-1) \ldots (n-k+2)
\end{eqnarray*}

This shows that for all $n \geq 0$, $P(n) \Rightarrow P(n+1)$ and
completes the proof.  \qed

The algebra in this proof is sneaky and one probably woudn't think of
this proof right away.  The key idea here is working with a quantifier
in the induction hypothesis.

\subsection*{Sharing Chocolate}

We are given a chocolate bar with $m \times n$ squares of chocolate
and our task is to divide it into $mn$ individual squares.  We are
only allowed to split one piece of chocolate at a time using a
vertical or a horizontal break.

For example, suppose that the chocolate bar is $2 \times 2$.  The
first split makes two pieces, both $2 \times 1$.  Each of these pieces
requires one more split to form single squares.  This gives a total of
three splits.  We would like to prove the following general result:
 
\begin{theorem}
To divide up a chocolate bar with $m \times n$ squares, we need exactly
$m n - 1$ splits.
\end{theorem}
 
Once again, we have two variables.  If one variable can be eliminated,
then ordinary induction will suffice.  We could try the previous
technique of formulating an induction hypothesis with a quantifier.

But let's try a second approach.  Intuitively, to break up a big
chocolate bar, we need one split to make two pieces, and then we can
break up the two pieces recursively.  This suggests a proof using
strong induction on the {\em size} of the chocolate bar.  The size can
be defined to be $m n$, the area measured in chocolate squares.

This gives a second trick for using ordinary induction to prove a
theorem with two variables: apply induction on a {\em function} of the
variables.

{\em Proof. } The proof is by strong induction on $m n$.
 
{\em Inductive hypothesis: } Let $P(k)$ be the predicate that a
chocolate bar of size $k$ requires $k - 1$ splits.

{\em Base case: } In the base case, $P(1)$ is true because there is
only a single square of chocolate and so $1 - 1 = 0$ splits are
required.

{\em Inductive step: } For all $k \geq 1$, assume that a chocolate bar
of size $s$ requires $s-1$ splits where $k \geq s \geq 1$ in order to
prove that a chocolate bar of size $k+1$ requires $k$ splits.

First, we will have to break the chocolate bar of size $k+1$ into two
smaller pieces of size $p$ and $q$ where $p + q = k + 1$.  Then, by
strong induction, breaking up the two pieces will require $p - 1$ and
$q - 1$ splits.  The total number of splits is therefore $1 + (p - 1)
+ (q - 1) = p + q - 1 = (k + 1) - 1 = k$.  \qed

\section{Team Problems}

\begin{enumerate}
\item {\em Handshakes. } 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 your answer.

\item {\em Geometric mean vs Arithmetic mean. }  Show that for any
non-negative real numbers $x_1,x_2,\ldots,x_n$,
$$(x_1x_2\ldots x_n)^{\frac{1}{n}} \leq \left( x_1 + x_2 + \ldots + x_n \over n \right) $$ 
\end{enumerate}

\end{document}


