# 1.3: Binomial Coefficients

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

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}$.

$\square$

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.

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:

Theorem 1.3.3

\ds {n\choose i}={n\choose n-i}$.

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

$\square$

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.

Theorem 1.3.4

For $1\le i\le \lfloor{n\over 2}\rfloor$, $\ds {n\choose i}>{n\choose i-1}$.

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$, 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 $i\ge \lfloor{n-1\over 2}\rfloor+1$. These are left as an exercise.

$\square$