\documentclass[12pt]{article}
\setlength{\topmargin}{-.7in}     
\setlength{\oddsidemargin}{-.55in}
\setlength{\evensidemargin}{-.55in}
\setlength{\textwidth}{7.5in}
\setlength{\textheight}{9.5in}
\setlength{\parskip}{0.1in}
\usepackage{amsmath, amssymb, latexsym,mdwlist}
\usepackage{hyperref}
\usepackage{amsthm}

\def\Def{{\bf Definition:~}}
\def\Thm{{\bf Theorem:~}}
\def\Lemma{{\bf Lemma:~}}
\def\Proof{{\bf Proof:~}}
\def\Eg{{\bf Example:~}}
\def\Ans{{\bf Answer:~}}
\def\Notation{{\bf Notation:~}}
\def\R{{\mathbb{R}}}
\def\e{{\epsilon}}
\def\notA{{\overline{A}}}

\hypersetup{
  colorlinks, linkcolor=blue
}

\newtheorem*{theorem}{Theorem}



\begin{document}
\begin{flushleft}

\begin{center}
{\LARGE \bf Pascal's Triangle and Binomial Coefficients}\\
Information for the Mathcamp 2017 Qualifying Quiz
\end{center}

\section{Pascal's Triangle}

{\em Pascal's triangle} (named for the mathematician Blaise Pascal, 1623--1662) is an infinite triangular arrangement of numbers, constructed according to the following two rules:
\begin{enumerate*}
\vspace{-.3cm}
\item The first and last entry in each row is 1;
\item Each other entry is the sum of the two entries directly above it.
\end{enumerate*}

Here are the first few rows of Pascal's triangle:

$$
\begin{array}{r c c c c c c c c c c c c c c}
&\qquad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad\\
 \text{\small Row 0}&&&&&&&&1&&&&&&\\
  \\
\text{\small Row 1}&&&&&&& 1 &   & 1 &   &   &   &   & \\
 \\
 \text{\small Row 2}&&&&&& 1 &   & 2 &   & 1 &   &   &   & \\
 \\
  \text{\small Row 3} &&&   &   & 1 &   & 3 &   & 3 &   & 1 &   &   &  \\
\\
 \text{\small Row 4}  &&&   & 1 &   & 4 && 6 &   & 4 &   & 1 &   & \\
\\
 \text{\small Row 5}  &&& 1 &   & 5 &   & 10 &   & 10 &   & 5 &   & 1 &  \\
\\
 \text{\small Row 6}&&1 &   & 6 &   & 15 &   & 20 &   & 15 &   & 6 &   & 1 \\
&&\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
\end{array}
$$

We number the rows of Pascal's triangle starting at $0$. The $n$\textsuperscript{th} row has $n+1$ entries, which we also number starting at $0$. For example, Rule 1 tells us that the $0$\textsuperscript{th} and the $n$\textsuperscript{th} entry of row $n$ are both 1. 

We denote the $k$\textsuperscript{th} entry of the $n$\textsuperscript{th} row of Pascal's triangle by ${n \choose k}$.  For example, referring to the table above, we can see that 
$$
{3 \choose 1} = 3, \quad  {5 \choose 2} = 10, \quad {6 \choose 4} = 15, \quad 
$$

We can now rephrase the two rules for constructing Pascal's triangle as follows: for each $n\geq 0$,
\begin{enumerate}
\item $\displaystyle{{n \choose 0} = 1}$ and  $\displaystyle{{n \choose n} = 1.}$ 
\item If $0<k<n$, then $\displaystyle{{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}.}$
\end{enumerate}

\section{Binomial Coefficients}

And now for something completely different (or so it seems)... What do you get if you multiply out the polynomial $(x+y)^n$? Let's see:
$$
\begin{array}{r c c c c c c c c c c c c c c}
&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad&\quad\\
 (x+y)^0&=&&&&&&&1&&&&&&\\
  \\
 (x+y)^1&=&&&&&& x & +  & y &   &   &   &   & \\
 \\
 (x+y)^2&=&&&&& x^2 & +  & 2xy & +  & y^2 &   &   &   & \\
 \\
 (x+y)^3&=&&   &   & x^3 & +  & 3x^2y &  + & 3xy^2 & + & y^3 &   &   &  \\
\\
 (x+y)^4 &=&&   & x^4 &  + & 4x^3y & + & 6x^2y^2 &  + & 4xy^3 & +  & y^4 &   & \\
\\
 (x+y)^5 &=&& x^5 & +  & 5x^4y &  + & 10x^3y^2 &  + & 10x^2y^3 &  + & 5xy^4 &  + & y^5 &  \\
\\
 %(x+y)^6&=&x^6 & + & 6x^5y &  + & 15x^4y^2 & +  & 20x^3y^3 &  + & 15x^2y^4 & +  & 6xy^5 & +  & y^6 \\
%\\
\end{array}
$$

Compare the coefficients in these polynomials to the numbers in Pascal's triangle, and you will immediately see a pattern:
$$
{n \choose k} = \text{ the coefficient of the monomial $x^{n-k}y^k$ in $(x+y)^n$,}
$$ 
or, in other words, 
$$
(x+y)^n = \sum_{k=0}^n {n\choose k}x^{n-k} y^k
$$

This statement is called the {\em binomial theorem} (because it is about powers of the binomial $x+y$), and the numbers ${n \choose k}$ are called {\em binomial coefficients}. If you're curious, you can find a proof of the binomial theorem \href{https://en.wikipedia.org/wiki/Binomial_theorem#Inductive_proof}{HERE}.

\section{A Pattern in Pascal's Triangle}

One of the reasons Pascal's triangle is interesting to mathematicians is that there are many surprising patterns that appear in its entries. Here is one of the most well-known such patterns.

\begin{theorem}
	The sum of the entries in the $n$\textsuperscript{th} row of Pascal's triangle is $2^n$.
\end{theorem}

We give two proofs of this theorem: one that relies directly on the rules that generate Pascal's triangle, and one that uses the binomial theorem.

\begin{proof}
Our first proof proceeds by induction on $n$: we will check that the theorem is true for $n=0$, and then prove that whenever it holds for $n=m$, it also holds for $n=m+1$.

{\em If you have never seen mathematical induction before, you can find a basic explanation \href{https://www.mathsisfun.com/algebra/mathematical-induction.html}{HERE} or in many other places around the web.}
\begin{itemize}
\item \textbf{\boldmath Base case: $n=0$.} When $n=0$, our theorem says that the sum of the entries in the 0\textsuperscript{th} row of Pascal's triangle is $2^0=1$. This is true, since there's only one entry in the 0\textsuperscript{th} row, and it's equal to ${0 \choose 0} = 1$.

\item \textbf{Inductive step.}
Suppose that our result holds for $n=m$. In other words, we assume that
\[
	{m \choose 0} + {m \choose 1} + {m \choose 2} + \cdots + {m \choose m-1} + {m \choose m} = 2^m.
\]
Now, let's try to prove that the same thing is true for $n=m+1$, where we're dealing with the sum
\[
	S = {m+1 \choose 0} + {m+1 \choose 1} + {m+1 \choose 2} + \cdots + {m+1 \choose m} + {m+1 \choose m+1}.
\]
We know that ${m+1 \choose 0} = 1 = {m \choose 0}$, and ${m+1 \choose m+1} = 1 = {m \choose m}$, by Rule 1. We also know that for any $k$ with $0 < k < m+1$, ${m+1 \choose k} = {m \choose k-1} + {m \choose k}$, by Rule 2. 

Use both of these rules to replace the terms in the sum $S$, which are entries of the $(m+1)$\textsuperscript{th} row of Pascal's triangle, by entries of the $m$\textsuperscript{th} row. We get
\[
	S = {m \choose 0} + \left[{m \choose 0} + {m \choose 1}\right] + \left[{m \choose 1} + {m \choose 2}\right] + \cdots + \left[{m \choose m-1} + {m \choose m}\right] + {m \choose m}.
\]
Now notice that in this sum, every entry ${m \choose k}$ appears exactly twice. So we have
\[
	S = 2 \cdot \left[{m \choose 0} + {m \choose 1} + {m \choose 2} + \cdots + {m \choose m-1} + {m \choose k}\right].
\]
By our assumption, the sum of the entries in the $m$\textsuperscript{th} row of Pascal's triangle is $2^m$, so we have $S = 2 \cdot 2^m = 2^{m+1}$. So the sum of the entries in the $(m+1)$\textsuperscript{th} row also matches the theorem, and our induction is complete. \qedhere
\end{itemize}
\end{proof}

Our second proof is much shorter, because it relies on the power of the binomial theorem. But the induction proof was also worth seeing, because similar ideas apply even when the binomial theorem does not work. In fact, the binomial theorem itself can be proven with a similar argument to our first proof!

\begin{proof}
By the binomial theorem, we have
\[
	(x+y)^n = {n \choose 0}x^n + {n \choose 1}x^{n-1} y + {n \choose 2}x^{n-2} y^2 + \cdots + {n \choose n-1}x y^{n-1} + {n \choose n} y^n.
\]
This is true for any $x$ and $y$, so in particular it's true when $x=y=1$. Making this substitution, we get
\[
	(1+1)^n = {n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n-1} + {n \choose n}.
\]
But $(1+1)^n = 2^n$, so this is exactly the result we wanted.
\end{proof}


\section{More on Binomial Coefficients}

There is a lot more to say about binomial coefficients: they appear absolutely everywhere in mathematics! Most famously, they come up in counting ``combinations" of objects: 
$$
{n \choose k} = \text{ the number of ways to select $k$ out of $n$ objects, when order does not matter}.
$$
For example, if we have four objects $A$, $B$, $C$, $D$, here are all the ways we can select two of them:
$$
AB\qquad AC \qquad AD \qquad BC \qquad BD \qquad CD
$$
There are 6 different possibilities, and indeed ${4 \choose 2} =6$. 

From this combinatorial interpretation, one can derive a formula for the binomial coefficients:
$$
{n \choose k} = \frac{n!}{k!(n-k)!}.
$$

If you are curious, you can find more information about this formula and its connection to Pascal's triangle in many places around the web (such as \href{https://en.wikipedia.org/wiki/Binomial_coefficient}{Wikipedia}). 

However, \underline{\bf you do not need to know any of this to solve Problem \#2 on the Qualifying Quiz.} The information in the first three sections of this handout should suffice.

\bigskip

{\large \em Good luck and have fun!}



\end{flushleft}
\end{document}





 
$$
{n \choose k} = \text{ the number of ways to choose $k$ objects out of a set of $n$ objects}.
$$



