Recall the appearance of Pascal's Triangle in example 1.2.6. If you have encountered the triangle before, you may know it has many interesting properties. We will explore some of these here.
You may know, for example, that the entries in Pascal's Triangle are the coefficients of the polynomial produced by raising a binomial to an integer power. For example, $\ds (x+y)^3=1\cdot x^3+3\cdot x^2y+ 3\cdot xy^2+1\cdot y^3$, and the coefficients 1, 3, 3, 1 form row three of Pascal's Triangle. For this reason the numbers $n\choose k$ are usually referred to as the binomial coefficients.
Theorem 1.3.1 (Binomial Theorem) $$ (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}y^n= \sum_{i=0}^n {n\choose i}x^{n-i}y^i$$
Proof. We prove this by induction on $n$. It is easy to check the first few, say for $n=0,1,2$, which form the base case. Now suppose the theorem is true for $n-1$, that is, $$(x+y)^{n-1} =\sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^i.$$ Then $$(x+y)^n=(x+y)(x+y)^{n-1}=(x+y)\sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^i.$$ Using the distributive property, this becomes $$\eqalign{ x\sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^i+ y&\sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^i\cr &=\sum_{i=0}^{n-1}{n-1\choose i}x^{n-i}y^i+ \sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^{i+1}.\cr} $$ These two sums have much in common, but it is slightly disguised by an "offset'': the first sum starts with an $x^ny^0$ term and ends with an $x^{1}y^{n-1}$ term, while the corresponding terms in the second sum are $x^{n-1}y^{1}$ and $x^{0}y^{n}$. Let's rewrite the second sum so that they match: $$\eqalign{ \sum_{i=0}^{n-1}{n-1\choose i}&x^{n-i}y^i+ \sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^{i+1}\cr &=\sum_{i=0}^{n-1}{n-1\choose i}x^{n-i}y^i+ \sum_{i=1}^{n} {n-1\choose i-1}x^{n-i}y^{i}\cr &={n-1\choose 0}x^n+\sum_{i=1}^{n-1}{n-1\choose i}x^{n-i}y^i+ \sum_{i=1}^{n-1} {n-1\choose i-1}x^{n-i}y^{i}+{n-1\choose n-1}y^{n}\cr &={n-1\choose 0}x^n+ \sum_{i=1}^{n-1}({n-1\choose i}+{n-1\choose i-1})x^{n-i}y^{i}+ {n-1\choose n-1}y^{n}.\cr }$$ Now we can use theorem 1.2.7 to get: $$\eqalign{ {n-1\choose 0}x^n+ &\sum_{i=1}^{n-1}({n-1\choose i}+{n-1\choose i-1})x^{n-i}y^{i}+ {n-1\choose n-1}y^{n}.\cr &={n-1\choose 0}x^n+ \sum_{i=1}^{n-1}{n\choose i}x^{n-i}y^{i}+ {n-1\choose n-1}y^{n}.\cr &={n\choose 0}x^n+ \sum_{i=1}^{n-1}{n\choose i}x^{n-i}y^{i}+ {n\choose n}y^{n}\cr &=\sum_{i=0}^{n}{n\choose i}x^{n-i}y^{i}.\cr }$$ At the next to last step we used the facts that ${n-1\choose 0}={n\choose 0}$ and ${n-1\choose n-1}={n\choose n}$. $\qed$
Here is an interesting consequence of this theorem: Consider $$(x+y)^n=(x+y)(x+y)\cdots(x+y).$$ One way we might think of attempting to multiply this out is this: Go through the $n$ factors $(x+y)$ and in each factor choose either the $x$ or the $y$; at the end, multiply your choices together, getting some term like $xxyxyy\cdots yx= x^iy^j$, where of course $i+j=n$. If we do this in all possible ways and then collect like terms, we will clearly get $$\sum_{i=0}^n a_ix^{n-i}y^i.$$ We know that the correct expansion has ${n\choose i}=a_i$; is that in fact what we will get by this method? Yes: consider $x^{n-i}y^i$. How many times will we get this term using the given method? It will be the number of times we end up with $i$ $y$-factors. Since there are $n$ factors $(x+y)$, the number of times we get $i$ $y$-factors must be the number of ways to pick $i$ of the $(x+y)$ factors to contribute a $y$, namely $n\choose i$. This is probably not a useful method in practice, but it is interesting and occasionally useful.
Example 1.3.2 Using this method we might get $$(x+y)^3 = xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy$$ which indeed becomes $\ds x^3+3x^2y+3xy^2 + y^3$ upon collecting like terms. $\square$
The Binomial Theorem, 1.3.1, can be used to derive many interesting identities. A common way to rewrite it is to substitute $y=1$ to get $$(x+1)^n=\sum_{i=0}^n {n\choose i} x^{n-i}.$$ If we then substitute $x=1$ we get $$2^n=\sum_{i=0}^n{n\choose i},$$ that is, row $n$ of Pascal's Triangle sums to $2^n$. This is also easy to understand combinatorially: the sum represents the total number of subsets of an $n$-set, since it adds together the numbers of subsets of every possible size. It is easy to see directly that the number of subsets of an $n$-set is $2^n$: for each element of the set we make a choice, to include or to exclude the element. The total number of ways to make these choices is $2\cdot2\cdots2=2^n$, by the multiplication principle.
Suppose now that $n\ge 1$ and we substitute $-1$ for $x$; we get $$\eqalignno{ (-1+1)^n&=\sum_{i=0}^n{n\choose i}(-1)^{n-i}.& (1.3.1)\cr }$$ The sum is now an alternating sum: every other term is multiplied by $-1$. Since the left hand side is $0$, we can rewrite this to get $$\eqalignno{ {n\choose 0}+{n\choose 2}+\cdots&={n\choose 1}+{n\choose 3}+\cdots.& (1.3.2)\cr }$$ So each of these sums is $2^{n-1}$.
Another obvious feature of Pascal's Triangle is symmetry: each row reads the same forwards and backwards. That is, we have:
Proof. This is quite easy to see combinatorially: every $i$-subset of an $n$-set is associated with an $(n-i)$-subset. That is, if the $n$-set is $A$, and if $B\subseteq A$ has size $i$, then the complement of $B$ has size $n-i$. This establishes a 1–1 correspondence between sets of size $i$ and sets of size $n-i$, so the numbers of each are the same. (Of course, if $i=n-i$, no proof is required.) $\qed$
Note that this means that the Binomial Theorem, 1.3.1, can also be written as $$(x+y)^n=\sum_{i=0}^n {n\choose n-i}x^{n-i}y^{i}.$$ or $$(x+y)^n=\sum_{i=0}^n {n\choose i}x^{i}y^{n-i}.$$
Another striking feature of Pascal's Triangle is that the entries across a row are strictly increasing to the middle of the row, and then strictly decreasing. Since we already know that the rows are symmetric, the first part of this implies the second.
Proof. This is by induction; the base case is apparent from the first few rows. Write $$\eqalign{ {n\choose i}&={n-1\choose i-1}+{n-1\choose i}\cr {n\choose i-1}&={n-1\choose i-2}+{n-1\choose i-1}\cr }$$ Provided that $1\le i\le \lfloor{n-1\over 2}\rfloor$, we know by the induction hypothesis that $${n-1\choose i}>{n-1\choose i-1}.$$ Provided that $1\le i-1\le \lfloor{n-1\over 2}\rfloor$, or equivalently $2\le i\le \lfloor{n-1\over 2}\rfloor+1$, we know that $${n-1\choose i-1}>{n-1\choose i-2}.$$ Hence if $2\le i\le \lfloor{n-1\over 2}\rfloor$, $${n\choose i}>{n\choose i-1}.$$ This leaves two special cases to check: $i=1$ and for $n$ even, $i=\lfloor{n-1\over 2}\rfloor+1=\lfloor{n\over 2}\rfloor$. These are left as an exercise. $\qed$
Exercises 1.3
Ex 1.3.1 Suppose a street grid starts at position $(0,0)$ and extends up and to the right:
A shortest route along streets from $(0,0)$ to $(i,j)$ is $i+j$ blocks long, going $i$ blocks east and $j$ blocks north. How many such routes are there? Suppose that the block between $(k,l)$ and $(k+1,l)$ is closed, where $k< i$ and $l\le j$. How many shortest routes are there from $(0,0)$ to $(i,j)$?
Ex 1.3.2 Prove by induction that $\sum_{k=0}^n {k\choose i} = {n+1\choose i+1}$ for $n\ge 0$ and $i\ge 0$.
Ex 1.3.3 Use a combinatorial argument to prove that $\sum_{k=0}^n {k\choose i} = {n+1\choose i+1}$ for $n\ge 0$ and $i\ge 0$; that is, explain why the left-hand side counts the same thing as the right-hand side.
Ex 1.3.4 Use a combinatorial argument to prove that ${k \choose 2} + {n-k \choose 2}+k(n-k) = {n \choose 2}$.
Ex 1.3.5 Use a combinatorial argument to prove that ${2n\choose n}$ is even.
Ex 1.3.6 Suppose that $A$ is a non-empty finite set. Prove that $A$ has as many even-sized subsets as it does odd-sized subsets.
Ex 1.3.7 Prove that $\sum_{k=0}^n {k\choose i}k = {n+1\choose i+1}n-{n+1\choose i+2}$ for $n\ge 0$ and $i\ge 0$.
Ex 1.3.8 Verify that ${n+1\choose2}+{n\choose2}=n^2$. Use exercise 2 to find a simple expression for $\sum_{i=1}^n i^2$.
Ex 1.3.9 Make a conjecture about the sums of the upward diagonals in Pascal's Triangle as indicated. Prove your conjecture is true.
Ex 1.3.10 Find the number of ways to write $n$ as an ordered sum of ones and twos, $n\ge 0$. For example, when $n=4$, there are five ways: $1+1+1+1$, $2+1+1$, $1+2+1$, $1+1+2$, and $2+2$.
Ex 1.3.11 Use $(x+1)^n=\sum_{i=0}^n{n\choose i}x^i$ to find a simple expression for $\sum_{i=1}^n i{n\choose i}x^{i-1}$. Then find a simple expression for $\sum_{i=1}^n i {n\choose i}$.
Ex 1.3.12 Use $(x+1)^n=\sum_{i=0}^n{n\choose i}x^i$ to find a simple expression for $\sum_{i=0}^n{1\over i+1}{n\choose i}x^{i+1}$. Then find a simple expression for $\sum_{i=0}^n{1\over i+1}{n\choose i}$.
Ex 1.3.13 Use the previous exercise to find a simple expression for $\sum_{i=0}^n(-1)^i{1\over i+1}{n\choose i}$.
Ex 1.3.14 Give a combinatorial proof of $$\sum_{i=0}^k {m\choose i}{n\choose k-i}={m+n\choose k}.$$ Rewrite this identity in simpler form if $m=n$, and when $k=m=n$.
Ex 1.3.15 Finish the proof of theorem 1.3.4.
Ex 1.3.16 Give an alternate proof of theorm 1.3.4 by characterizing those $i$ for which ${n\choose i}/{n\choose i-1} > 1$.
Ex 1.3.17 When is ${n\choose i}/{n\choose i-1}$ a maximum? When is ${n\choose i}/{n\choose i-1}=2$?
Ex 1.3.18 When is ${n\choose i}-{n\choose i-1}$ a maximum?
Ex 1.3.19 A Galton board is an upright flat surface with protruding horizontal pins arranged as shown below. At the bottom are a number of bins; if the number of rows is $n$, the number of bins is $n+1$. A ball is dropped directly above the top pin, and at each pin bounces left or right with equal probability. We assume that the ball next hits the pin below and immediately left or right of the pin it has struck, and this continues down the board, until the ball falls into a bin at the bottom. If we number the bins from 0 to $n$, how many paths can a ball travel to end up in bin $k$?
This may be interpreted in terms of probability, which was the intent of Sir Francis Galton when he designed it. Each path is equally likely to be taken by a ball. If many balls are dropped, the number of balls in bin $k$ corresponds to the probability of ending up in that bin. The more paths that end in a bin, the higher the probability. When a very large number of balls are dropped, the balls will form an approximation to the bell curve familiar from probability and statistics.
There is an animation of the process at https://www.randomservices.org/random/apps/GaltonBoardExperiment.html. There was once a very nice physical implementation at the Pacific Science Center in Seattle.