\documentclass[twoside,12pt]{article}

\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\topmargin}{0 in}
\setlength{\headheight}{0.25 in}
\setlength{\headsep}{0.25 in}
\setlength{\evensidemargin}{0 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\parskip}{1ex}

\newcommand{\heading}[1]{\vspace{3ex} {\Large {\em #1}}}
\newcommand{\subheading}[1]{\vspace{3ex} {\large {\em #1}}}

\usepackage{graphics}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}

\newenvironment{comment}[1]{}{}
\newenvironment{proof}{\noindent {\em Proof.}}{$\Box$}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{fact}{Fact}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\pr}[1]{\Pr\left\{#1\right\}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }

\begin{document}

\begin{center}
{\Large Notes for Tutorial 10} \\
6.042 - April 25 and April 29, 2003 \\
\bigskip
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

There are three topics.

\begin{itemize}

\item Counting practice.

\item Bounding a sum using integration.

\item Binomial theorem and consequences.

\end{itemize}

\noindent In addition, try to weasel in the idea of combinatorial
proof somewhere.  There are no problems on this in the current
homework, but there probably will be on the next.  There are
opportunities in both the counting practice and just before the proof
of the binomial theorem.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Counting Practice}

I have $f$ fiction books, $n$ nonfiction books.  All are different.
Assume $f, n \geq 5$.  Ask these questions verbally or write them on
the board.  Have students answer aloud and explain their reasoning.

\begin{itemize}

\item In how many ways can I arrange these books on a shelf?

\[
(f + n)!
\]

\item In how many ways can I arrange these books on a shelf if I keep
the fiction books together and the nonfiction books together?

Either fiction comes first or nonfiction does, so we have:

\[
2 \cdot f! \cdot n!
\]

\item I want to bring 3 fiction books and 2 nonfiction books on a
trip.  In how many different ways can I choose which books to bring?

\[
\binom{f}{3} \binom{n}{2}
\]

\item In May, I plan to read 3 different fiction books followed by 2
different nonfiction books.  In how many different ways can I do this?
(Here, assume that order matters; that is, reading book $A$ and then
book $B$ is one possibility, but reading $B$ and then $A$ is
considered a different possibility.)

\[
f (f-1) (f-2) n (n-1)
\]

\item My friend plans to read 5 of my books, 3 of them fiction and 2
of them nonfiction.  In how many different ways can she do this?
(Again, assume that order matters.)

We could select the books and then order them:

\[
\binom{f}{3} \binom{n}{2} \cdot 5!
\]

Or we could order the fiction books and order the nonfiction books,
and then pick 3 of the 5 ``reading slots'' to fill with fiction books:

\[
f(f-1)(f-2) n (n-1) \cdot \binom{5}{3}
\]

These expressions must be equivalent!  It is easy to check that they
are.

\item On another trip, I plan to bring a total of $k$ books, of which
$i$ are fiction and $k - i$ are nonfiction.  In how many different
ways can I do this?  (Order does not matter; assume $k < f$ and $k <
n$.)

\[
\binom{f}{i} \binom{n}{k-i}
\]

\item On my trip, I plan to bring a total of $k$ books.  In how many
different ways can I do this?  (Again, order does not matter.)

The obvious answer is:

\[
\binom{f + n}{k}
\]

An alternative is to note that we must read $i$ fiction books for some
$i$ in the range $0 \leq i \leq k$ and use the preceding answer:

\[
\sum_{i=0}^k \binom{f}{i} \binom{n}{k-i}
\]

Since we've counted the same thing in two different ways, it must be
that:

\beqn
\binom{f + n}{k}
	& = & \sum_{i=0}^k \binom{f}{i} \binom{n}{k-i}
\eeqn

We've proved that this equation holds by {\em counting the same thing
in two different ways}.  This is called a {\em combinatorial proof}.

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Approximating a Sum via Integration}

One of the functions that we'll use the most for the remainder of the
term is factorial.  In lecture, we saw how to upper and lower bound a
sum using integration.  It would be nice to get similar bounds on
$n!$.  Unfortunately, this is a product:

\beqn
n! & = & n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1
\eeqn

If there were a way to make this product into a sum, we could get
upper and lower bounds by integration.  How could we could this?  Take
the logaritm of both sides:

\beqn
\ln n! & = & \ln(n) + \ln(n-1) + \ln(n-2) + \cdots + \ln(3) + \ln(2) + \ln(1)
\eeqn

Ask students to compute upper and lower bounds on $n!$ using the
integral method.  Encourage them to draw a picture, since this really
helps get the bounding functions and integration ranges right.  You
might provide them with the following integration formula:

\beqn
\int \ln x\ dx & = & x \ln x - x
\eeqn

\noindent There are many ways to set up the integrals and handle the
boundaries.  Here is one way.

\beqn
\sum_{k=1}^n \ln k
	& < &	\int_0^n \ln(x+1)\ dx \\
	& = &	\left.(x+1) \ln(x + 1) - (x+1) \right|_0^n \\
	& = &	(n+1) \ln(n+1) - n
\eeqn

\beqn
\sum_{k=1}^n \ln k
	& > &	\int_1^n \ln x\ dx \\
	& = &	\left. x \ln x - x \right|_1^n \\
	& = &	n \ln n - n + 1
\eeqn

\noindent Now exponentiating gives the bounds:

\[
\frac{n^n}{e^{n-1}} \ <\ n!\ <\ \frac{(n+1)^{n+1}}{e^n}
\]

This shows that $n!$ is right around $(n/e)^n$.  With a bit more work,
one can obtain the following approximation, which is worth
remembering:

\beqn
n! & \approx & \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n
\eeqn

\noindent This looks a lot worse than $n!$, but is actually much
easier to work with in practice.

For example, what is the probability that we flip {\em exactly} a
thousand heads when we flip a fair coin two thousand times?  The exact
answer is:

\beqn
\frac{1}{2^{2000}} \cdot \binom{2000}{1000}
	& = & \frac{1}{2^{2000}} \cdot \frac{2000!}{(1000!)^2}
\eeqn

\noindent Good luck computing two thousand factorial.  Letting $n =
1000$ and using Stirling's formula gives:

\beqn
\frac{1}{2^{2n}} \cdot \binom{2n}{n}
	& = &	\frac{1}{2^{2n}} \cdot \frac{(2n)!}{(n!)^2} \\
	& = &	\frac{1}{2^{2n}} \cdot 
		\frac{\sqrt{2 \pi (2n)} \left(\frac{2n}{e}\right)^{2n}}
		{\left(\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n\right)^2} \\
	& = &	\frac{1}{\sqrt{\pi n}}
\eeqn

\noindent Everything cancels!  We can evaluate this last expression
with a calculator.  The probability is $0.0178\ldots$, or about
$1.8\%$.  Thus, even though the coin is fair, it is extremely {\em
unlikely} that you get half heads and half tails!

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Binomial Theorem}

Here's a neat combinatorial fact:

\begin{fact}
\beqn
\binom{n}{k} & = & \binom{n-1}{k} + \binom{n-1}{k-1}
\eeqn
\end{fact}

We {\em can} prove this algebraically by subtituting in the
definitions of the binomial coefficients and working out all the
factorials.  (You should probably not work through this, but here's
the argument if you must.)

\beqn
\binom{n-1}{k} + \binom{n-1}{k-1}
	& = &	\frac{(n-1)!}{k!\ (n-k-1)!} +
		\frac{(n-1)!}{(k-1)!\ (n-k)!} \\
	& = &	\left( \frac{1}{k} + \frac{1}{n-k} \right) \cdot
		\frac{(n-1)!}{(k-1)!\ (n-k-1)!} \\
	& = &	\frac{n}{k(n-k)} \cdot 
		\frac{(n-1)!}{(k-1)!\ (n-k-1)!} \\
	& = &	\frac{n!}{k!\ (n-k)!} \\
	& = &	\binom{n}{k}
\eeqn

There is an easy way to see that this equation holds.  How many ways
are there to choose $k$ objects from a set of $n$ objects?

\[
\binom{n}{k}
\]

\noindent But there's another way to answer that question.  Pick one
of the $n$ objects and call it $x$.  Now when we choose $k$ objects
from the set of $n$, we either pick $x$ or we don't.  If we do pick
$x$, how many ways are there to choose the remaining $k-1$ objects?

\[
\binom{n-1}{k-1}
\]

\noindent If we don't pick $x$, then how many ways are there to choose
the $k$ objects?

\[
\binom{n-1}{k}
\]

\noindent Therefore, we have:

\beqn
\binom{n}{k} & = & \binom{n-1}{k} + \binom{n-1}{k-1}
\eeqn

\noindent This is called a {\em combinatorial proof}.  The basic idea
is to {\em count the same thing in two different ways}.  This gives
two expressions that must be equal.  Here we've counted the number of
ways to pick $k$ objects from a set of $n$ in two different ways and
gotten a neat equation--- without using any algebra!  We'll see more
of this later on.

We can use our equation and induction to prove one of the most
important theorems of all time!  In fact, this is where binomial
coefficients get their name.  (Make this an exercise.)

\begin{theorem}[Binomial Theorem]
For all $n \in \mathbb{N}$ and $x, y \in \mathbb{R}$:

\beqn
(x + y)^n & = & \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}
\eeqn
\end{theorem}

\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that:

\beqn
(x + y)^n & = & \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}
\eeqn

\noindent for all $x, y \in \mathbb{R}$.  Note that $P(0)$ is true,
because $(x + y)^0 = 1$ and:

\beqn
\sum_{k=0}^0 \binom{n}{k} x^k y^{n-k}
	& = &	\binom{0}{0} x^0 y^0 \\
	& = &	1
\eeqn

Now we must show that for $n \geq 1$, $P(n-1)$ implies $P(n)$.  To
that end, we assume $P(n-1)$ and reason as follows:

\beqn
(x + y)^n
	& = &	(x+y) \cdot (x + y)^{n-1} \\
	& = &	(x+y) \cdot \sum_{k=0}^{n-1} \binom{n-1}{k} x^k y^{n-1-k} \\
	& = &	x \sum_{k=0}^{n-1} \binom{n-1}{k} x^k y^{n-1-k} +
		y \sum_{k=0}^{n-1} \binom{n-1}{k} x^k y^{n-1-k} \\
	& = &	\sum_{k=0}^{n-1} \binom{n-1}{k} x^{k+1} y^{n-1-k} +
		\sum_{k=0}^{n-1} \binom{n-1}{k} x^k y^{n-k} \\
	& = &	\sum_{k=1}^{n} \binom{n-1}{k-1} x^k y^{n-k} +
		\sum_{k=0}^{n-1} \binom{n-1}{k} x^k y^{n-k} \\
	& = &	\sum_{k=0}^n \binom{n}{k} x^k y^{n-k}
\eeqn

\noindent The first step uses algebra.  The second uses the induction
hypothesis.  In the third step, we use the distributive law.  Next, we
move $x$ and $y$ into the summations.  In the fifth step, we reindex
the first summation.  The final step uses the identity derived above
and the relations:

\beqn
\binom{n-1}{n-1}	& = & \binom{n}{n} \\
\binom{n-1}{0}		& = & \binom{n}{0}
\eeqn

\noindent Thus, the claim is proved by induction.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
