\documentstyle[11pt]{article}

\setlength{\oddsidemargin}{-0.1 in}
\setlength{\evensidemargin}{-.3 in}
\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8in}

\setlength{\parskip}{\medskipamount}
\pagestyle{empty}

\input{macros}
	
\begin{document}


\section{Induction and well-ordering}

The principle of induction is basic.
In order to prove that some property holds for all natural numbers, 
one shows that ($i$) the property holds for $1$, and 
($ii$) if, for any natural number $k$, the property holds for $k$, 
then the property holds for $k+1$.
The soundness of induction seems almost self-evident:  the property must
hold for all natural numbers, because every natural number
can be ``reached'' from $1$ by successively adding $1$.

Formally, this principle states 
\begin{quotation}
If $S\subseteq N=\{1,2,3,\ldots\}$ satisfies
\begin{itemize}
\item $1\in S$ 
\item For each $k \in S$, if $k\in S$ then $k+1\in S$
\end{itemize}
\end{quotation}

This seemingly obvious fact can be proved formally from the 
axioms for the natural numbers with addition.
It is the axiom of {\em well-ordering} which is essential:
\begin{quotation}
Every set nonempty $X\subseteq N$ has a least element.
That is, there is an element $x\in X$ such that $x\leq y$ for all $y\in X$.
\end{quotation}

In fact, the axiom of well-ordering is equivalent to induction, 
in the sense that either one can be proved from the other
using only the remaining axioms of the natural numbers with addition.
It is easy to prove induction from the axiom of well-ordering:
given the two conditions on $S$, 
there cannot be any number in $N$ that is not in $S$,
for then there would have to be a least such element $x$ 
in the set $\{ n: n\in N, n\not\in S\}$ (by well-ordering) 
which is impossible since then $x-1\in S$
but the second condition of induction requires that therefore $(x-1)+1=x\in S$.
Conversely, if induction is taken as an axiom, 
it follows that well-ordering must hold:
%	we perform induction on 
If $1\in X$ then $1$ is the least element.
Now suppose $k\in S$.
If $k$ is the least element of $X$, then we are done.
Otherwise, consider the set $X\cup \{ k-1\}$.  
It has a least element $x$, by induction.
If $x\in X$, then $x$ is also the least element of $X$;
if $x \not\in X$, then $x=k-1$ and none of $1,2,\ldots, k-2$ is in $X$, 
so $k$ is the least element of $X$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The pigeonhole principle}

[[[Define injection, (surjection?), bijection first?  ``$|A|$''?]]]

The pigeonhole principle is so obvious that you may 
have used it without having heard of it before.
It simply says
\begin{quotation}
For any two finite nonempty sets $A$ and $B$ such that $|A|>|B|$, 
any mapping $f$ from $A$ to $B$ must map two elements to the same place:
$f(a)=f(a')$ for some $a$ and $a'$.
\end{quotation}

[[[Is this really worth proving?]]]

For example, in any set of $367$ people, two must have the same birthday;
any map from people to birthdays must give two people the same day.
A more interesting example is to prove that 
in any set of people, there must be two who have the same number of 
friends (not counting one's self)
within the set (assuming that all friendships are reciprocated).
Say there are $n$ people in the set. 
Each person may have anywhere from $0$ to $n-1$ friends---
$n$ possibilities, potentially one for each person.
However, there cannot be both someone with $n-1$ friends and someone
with $0$ friends because either those two are friends or not.
Thus, there are only $n-1$ values that are simultaneously possible
and therefore two of the $n$ people must have the same number of friends.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Symmetry}

The symmetry of a structure is often useful for completing 
the argument of a proof.
For example, imagine a game played on a perfectly round table
where two players take turns placing coins of the same size on the table.
The loser is the first one who is unable to place a coin directly on 
the table. 
We would like to show that the player who goes first has a winning strategy.
The strategy is for that player to place the first coin of the game 
in the very center of the table.
From now on, no matter where the other places a coin, 
the first player may place a coin directly opposite his:
if there was space on one side of the table, there is space on the
other side, because a certain symmetry is maintained.

[[[Figure?]]]

[[[Another example: proving that the alternating sum of the 
binomial coefficients is 0 because you're basically subtracting the
number of odd subset from the number of even subset, and they're the same.]]]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proof by contradiction}

A proof by contradiction proceeds by assuming that the conclusion 
of the theorem is not true and showing that implies a contradiction---%
that two contradictory statements must be true simultaneously.
The contradiction may be that a well-known fact is implied false,
or that something assumed in the theorem is implied false,
or that two contradictory statements are both implied by supposing the
theorem false.
This often takes the form of proving the contrapositive of the
statement of the statement of the theorem:
Suppose we wish to prove
\thm  If $A$ then $B$.  
\ethm
We may prove this by contradiction by proving ``If not $B$ then not $A$.'':

\pf
By contradiction.
Assume $B$ is false.  
Then it must be that \ldots 
and therefore $A$ is false.  
But this is a contradiction to the hypothesis of the theorem.
\epf

Proof by contradiction
It is sometimes convenient, though rarely necessary.
An example in which it seems indispensable is proving that there
are an infinite number of primes:
\thm
There are an infinite number of primes.
\ethm
\pf
By contradiction: suppose not---suppose the primes constitute
a finite set $P=\{ p_1, p_2, \ldots, p_n\}$.
%	and let $P$ be indexed in increasing order, so $p_i<p_j$ for $i<j$.
The number $p=p_1\times p_2\times \cdots \times p_n + 1$
is not divisible by any element of $P$ since a remainder of $1$ is left.
But $p$ has a unique factorization into primes, none of which is in $P$, 
so $P$ does not contain all primes.
\epf

Proofs by contradiction are sometimes deceptive; 
under the assumption that a true statement (the theorem, which in fact is true)
is false, arbitrary false ``lemmas'' may be proved along the 
way to reaching the final contradiction.
This may obscure the truth!
[[[Example?]]]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Invariants}

\section{Notation}

\section{Permutations}

\section{Recurrences}

\section{Quantifiers}

The usual quantifiers are $\forall$, ``for all'', and $\exists$, ``exists'';
both are meaningful only in the context of a given set.
Their meaning is apparent:  $\forall x \phi(x)$ means that $\phi(x)$ 
is true for every element $x$ of the set; 
$\exists x \phi(x)$ means that $\phi(x)$ is true for at least one element
$x$ of the set.

When more than one quantifier is used in a single statement, 
the order in which they appear is extremely important.
You should be comfortable with the meaning of the order of quantifiers.
For example,
look again at the statement of the axiom of well-ordering:
it says that for every nonempty set $X\subseteq N$, there is a least
element $x$.
In the notation of quantifiers, 
$\forall X \exists x \phi (x)$, where $\phi (x)$ is true if $x$ is less
than every other element of $X$.
(Here, the capital $X$ is understood to vary over the set of subsets of $N$
and the lowercase $x$ over the elements of $N$.)
In order to prove this statement, for each set $X$, 
we may choose a different element $x$.
Exchanging the order of the quantifiers produces a statement
which is very different:  $\exists x \forall X \phi (x)$, 
there is an element $x\in N$ such that for every set $X\subseteq N$, 
$x$ is less than every element of $X$. 
This says that the same element $x$ must work for every set $X$,
and a much stronger statement.

In general, consider a statement like 
$\forall x_1 \exists x_2 \forall x_3 \exists x_4 \cdots \exists x_n 
\phi(x_1, x_2, \ldots, x_n)$.
Assuming that the only variables of $\phi$ are $x_1, \ldots, x_n$, 
this statement is either true or false.
The content of the statement may be viewed as a game between two players, 
the Exists player and the Forall player.
In order for the entire quantified statement to be true, 
it must be the case that no matter what the Forall player picks for $x_1$,
the Exists player can find a choice of $x_2$ such that no matter what
the Forall player chooses for $x_3$, and so on, the Exists player
can choose a value for $x_n$ so that the predicate $\phi$ is true
on those values.
So the game is that the player take turns choosing values for the $x_i$,
depending on the quantifiers.  
The goal of the Forall player is to make $\phi$ false when it is 
instantiated with the chosen values;
the goal of the Exists player is to make $\phi$ true.
The quantified statement is true if and only if the Exists player 
has a winning strategy.

\section{DeMorgan's Law}

\section{Inclusion/Exclusion}

Suppose we wish to determine the size of the union $A\cup B$ of
two finite sets $A$ and $B$.
It is not hard to see that this is equal to the size of $A$ plus
the size of $B$ minus the size of their intersection:
\[
|A\cup B| = |A| + |B| - |A\cap B|.
\]
By extension, we also see that the size of the union of three sets 
may be expressed as 
\[
|A\cup B\cup C| = \left( |A| + |B| + |C|\right) 
		- \left( |A\cap B| + |A\cap C| + |B\cap C|\right)
		+ |A\cap B\cap C|.
\]
This is verified by seeing that an element that occurs in only one 
set, say $A$, is counted exactly once (in $|A|$ only);
an element that occurs in two sets, say $A$ and $B$, is counted 
a total of once---once in $|A|$, once in $|B|$, and subtracted once 
in $|A\cap B|$; and an element that occurs in all three sets is 
counted once in each of $|A|$, $|B|$, and $|C|$, subtracted once in 
each of $|A\cap B|$, $|A\cap C|$, and $|B\cap C|$, and finally added back
in $|A\cap B\cap C|$, for a total of once.

The generalization of this idea is called the principle
of {\em inclusion/exclusion} (or the {\em sieve} principle):
\thm
\begin{eqnarray*}
|A_1 \cup A_2 \cup \cdots A_n| & = &
|A_1| + |A_2| + \cdots + |A_n| \\
& & - \; (|A_1\cap A_2| + |A_1\cap A_3| + \cdots + |A_{n-1}\cap A_n|) \\
& & + \; (|A_1\cap A_2\cap A_3| + |A_1\cap A_2\cap A_4| + \cdots + 
	|A_{n-2}\cap A_{n-1}\cap A_n|) \\
& & \vdots \\
& & + (-1)^{n-1} |A_1\cap A_2\cap \cdots A_n| \\
& =  & \sum_i |A_i| - \sum_{i<j} |A_i\cap A_j| 
	+ \sum_{i<j<k} |A_i\cap A_j\cap A_k| + \cdots
	+ (-1)^{n-1} |A_1\cap A_2\cap \cdots A_n|.
\end{eqnarray*}
\ethm

\section{Generating Functions}

\section{Basic sums and identities}

\section{Counting two ways}











\end{document}
