\documentstyle[12pt,twoside,amstex]{article}

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}

\newtheorem{method}{Method}
%\newcommand{\mod}{ \mbox { mod }}

\begin{document}

\handout{tut2}{Notes for Recitation 2 (9/18/98)}{September 18, 1998}

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}


\subsection*{Induction Proof Method}

While the plan for writing an induction proof is clear, there is no
rigid plan for finding such a proof.  There are, however, a few good
tricks to know.  There are usually two difficulties in completing a
proof by induction: choosing the right induction hypothesis $P(n)$ and
completing the inductive step.  (Sometimes proving the base case is
also hard.)  The most obvious candidate for an induction hypothesis is
the theorem statement itself.

\begin{method}
When searching for a proof by induction, first try to lift an
induction hypothesis directly from the theorem statement.
\end{method}

To complete the inductive step, we must prove that for all $n \geq 0$,
$P(n) \Rightarrow P(n+1)$.  Typically $P(n)$ and $P(n+1)$ are very
similar statements, but with some small difference or gap.  The
challenge is to clearly identify this gap and then to bridge it with
some extra facts.  Working ``backward'' is often helpful.

\begin{method}
To prove $P(n) \Rightarrow P(n+1)$, write down $P(n+1)$ and then use
$P(n)$ to reduce this statement to a simpler assertion; this assertion
is the extra fact needed to bridge the gap from $P(n)$ to $P(n+1)$ and
complete the proof.
\end{method}

\subsection*{Examples}

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

\iffalse
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!  
\fi

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 $\equiv\bmod$ notation from Rosen 2.3: $x \equiv y \pmod{q}$
iff $q | (x-y)$ for integers $x,y,q$.  In words, this says $x$ is
``congruent'' to $y$ ``mod'' $q$ if and only if $q$ evenly divides $x -
y$; another way to formulate this is to say that $x$ and $y$ have the same
remainder after division by $q$.  For example, $15 \equiv 3 \pmod{6}$ since
$6$ evenly divides $15 - 3 = 12$; both 15 and 3 have remainder 3 after
division by 6.

While $x \equiv y \pmod{q}$ is a statement, like an equation, the
similar-looking notation $a \bmod b$ stands for an integer quantity,
namely, $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$.
Now we have:
\[x \equiv y \pmod{q} \quad \mbox{iff} \quad [x \bmod{q} = y \bmod{q}].\]

\iffalse
\begin{theorem}
$\forall n \in \naturals: n^3 \equiv n \pmod{3}$
\end{theorem}

We can apply these principles to obtain a proof by induction of the
preceding theorem.  To begin, we can lift the induction hypothesis
directly from the theorem statement.  Let $P(n)$ be the predicate $n^3
\equiv n \pmod{3}$.  Second, we have to prove that for all $n \geq 0$,
$P(n) \Rightarrow P(n+1)$.  Using the definition of $\equiv \pmod{3}$, the
predicate $P(n+1)$ is equivalent to $3 \mid (n+1)^3 - (n+1)$.  Expanding
terms in $P(n+1)$ gives $3 \mid n^3 + 3n^2 + 2n$.  We can now use $P(n)$
to simplify $P(n+1)$ by subtracting off the quantity that $P(n)$ asserts
is divisible by 3.  This gives $3 \mid 3n^2 + 3n$.  This obvious statement
is the extra fact needed to bridge the gap from $P(n)$ to $P(n+1)$.  In
short, we can show that $P(n)$, together with the extra fact $3 \mid 3n^2
+ 3n$, implies $P(n+1)$.  Here is the concise proof:

\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition $n^3 \equiv n
\pmod{3}$.  In the base case, the proposition is true because $n^3 = n =
0$ and $3 \mid (0 - 0)$.  For $n \geq 0$, assume $3 \mid n^3 - n$ to prove
$3 \mid (n+1)^3 - (n+1)$.

\begin{eqnarray*}
& & 3 \mid (n^3 - n) \\
& \Rightarrow & 3 \mid (n^3 - n) + 3 (n^2 + n) \\
& \Rightarrow & 3 \mid n^3 + 3n^2 + 3n + 1 - n - 1 \\
& \Rightarrow & 3 \mid (n+1)^3 - (n+1)
\end{eqnarray*}

The first implication follows because $3 (n^2 + n)$ is divisible by 3.
The remaining implications involve only rewriting the expression on the
right.  This proves that for all $n \in \naturals$, $P(n)$ implies
$P(n+1)$, completing the proof.
\end{proof}

The final concise proof might seem mysterious to anyone not privy to the
scratchwork we did beforehand.  For example, one might ask how we had the
foresight to introduce the magic term $3 (n^2 + n)$.  Of course, this was
not foresight at all; we worked backward.

By the way, there is also a simple direct proof of this theorem w/o
induction:
\[n^3-n = n(n^2 -1) = n (n+1) (n-1) = (n-1) n (n+1).\]
But $n-1, n$, and $n+1$ are three consecutive integers, so one of them
must be divisible by 3.  Hence, $3 \mid n^3-n$. \qed

\fi
%NOT USED S98: From F97 recitation notes:
\begin{theorem}
If $n$ is an positive odd integer, then $n^2 \equiv 1 \pmod{8}$.
\end{theorem}

%{\bf COMMENT by ARM, Feb 1998}: the proof given in F97 was by induction,
%involving more cumbersome reasoning than the following simple equational
%reasoning.  So we prexsumably need another induction example hear.

%proof: Say $n=2k+1$, so $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1$.
%But since either $k$ or $k+1$ is even, $4k(k+1)$ is divisible by $4\cdot 2
%= 8$, so $n^2 = 8m +1$ for some $m$.  (Note that this proof works fine for
%all odd $n$, not just positive ones.) \qed


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
proof by 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 wouldn'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}

\iffalse
\item %From F97 PS2 Problem 10, much revised:

An $n$-player tournament, consists of some set of $n\geq 2$ elements
called {\em players}, and, for every two distinct players, a specification
that one of the players beats the other.  That is, player $p_1$ beats
player $p_2$ iff $p_2$ does not beat $p_1$, for all players $p_1 \neq
p_2$, and no player beats him/herself.

A sequence 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$ is called a
{\em ranking} of these players.  If also player $p_k$ beats player $p_1$,
the ranking is called a $k$-{\em cycle}.

(a) Prove that in every tournament, either there is a ``champion'' player
that beats every other player, or there is a 3-cycle.

{\bf Solution}: (Proof by induction.)  The induction hypothesis $P(n)$, is
``In an $n$-player tournament, either there is a player that
beats every other player, or there is a 3-cycle.''

{\bf Base case $n=2$:} By definition of a 2-player tournament, one of the
players beats the only other player and therefore is the champion.

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

Consider an $n+1$-player tournament.  If there is a champion, we are done.
So we may assume that every player is beaten by some other player.  Now
remove any player, say player $p$, and treat the remaining $n$ players as an
$n$-player tournament.  There are two cases:

1) Every player in the $n$-player tournament is beaten by some other
player in the tournament.

2) There is some champion in the $n$-player tournament who beats every
other player in the $n$-player tournament.

In case (1), we have by induction hypothesis a 3-cycle of players in the
$n$-player tournament.  Since a 3-cycle in the $n$-player tournament will
also be a 3-cycle in the full $n+1$-player tournament, we are OK in this
case.

In case (2), there is some ``champion'', $q$, in the $n$-player
tournament.  Since everybody in the ($n+1$)-player tournament is beaten by
somebody, $q$ must be beaten by a player not in the $n$-player tournament,
that is, $p$ beats $q$.  For the same reason, there is some
player $r$ that beats $p$.  Since $r$ is in the $n$-player tournament, $r$
is beaten by the champion $q$.  So we have found a 3-cycle $p,q,r$.

\medskip
(b) A {\em consistent ranking} is a sequence $p_1,p_2, \ldots, p_n$ of all
$n$ players in the tournament such that $p_i$ beats $p_j$ iff $i < j$, for
$1 \leq i,j \leq n$.  Conclude that a tournament has no consistent ranking
iff some subset of three of its players has no consistent ranking.

\item
The well-matched strings of left and right parentheses, {\em WMP}'s
for short, are defined inductively as follows:
\begin{itemize}

\item The string of length two consisting of a left parenthesis followed
by a right parenthesis, namely, {\tt ()}, is a WMP.

\item If $W_1W_2\dots W_k$ is a sequence of $k\geq 1$ WMP's, then $\mbox{\tt
(}W_1W_2\dots W_k\mbox{\tt )}$ is a WMP.
\end{itemize}

The {\em count} of a string of one or more parentheses is defined as
follows:
\begin{itemize}
\item $\mbox{count}(\mbox{\tt)}) = -1$,
\item $\mbox{count}(\mbox{\tt(}) = 1$,
\item of $s$ is a string of parentheses and $p$ is a single parenthesis,
then  $\mbox{count}(sp) = \mbox{count}(s) + \mbox{count}(p)$.
\end{itemize}

A string, $Z$, of one or more parentheses is a {\em well-counting} string
of parentheses, a {\em WCP} for short, iff $\mbox{count}(Z) = 0$ and
$\mbox{count}(X)> 0$ for any proper prefix, $X$, of $Z$.  ($X$ is a {\em prefix}
of $Z$ means that $Z = XY$ for some string $Y$.  $X$ is a {\em proper}
prefix if it is a prefix of $Z$ and its length is positive and strictly
less than the length of $Z$.)

(a) Prove that every WMP is a WCP.

{\bf Solution}: First prove that every WMP is a WCP, by strong induction
on the length of the WMP:
\[P(n) ::\equiv \mbox{If $W$ is a length $n$ WMP, then $W$ is a WCP}.\]

{\bf Base Cases}: $n\leq 2$. $W = \Code{()}$ is the only possible WMP of
length $\leq 2$.  Now $W$ has count $1 = -1 = 0$, and its only proper
prefix is the initial left parenthesis, which has count 1.  So $W$ is a
WCP.

{\bf Inductive Step:} Assume $P(k)$ is true for all $k\leq n$.  We need to
show that $P(n+1)$ holds.

Let $W$ be a length $n+1$ WMP for $n\geq 2$.  By definition of WMP, $W =
\Code{(}W_1W_2...W_k\Code{)}$, where $W_i$ is a WMP for $1\leq i \leq
k$.  By inductive hypothesis, $W_i$ is a WCP for each $i$.

We note the ``obvious'' fact (which itself could be proved by induction if
need be) that for any strings of parentheses $U, V$,
\[\mbox{count}(UV) = \mbox{count}(U) + \mbox{count}(V).\]
From this, we have
\begin{eqnarray*}
\mbox{count}(W)&=&\mbox{count}(\Code{(}W_1W_2\ldots W_k\Code{)})\\
&=&\mbox{count}(\Code{(}) + \mbox{count}(W_1) + \dots + \mbox{count}(W_k)
+ \mbox{count}(\Code{)})\\
&=&1+0+\dots+0-1\\
&=&0.
\end{eqnarray*}

Now let $X$ be a proper prefix of $W$.  We must show that
$\mbox{count}(X)>0$.  But $X$ must be of the form:
\[X=\Code{(}W_1W_2\ldots W_jY\]
for some $j<k$ and $Y$ a prefix of $W_{j+1}$.  Since $W_{j+1}$ is a WCP,
$\mbox{count}(Y)\geq 0$.  So
\begin{eqnarray*}
\mbox{count}(X)
&=&\mbox{count}(\Code{(}) + \mbox{count}(W_1) + \dots + \mbox{count}(W_j)
+ \mbox{count}(Y)\\
&=& 1+0+\ldots+0+\mbox{count(}Y)\\
&\geq&1+0 > 0.
\end{eqnarray*}
\qed

\medskip
(b) Conversely, prove that every WCP is a WMP.

{\bf Solution}: we show that every WCP is a WMP by induction on the length
of the WCP:
\[Q(n) ::\equiv \mbox{If $W$ is a length $n$ WCP, then $W$ is a WMP}.\]

{\bf Base Cases}: $n\leq 2$.  It follows from the definition of the count
of a string of parentheses that the only WCP with length $\leq 2$ is
\Code{()}.  This string is a WMP by definition.

{\bf Inductive Step:} Assume that $Q(k)$ is true for all $k\leq n$, we
need to prove that $Q(n+1)$ is also true.  Let $X$ be a length $n+1$ WCP
for any $n\geq 2$.

Any WCP it must be of length $\geq 2$, so it must begin with a
parenthesis, and this parenthesis is a proper prefix of the WCP.  Since
the count of that parenthesis must be positive, it has to be a left
parenthesis.  Likewise, any WCP must end with a right parenthesis.

So $X = \Code{(}Y\Code{)}$ for some string $Y$.  Since the counts of
the initial and final parentheses, namely 1 and -1, sum to zero, and
$\mbox{count}(X)=0$, it must also be the case that $\mbox{count}(Y)=0$.
Also, since any proper prefix of $X$ is a left parenthesis followed by a
prefix of $Y$, and the count of any proper prefix of $X$ is positive, it
follows that the count of any prefix of $Y$ is nonegative.

Let $k$ be the number of positive length prefixes of $Y$ with count zero.
Let $Y_1, Y_1Y_2, \dots, Y_1Y_2\dots Y_{k}$ be these prefixes.  Now for
$i<k$ we have,
\[0 = \mbox{count}(Y_1\dots Y_{i+1}) = \mbox{count}(Y_1\dots Y_{i}) +
\mbox{count}(Y_{i+1}) = 0 + \mbox{count}(Y_{i+1}) = \mbox{count}(Y_{i+1}).\]

Note that $Y_1Y_2\dots Y_{k} = Y$ since $Y$ is a prefix of itself and
$\mbox{count}(Y)= 0$.  Let $V$ be a proper prefix of $Y_{i+1}$.  Then
$Y_1\dots Y_iV$ is a prefix of $Y$ and so has nonegative count.  In fact,
it must have positive count, since the shortest prefix longer than
$Y_1\dots Y_i$ with count zero is $Y_1\dots Y_{i+1}$ by definition.  So
\[0 < \mbox{count}(Y_1\dots Y_{i}V) = \mbox{count}(Y_1\dots Y_{i}) +
\mbox{count}(V) = 0+\mbox{count}(V) = \mbox{count}(V).\]

Thus, we have shown that the string $Y_{i+1}$ is a WCP for $0\leq i <k$.
By inductive hypothesis, every $Y_{i+1}$ is also a WMP.  Hence $Y=Y_1\dots
Y_k$ is a sequence of WMP's, and therefore $X=\Code{(}Y\Code{)}$ is WMP by
definition. \qed

\fi


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

Note that there are 24 people (12 couples) in this case.

We will prove the following for a set of $n$ couples:
\begin{theorem}
Suppose at a party for $n$ couples (total) it turns out that
someone other than me has shaken $k$ hands for every $k$ from $0$ to $2n-2$. 
Then I must have shaken $n-1$ hands.
\end{theorem}

{\em Proof.}
By induction on $n$.

I.H. $P(n)$ : At an $n$ couple party, if someone other than me shakes $k$ 
hands 
for every $k$ from $0$ to $2n-2$ then I must have shaken $n-1$ hands.

Base: $n=1$. There are no other couples. My wife has shaken $0$ hands
(can't shake with me). I have shaken $0$ hands ($=n-1$). (some party!)

I.H. Assume $P(n-1)$ is true. To prove $P(n)$, 
consider a party with $n$ couples. 

Someone has shaken $2n-2$ hands, i.e., with everyone in the room
except themselves and their spouse. Therefore everyone else but this
couple has shaken hands at least once. So the one who hasn't shaken hands
at all must be this person's spouse. $2n-2$ is paired with $0$. 
Consider the subparty of the remaining $n-1$ couples. I must be in this
group since there cannot be two people who shook hands $2n-2$ times or $0$
times. Consider the
number of times this group of people has shaken hands among themselves,
i.e., not counting handshakes with the $2n-2, 0$ couple. Then the 
number of handshakes I see is every number between $0$ and $2n-4$. This 
is because this group of people has original handshake counts of $1,2,3,\ldots,
2n-3$. Since everyone shakes the $2n-2$
person's hand once, we are left with handshake counts of $0,1,\ldots,2n-4$. 
This
is exactly the premise of $P(n-1)$. So by the I.H. I must have shaken
$n-2$ hands within this group. Adding the one handshake with
the $2n-2, 0$ couple, I must have shaken a total of $n-1$ hands.
\qed

For $n=12$, the answer is that I shook 11 hands.
 
\item {\em Geometric mean vs Arithmetic mean. }  Show that for any 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}

By strong induction on n.

          Notation: $ AM(x_1\ldots x_n) = \frac{x_1+..+x_n}{n}$
   
   Ind. Hyp.   $(x_1x_2\ldots x_n) \leq  (AM(x_1,..,x_n) )^n$               
   
   Base case. $n=1$:  $x_1 \leq x_1$.

   $ n=2$:    $4x_1x_2  \leq (x_1+x_2)^2$

           or  $0 \leq (x_1-x_2)^2$   which is true.


   Ind step. Assume $P(1) \wedge P(2) \wedge \ldots \wedge P(n-1)$ is true
to prove $P(n)$.We will prove $P(n)$ separately for odd values of $n$ and 
even values of $n$.

 \begin{enumerate}        
    \item $n$ is even.

         Then,
\[ (x_1x_2\ldots x_n) = (x_1x_2\ldots x_{n/2})(x_{n/2 +1}x_{n/2+2}\ldots x_{n}) \]
\[ \leq  AM(x_1..x_{n/2})^{\frac{n}{2}} AM(x_{n/2 +1}..x_{n})^{\frac{n}{2}} \]
Using $P(\frac{n}{2})$,
\[  \leq  [AM(x_1 ..x_{n/2}) AM(x_{n/2 +1}..x_{n})]^{\frac{n}{2}} \]
\[ \leq [(AM(x_1 ..x_{n/2})+ AM(x_{n/2 +1}..x_{n}))/2]^n \]
(from $P(2)$) 
 \[ \leq [AM(x_1 ..x_{n})]^n \]

       
    \item  $n$ is odd.  Then we show that 

          \[ P(\frac{n+1}{2}) \rightarrow P(n+1) \rightarrow P(n). \]
    
         Assume $n \geq 2$. Then $\frac{n+1}{2} < n$ and hence
we can assume from the I.H. that $P(\frac{n+1}{2})$ is true.
The proof of the first implication is then identical to earlier case.

          To show $P(n+1) \rightarrow P(n)$,

        Start with P(n+1).  
Let $x_{n+1} = {x_1 + x_2 +\ldots + x_n \over n}$. This implies 
$x_{n+1} = {x_1+\ldots +x_{n+1} \over n+1}$. Which means that
$AM(x_1,\ldots,x_n) = AM(x_1,\ldots,x_{n+1})$ for this choice of $x_{n+1}$.
         
        Then $P(n+1)$ is
         $$x_1x_2\ldots x_nx_{n+1} \leq AM(x_1,\ldots,x_{n+1})^{n+1}$$
Dividing both sides by $x_{n+1}$ we have:
         $$x_1x_2\ldots x_n \leq  AM(x_1, \ldots x_{n+1})^n$$
                  $$= AM(x_1, \ldots x_n)^n$$


\end{enumerate}

\end{document}


