Theorem 5.3.1. The Binomial Theorem.
Let \(x \and y\) be variables and \(n\) a natural number, then
\begin{equation*}
(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^{k}
\end{equation*}
Section 5.3 Combinatorial Proofs
We’re going to begin this section by doing a lot of tedious looking algebra, but then we’ll make a connection to what we’ve been doing. There’s a reason! Later in the section, we will introduce a new method of proof called, “combinatorial proof” in which we’re able to verify mathematical statements by counting!
Subsection Binomial Coefficients
As promised, we begin with some tedious calculations. Let’s start by expanding each of the following binomials:
\begin{equation*}
(x+y)^0 = 1
\end{equation*}
\begin{equation*}
(x+y)^1 = 1x + 1y
\end{equation*}
\begin{equation*}
(x+y)^2 = 1x^2 + 2xy + 1y^2
\end{equation*}
\begin{equation*}
(x+y)^3 = 1x^3 + 3x^2y + 3xy^2 + 1y^3
\end{equation*}
\begin{equation*}
(x+y)^4 = 1x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + 1y^4
\end{equation*}
\begin{equation*}
(x+y)^5 = 1x^5 + 5x^4y + 10x^3 y^2 + 10x^2 y^3 + 5xy^4 + 1y^5
\end{equation*}
...
If we arrange the coefficients of the binomials (binomial coefficients) in a triangle, we can find many really neat patterns. In the West, this is usually called “Pascal’s Triangle” after Blaise Pascal (1600’s), though it was also discussed by the Chinese author Yang Hui (1200’s) and it’s called “Yang Hui’s triangle” in China.
There are lots of patterns hidden away in the triangle! Take a few minutes to look for some. Here are just a few to notice:
- The entries on the left or right side of the triangle are all 1.
- Any entry not on the border is the sum of the two entries above it.
- The triangle is symmetric. In any row, entries on the left side are mirrored on the right side.
- The sum of all entries on a given row is a power of 2.
A connection that Pascal did make in Traité du triangle arithmétique (Treatise on the Arithmetic Triangle) is that the entries in the table are actually combinations! Here’s the triangle again, but written with combinations And rather than going through further linguistic torture, we can now refer to “combinations” as “binomial coefficients”.
Now that we’ve connected the coefficients of the binomial to combinations, we can now write the formal binomial theorem as its often presented:
Take a moment to compare the binomials we expanded in the beginning of the section with the summation in the Binomial Theorem to see how it all fits together.
We can also return to the patterns we saw in the triangle and rewrite them in terms of binomial coefficients.
- The entries on the left or right side of the triangle are all 1. In symbols, we’ll write:\begin{equation*} \binom{n}{0} = \binom{n}{n} = 1 \end{equation*}
- Any entry not on the border is the sum of the two entries above it. In symbols:\begin{equation*} \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \end{equation*}
- The triangle is symmetric. In any row, entries on the left side are mirrored on the right side. In symbols:\begin{equation*} \binom{n}{k} = \binom{n}{n - k} \end{equation*}
- The sum of all entries on a given row is a power of 2. In symbols:\begin{equation*} \binom{n}0 + \binom{n}1 + \binom{n}2 + \dots + \binom{n}{n} = 2^n \end{equation*}
Our goal for the remainder of the section is to give proofs of binomial identities. We’ll start with a very tedious algebraic way to do it and then introduce a new proof technique to deal with the same identity.
Example 5.3.2.
Give an algebraic proof for the binomial identity
\begin{equation*}
{n \choose k} = {n-1\choose k-1} + {n-1 \choose k}.
\end{equation*}
Solution.
Proof.
By the definition of \({n \choose k}\text{,}\) we have
\begin{equation*}
{n-1 \choose k-1} = \frac{(n-1)!}{(n-1-(k-1))!(k-1)!} = \frac{(n-1)!}{(n-k)!(k-1)!}
\end{equation*}
and
\begin{equation*}
{n-1 \choose k} = \frac{(n-1)!}{(n-1-k)!k!}.
\end{equation*}
Thus, starting with the right-hand side of the equation:
\begin{align*}
{n-1 \choose k-1} + {n-1 \choose k} \amp = \frac{(n-1)!}{(n-k)!(k-1)!}+ \frac{(n-1)!}{(n-1-k)!\,k!}\\
\amp = \frac{(n-1)!k}{(n-k)!\,k!} + \frac{(n-1)!(n-k)}{(n-k)!\,k!}\\
\amp = \frac{(n-1)!(k+n-k)}{(n-k)!\,k!}\\
\amp = \frac{n!}{(n-k)!\, k!}\\
\amp = {n \choose k}.
\end{align*}
The second line (where the common denominator is found) works because \(k(k-1)! = k!\) and \((n-k)(n-k-1)! = (n-k)!\text{.}\)
That algebra had some fun manipulations if you’re into that kind of thing, but as 15th century mathematician Gerolamo Cardano said Ars Magna, it “is as refined as it is useless.”
Subsection Combinatorial Proofs
Here we introduce a new method of providing mathematical statements. Our goal is to show that an equality is true by counting each side of the equation differently, but showing that we’ve counted the same objects. In order to do this, we will make the following connection for things that binomial coefficients might represent:
- \(\binom{n}{k}\) is the number of ways to select \(k\) objects from a set of \(n\) objects.
- \(\binom{n}{k}\) is the number subsets of size \(k\) from a set of size \(n\)
- \(\binom{n}{k}\) is the number of bit strings of length \(n\) with exactly \(k\) 1’s
- \(\binom{n}{k}\) is the coefficient of \(x^{n-k}y^k\) in the expansion of \((x+y)^n\)
- \(\dots\) there are many more ways of viewing binomial coefficients.
For a combinatorial proof, we will follow this approach:
- Determine a question that can be answered by the particular equation.
- Answer the question in two different ways
- Because those answers count the same object, we can equate their solutions.
Coming up with the question is often the hardest part.
Example 5.3.3.
Give a combinatarial proof of the identity:
\begin{equation*}
{n \choose k} = {n-1\choose k-1} + {n-1 \choose k}.
\end{equation*}
by viewing the binomial coefficients as counting subsets.
Video / Answer.
Solution.
We begin by asking a question, and answering the question in two ways:
“How many subsets of size \(k\) are there from a set of size \(n\text{?}\)”
Answer one: There are \(\binom{n}{k}\) such subsets.
Answer two: Pick any element of the set. That element is either included in a subset, or it is not.
- How many subsets contain this element? We will be picking from the remaining \(n-1\) elements. Since we want the subsets to have \(k\) elements, but we already have one of them, we have a total of \(\binom{n-1}{k-1}\) such subsets.
- How many subsets do not contain this element? We will be picking from the remaining \(n-1\) elements. Since we want the subsets to have \(k\) elements, we have \(\binom{n-1}{k}\) such subsets.
Thus there are \(\binom{n-1}{k-1} + \binom{n-1}{k}\) subsets of \(k\) elements from a set of \(n\) elements.
Because each answer counted the same objects, but in two different ways, those answers much be the same. Thus
\begin{equation*}
{n \choose k} = {n-1\choose k-1} + {n-1 \choose k}.
\end{equation*}
Some people find combinatorial proofs “more fun” because they tell a story. In this next example, if we used a formula, we’d write
\begin{equation*}
\binom{n}{0}=\frac{n!}{0!(n-0)!} = 1\text{.}
\end{equation*}
Fine. But we could also see that this could actually be talking about cookies!
Example 5.3.4.
Give a combinatorial proof of \(\displaystyle \binom{n}0 = 1\text{.}\)
Hint.
Solution.
How about we ask how many ways can we take no cookies from a bag of \(n\) cookies?
Question: How many ways can we take no cookies from a bag of \(n\) cookies?
- Answer: This is \(\binom{n}{0}\text{,}\) since that’s what binomial coefficients count.
- Answer: There is exactly one way to do this. We just don’t get a cookie.
Because each answer answers the same question, we have shown that \(\binom{n}{0} = 1\text{.}\)
Example 5.3.5.
Give a combinatorial proof of \(\displaystyle \binom{n}{k} = \binom{n}{n-k}\)
Hint.
Solution.
Sticking with the cookie scenario, how many ways to pick \(k\) cookies from \(n\) cookies?
Question: How many ways can we take \(k\) cookies from a bag of \(n\) cookies?
- Answer: There are \(\binom{n}{k}\) ways to do this, since this is what binomial coefficients count.
- Answer: Instead of picking the cookies we want, let’s pick the cookies we don’t want. We will pick the \(n-k\) cookies that we don’t want, and there’s \(\binom{n}{n-k}\) ways to do this.
Because these both answer the same question, we have that \(\binom{n}{k} = \binom{n}{n-k}\text{.}\)
Example 5.3.6.
Prove the binomial identity
\begin{equation*}
\binom{n}{0}\binom{n}{0}+\binom{n}{1}\binom{n}{1}+\binom{n}{2}\binom{n}{2}+ \cdots + \binom{n}{n} \binom{n}{n} = \binom{2n}{n}
\end{equation*}
Hint.
Video / Answer.
Solution.
How many pizzas of \(n\) toppings can be made if we can choose from \(2n\) toppings?
Note that in the video, I start with a different form of the equation but quickly change it to this one. It’s equivalent.
For this one, I’m going to rewrite the equation, taking advantage of the symmetry property we proved in Example 5.3.5. We start with:
\begin{align*}
\binom{n}{0}\binom{n}{0}+\binom{n}{1}\binom{n}{1}+\binom{n}{2}\binom{n}{2}+ \cdots + \binom{n}{n} \binom{n}{n} \amp= \binom{2n}{n}\\
\binom{n}{0}\binom{n}{n-0}+\binom{n}{1}\binom{n}{n-1}+\binom{n}{2}\binom{n}{n-2}+ \cdots + \binom{n}{n} \binom{n}{n-n} \amp= \binom{2n}{n}
\end{align*}
and this is what we’ll use to prove the identity.
Question: If there are \(n\) meats and \(n\) non-meat toppings for a pizza, how many \(n\) topping pizzas can be made? (if we don’t allow repeat toppings)
- Answer: There are \(\binom{2n}{n}\) total pizzas that can be made.
- Answer: We’ll split on how many meats we want:
- If we want no meats, then we’ll select no meats and \(n\) non-meats. These are independent of one another, so we multiply: \(\binom{n}{0}\binom{n}{n}\)
- If we want 1 meat, then we’ll select \(n-1\) non-meats for the rest of the toppings. These are independent of one another, so we multiply: \(\binom{n}{1}\binom{n}{n-1}\)
- If we want 2 meats, then we’ll select \(n-2\) non-meats for the rest of the toppings. These are independent of one another, so we multiply: \(\binom{n}{2}\binom{n}{n-2}\)
- ...
- If we want n meats, then we’ll select \(n-n=0\) non-meats for the rest of the toppings. These are independent of one another, so we multiply: \(\binom{n}{n}\binom{n}{0}\)
because each of these pizzas are completely different than the rest (have different numbers of meats), the addition principle says to add them all together:\begin{equation*} \binom{n}{0}\binom{n}{n}+\binom{n}{1}\binom{n}{n-1}+\binom{n}{2}\binom{n}{n-2}+ \cdots + \binom{n}{n} \binom{n}{0} \end{equation*}
Because each answer was a different way to count the same objects, we find that
\begin{equation*}
\binom{n}{0}\binom{n}{n-0}+\binom{n}{1}\binom{n}{n-1}+\binom{n}{2}\binom{n}{n-2}+ \cdots + \binom{n}{n} \binom{n}{n-n} = \binom{2n}{n}
\end{equation*}
Exercises Exercises
1.
Prove \(\d\sum_{k=0}^n {n \choose k} = 2^n\text{.}\)
Hint.
Here are two different ways to go about it:
- Combinatorial proof: Answer the question “If a pizza place offers \(n\) toppings, how many pizzas can you build using any number of toppings using each topping no more than once?”
- Or, use the binomial theorem and set appropriate values of \(x \and y\text{.}\)
2.
Give a combinatorial proof of the identity \(2+2+2 = 3\cdot 2\text{.}\)
Solution.
Proof.
Question: How many 2-letter words start with a, b, or c and end with either y or z?
Answer 1: There are two words that start with a, two that start with b, two that start with c, for a total of \(2+2+2\text{.}\)
Answer 2: There are three choices for the first letter and two choices for the second letter, for a total of \(3 \cdot 2\text{.}\)
Since the two answers are both answers to the same question, they are equal. Thus \(2 + 2 + 2 = 3\cdot 2\text{.}\)
3.
Give a combinatorial proof for the identity \(1 + 2 + 3 + \cdots + n = {n+1 \choose 2}\text{.}\)
Solution.
Proof.
Question: How many subsets of \(A = \{1,2,3, \ldots, n+1\}\) contain exactly two elements?
Answer 1: We must choose 2 elements from \(n+1\) choices, so there are \({n+1 \choose 2}\) subsets.
Answer 2: We break this question down into cases, based on what the larger of the two elements in the subset is. The larger element can’t be 1, since we need at least one element smaller than it.
Larger element is 2: there is 1 choice for the smaller element.
Larger element is 3: there are 2 choices for the smaller element.
Larger element is 4: there are 3 choices for the smaller element.
And so on. When the larger element is \(n+1\text{,}\) there are \(n\) choices for the smaller element. Since each two element subset must be in exactly one of these cases, the total number of two element subsets is \(1 + 2 + 3 + \cdots + n\text{.}\)
Answer 1 and answer 2 are both correct answers to the same question, so they must be equal. Therefore,
\begin{equation*}
1 + 2 + 3 + \cdots + n = {n+1 \choose 2}
\end{equation*}
4.
A woman is getting married. She has 15 best friends but can only select 6 of them to be her bridesmaids, one of which needs to be her maid of honor. How many ways can she do this?
- What if she first selects the 6 bridesmaids, and then selects one of them to be the maid of honor?
- What if she first selects her maid of honor, and then 5 other bridesmaids?
- Explain why \(6 {15 \choose 6} = 15 {14 \choose 5}\text{.}\)
Solution.
- She has \({15 \choose 6}\) ways to select the 6 bridesmaids, and then for each way, has 6 choices for the maid of honor. Thus she has \({15 \choose 6}6\) choices.
- She has 15 choices for who will be her maid of honor. Then she needs to select 5 of the remaining 14 friends to be bridesmaids, which she can do in \({14 \choose 5}\) ways. Thus she has \(15 {14 \choose 5}\) choices.
- We have answered the question (how many wedding parties can the bride choose from) in two ways. The first way gives the left-hand side of the identity and the second way gives the right-hand side of the identity. Therefore the identity holds.
5.
Give a combinatorial proof of the identity \({n \choose 2}{n-2 \choose k-2} = {n\choose k}{k \choose 2}\text{.}\)
Solution.
Proof.
Question: You have a large container filled with ping-pong balls, all with a different number on them. You must select \(k\) of the balls, putting two of them in a jar and the others in a box. How many ways can you do this?
Answer 1: First select 2 of the \(n\) balls to put in the jar. Then select \(k-2\) of the remaining \(n-2\) balls to put in the box. The first task can be completed in \({n \choose 2}\) different ways, the second task in \({n-2 \choose k-2}\) ways. Thus there are \({n \choose 2}{n-2 \choose k-2}\) ways to select the balls.
Answer 2: First select \(k\) balls from the \(n\) in the container. Then pick 2 of the \(k\) balls you picked to put in the jar, placing the remaining \(k-2\) in the box. The first task can be completed in \({n \choose k}\) ways, the second task in \({k \choose 2}\) ways. Thus there are \({n \choose k}{k \choose 2}\) ways to select the balls.
Since both answers count the same thing, they must be equal and the identity is established.
6.
How many ways are there to rearrange the letters in the word “rearrange”? Answer this question in at least two different ways to establish a binomial identity.
Solution.
The word contains 9 letters: 3 “r”s, 2 “a”s and 2 “e”s, along with an “n” and a “g”. We could first select the positions for the “r”s in \({9 \choose 3}\) ways, then the “a”s in \({6 \choose 2}\) ways, the “e”s in \({4 \choose 2}\) ways and then select one of the remaining two spots to put the “n” (placing the “g” in the last spot). This gives the answer
\begin{equation*}
{9 \choose 3}{6 \choose 2}{4 \choose 2}{2\choose 1}{1\choose 1}.
\end{equation*}
Alternatively, we could select the positions of the letters in the opposite order, which would give an answer
\begin{equation*}
{9 \choose 1}{8\choose 1}{7 \choose 2}{5\choose 2}{3\choose 3}.
\end{equation*}
(where the 3 “r”s go in the remaining 3 spots). These two expressions are equal:
\begin{equation*}
{9 \choose 3}{6 \choose 2}{4 \choose 2}{2\choose 1}{1\choose 1} = {9 \choose 1}{8\choose 1}{7 \choose 2}{5\choose 2}{3\choose 3}.
\end{equation*}
7.
Give a combinatorial proof of the identity \(1 + 2 + 4 + 8 + \dots 2^{n-1} = 2^n - 1\)
8.
Give a combinatorial proof for the identity \(P(n,k) = {n \choose k}k!\)
Solution.
Proof.
Question: How many \(k\)-letter words can you make using \(n\) different letters without repeating any letter?
Answer 1: There are \(n\) choices for the first letter, \(n-1\) choices for the second letter, \(n-2\) choices for the third letter, and so on until \(n - (k-1)\) choices for the \(k\)th letter (since \(k-1\) letters have already been assigned at that point). The product of these numbers can be written \(\frac{n!}{(n-k)!}\) which is \(P(n,k)\text{.}\) Therefore there are \(P(n,k)\) words.
Answer 2: First pick \(k\) letters to be in the word from the \(n\) choices. This can be done in \({n \choose k}\) ways. Now arrange those letters into a word. There are \(k\) choices for the first letter, \(k-1\) choices for the second, and so on, for a total of \(k!\) arrangements of the \(k\) letters. Thus the total number of words is \({n \choose k}k!\text{.}\)
Since the two answers are correct answers to the same question, we have established that \(P(n,k) = {n \choose k}k!\text{.}\)
9.
Establish the identity below using a combinatorial proof.
\begin{equation*}
{2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2} = {n+3 \choose 5}.
\end{equation*}
Solution.
Proof.
Question: How many 5-element subsets are there of the set \(\{1,2,\ldots, n+3\}\text{.}\)
Answer 1: We choose 5 out of the \(n+3\) elements, so \({n+3 \choose 5}\) subsets.
Answer 2: Break this up into cases by what the “middle” (third smallest) element of the 5 element subset is. The smallest this could be is a 3. In that case, we have \({2 \choose 2}\) choices for the numbers below it, and \({n \choose 2}\) choices for the numbers above it. Alternatively, the middle number could be a 4. In this case there are \({3 \choose 2}\) choices for the bottom two numbers and \({n-1 \choose 2}\) choices for the top two numbers. If the middle number is 5, then there are \({4 \choose 2}\) choices for the bottom two numbers and \({n-2 \choose 2}\) choices for the top two numbers. An so on, all the way up to the largest the middle number could be, which is \(n+1\text{.}\) In that case there are \({n \choose 2}\) choices for the bottom two numbers and \({2 \choose 2}\) choices for the top number. Thus the number of 5 element subsets is
\begin{equation*}
{2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2}.
\end{equation*}
Since the two answers correctly answer the same question, we have
\begin{equation*}
{2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2} = {n+3 \choose 5}.
\end{equation*}
10.
In each polynomial below, assume \(x\) is some variable. Use the binomial theorem to expand and reduce modulo the appropriate number:
- \(\displaystyle (x+1)^2 \pmod 2 \)
- \(\displaystyle (x+1)^5 \pmod 5 \)
- \(\displaystyle (x+1)^7 \pmod 7 \)
Prove that \((x+1)^p \equiv x^p + 1 \pmod p\) for any prime \(p\text{.}\)
Solution.
Here’s a partial solution:
- \(\displaystyle (x+1)^2 = x^2 + 2x + 1 \equiv x^2 + 1 \pmod 2 \)
- \(\displaystyle (x+1)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1 \equiv x^5 + 1 \pmod 5 \)
What can be said about each each binomial coefficient except the first and the last? Why?
