Theorem 9.6.1.
Let \(n, r\) be nonnegative integers with \(r\leq n\text{.}\) Then
\begin{equation*}
\binom{n}{r}=\binom{n}{n-r}.
\end{equation*}
Section 9.6 Binomial Theorem
The Binomial Theorem has applications in many areas of mathematics, from calculus, to number theory, to probability. In this section we look at some examples of combinatorial proofs using binomial coefficients and ultimately prove the Binomial Theorem using induction.
An algebraic proof is straightforward and left as an exercise (see Exercise 9.6.1). We will give a combinatorial proof. This means we will prove the two sides of the equation are equal by showing that they are two different ways to count the same set. In general, a combinatorial proof is done by giving a counting argument.
Proof.
By definition, \(\binom{n}{r}\) is the number of subsets where we choose \(r\) objects from \(n\) objects.
We can create a set of \(r\) objects by specifying which objects are in the set or by specifying which objects are not in the set. We note that there are \(n-r\) objects not in the set. Thus, \(\binom{n}{n-r}\) counts the ways to find a set of \(r\) objects out of \(n\) objects by finding the ways to not include \(n-r\) objects. Thus, both \(\binom{n}{r}\) and \(\binom{n}{n-r}\) count subsets of \(r\) objects from \(n\text{,}\) one by counting the objects in the set, one by counting the objects not in the set.
Theorem 9.6.2. Pascal’s Formula.
Let \(n, r\) be nonnegative integers with \(r\leq n\text{.}\) Then
\begin{equation*}
\binom{n+1}{r}=\binom{n}{r-1}+\binom{n}{r}.
\end{equation*}
We leave the algebraic proof as an exercise (see Activity 9.6.1), and instead provide a combinatorial proof.
Proof.
By definition, \(\binom{n+1}{r}\) counts the subsets of \(r\) objects chosen from \(n+1\) objects.
Let \(S=\{x_1, x_2, \ldots x_{n+1}\}\text{,}\) a set of \(n+1\) objects. We can create all the subsets of \(r\) objects by choosing all \(r\) objects from \(\{x_1, \ldots, x_n\}\) or by choosing \(r-1\) out of \(\{x_1, \ldots, x_n\}\) and including \(x_{n+1}\text{.}\) Thus, we can count the subsets of \(r\) objects from \(n\) objects with \(\binom{n}{r}+\binom{n}{r-1}\text{.}\)
Activity 9.6.1.
Give an algebraic proof for Pascal’s Formula:
\begin{equation*}
{{n+1}\choose {r}}={n\choose {r-1}}+{n \choose r}.
\end{equation*}
Hint.
Start with the right-hand side. Use the definition of “choose,” then find a common denominator. Note, you will save yourself a lot of work if you find the least common denominator.
We often call terms of the form \(\binom{n}{r}\) binomial coefficients.
There is a connection between binomial coefficients and Pascal’s Triangle.
You may have seen Pascal’s Triangle before, the start of which is
| 1 | ||||||
| 1 | 1 | |||||
| 1 | 2 | 1 | ||||
| 1 | 3 | 3 | 1 |
We get each number in a row by adding the two numbers above. If there is only one number, you just get 1. For example, the fourth row is 1, 3, 3, 1, since \(1+2=3\text{.}\) The next row would be 1, 4, 6, 4, 1.
If we think about the first row as actually being the 0th row, we can make a triangle with the binomial coefficients:
| \(\binom{0}{0}\) | ||||||
| \(\binom{1}{0}\) | \(\binom{1}{1}\) | |||||
| \(\binom{2}{0}\) | \(\binom{2}{1}\) | \(\binom{2}{2}\) | ||||
| \(\binom{3}{0}\) | \(\binom{3}{1}\) | \(\binom{3}{2}\) | \(\binom{3}{3}\) |
If you calculate the binomial coefficients, you will see that you get the same values as Pascal’s Triangle. Furthermore, Pascal’s Formula is just the rule we use to get the triangle: add the \(r-1\) and \(r\) terms from the \(n^{th}\) row to get the \(r\) term in the \(n+1\) row.
A binomial is an expression of the form \(a+b\text{.}\)
The Binomial Theorem gives a formula for calculating \((a+b)^n\text{.}\) We can prove the Binomial Theorem combinatorially or algebraically. We will provide the algebraic proof, which is a proof by induction. Although we do not provide the details of the combinatorial proof, the next example should give some insight into the combinatorial argument.
Example 9.6.3. A Combinatorial Calculation for \((a+b)^3\).
Suppose we want to expand (or multiply) \((a+b)^3=(a+b)(a+b)(a+b)\text{.}\) We can think of the multiplication in this way,
- there is 1 way to get \(a^3\text{:}\) choose 0 \(b\)’s from the three factors.
- there are 3 ways to get \(a^2b\text{:}\) choose 1 \(b\) from the three factors.
- there are 3 ways to get \(ab^2\text{:}\) choose 2 \(b\)’s’ from the three factors.
- there is 1 way to get \(b^3\text{:}\) choose 3 \(b\)’s from the three factors.
This give us
\begin{equation*}
(a+b)^3=\binom{3}{0}a^3+\binom{3}{1}a^2b+\binom{3}{2}ab^2+\binom{3}{3}b^3.
\end{equation*}
Example 9.6.3 can be generalized to \((a+b)^n\) in the Binomial Theorem.
Theorem 9.6.4. Binomial Theorem.
Let \(n\) be a nonnegative integer, then
\begin{align*}
(a+b)^n&= \binom{n}{0}a^n+\binom{n}{1}a^{n-1}b+\binom{n}{2}a^{n-2}b^{2}+\cdots +\binom{n}{n-1}ab^{n-1}+\binom{n}{n}b^n\\
&=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k.
\end{align*}
Proof.
Prove
\begin{equation*}
(a+b)^n=\sum_{i=0}^{n}\binom{n}{i}a^{n-i}b^i
\end{equation*}
by induction on \(n\text{.}\)
Base step: Let \(n=0\text{.}\) Then
\begin{equation*}
(a+b)^0=1\text{.}
\end{equation*}
Also,
\begin{equation*}
\sum_{i=0}^{0}\binom{0}{i}a^{0-i}b^i=a^0b^0=1.
\end{equation*}
Induction step: Assume \((a+b)^k=\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i\text{.}\)
Show \((a+b)^{k+1}=\sum_{i=0}^{k+1}\binom{k+1}{i}a^{k+1-i}b^i\)
\begin{align*}
(a+b)^{k+1}&=(a+b)^k(a+b)\\
&=\biggl(\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i\biggr)(a+b)\\
&=a\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i+b\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^i\\
&=\sum_{i=0}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^{i+1}
\end{align*}
Now we want to change the index of the second sum. This is just a substitution of variable that allows us to shift how we index the terms. If we were to write out the sum, rather than have it in summation notation, we would not need this step. But it allows us to easily combine like terms in the two summations. So, in the second sum, let \(j=i+1\text{,}\) so when \(i=0, j=1\text{;}\) when \(i=k, j=k+1\text{,}\) and \(i=j-1\text{.}\) We get
\begin{align*}
(a+b)^{k+1}&=\sum_{i=0}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{i=0}^{k}\binom{k}{i}a^{k-i}b^{i+1}\\
&=\sum_{i=0}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{j=1}^{k+1}\binom{k}{j-1}a^{k+1-j}b^j\\
&=a^{k+1}+\sum_{i=1}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{j=1}^{k}\binom{k}{j-1}a^{k+1-j}b^j+b^{k+1}\\
&\text{where we pulled out the first term of the first sum}\\
&\text{and the last term of the second sum}\\
&=a^{k+1}+\sum_{i=1}^{k}\binom{k}{i}a^{k+1-i}b^i+\sum_{i=1}^{k}\binom{k}{i-1}a^{k+1-i}b^i+b^{k+1}\\
&\text{where we just relabeled the index in the second sum}\\
&=a^{k+1}+\sum_{i=1}^{k}\biggl[\binom{k}{i}+\binom{k}{i-1}\biggr]a^{k+1-i}b^i+b^{k+1}\\
&\text{where we combined like terms in the two sums}\\
&=a^{k+1}+\sum_{i=1}^{k}\binom{k+1}{i}a^{k+1-i}b^i+b^{k+1}\\
&\text{by Pascal's Formula}\\
&=\sum_{i=0}^{k+1}\binom{k+1}{i}a^{k+1-i}b^i
\end{align*}
Activity 9.6.2.
Show the Binomial Theorem holds for \(n=2\) and \(n=3\text{.}\)
The Binomial Theorem relates a sum to a power of a binomial. Although we often think of using the Binomial Theorem as a way to calculate the coefficients for expanding \((a+b)^n\text{,}\) it can also be used to simplify certain sums. In this case, the power of the binomial is the closed form.
Example 9.6.5. Expressing a Sum in Closed Form.
Express the sum, \(\sum_{i=0}^{n}\binom{n}{i}x^i\text{,}\) in closed form.
For problems such as this, we need to identify \(a\) and \(b\) as in the Binomial Theorem.
We can see that \(x=b\text{,}\) since the power of \(x\) matches the power of \(b\text{.}\) Since there does not appear to be any term for \(a\text{,}\) we can let \(a=1\text{.}\) Thus, the closed form is \((1+x)^n\text{.}\)
Activity 9.6.3.
Use the Binomial Theorem to find \((3-2x)^3\text{.}\)
Hint.
In this expression, what are \(a, b, n\text{?}\)
Activity 9.6.4.
Prove \(2^n=\sum_{k=0}^n{n \choose k}\text{.}\)
Hint.
Use that \(2=(1+1)\text{.}\)
Reading Questions Check Your Understanding
1.
Use the Binomial Theorem to find \((a+b)^4\text{.}\)
Hint.
There should be 5 terms in your answer.
2.
Use the Binomial Theorem to find \((a+2)^4\text{.}\)
Hint.
There should be 5 terms in your answer.
3.
Use the Binomial Theorem to find \((a-2)^4\text{.}\)
Hint.
There should be 5 terms in your answer.
4.
Use the Binomial Theorem to find the coefficient of \(x^2y^2\) in \((3x-2y)^4\text{.}\)
Note, your answer should not include any variables.
5.
Use the Binomial Theorem to find the coefficient of \(x^5y^2\) in \((3x-2y)^7\text{.}\)
Note, your answer should not include any variables.
6.
Use the Binomial Theorem to find the coefficient of \(x^4y^3\) in \((3x-2y)^7\text{.}\)
Note, your answer should not include any variables.
Exercises Exercises
1.
Give an algebraic proof for the formula in Theorem 9.6.1:
\begin{equation*}
{{n}\choose {r}}={n\choose {n-r}}
\end{equation*}
for integers \(n\) and \(r\) with \(0\leq r\leq n\text{.}\)
2.
Use Pascal’s triangle to find the following binomial coefficients.
- Find the values of \({6\choose 2}, {6\choose 3}, {6\choose 4}\) and \({6\choose 5}\text{.}\)
- Use the result of part (a) to find \({7\choose 3}\text{,}\) \({7\choose 4}\text{,}\) and \({7\choose 5}\text{.}\)
- Complete the row of Pascal’s triangle that corresponds to \(n=7\text{.}\)
3.
The row of Pascal’s triangle that corresponds to \(n=8\) is
\begin{equation*}
1\ \ \ 8\ \ \ 28\ \ \ 56\ \ \ 70\ \ \ 56\ \ \ 28\ \ \ 8\ \ \ 1.
\end{equation*}
What is the row that corresponds to \(n=9\text{?}\)
4.
Use the Binomial Theorem to expand \((u-v)^5\text{.}\)
5.
Use the Binomial Theorem to expand \((p-2q)^4\text{.}\)
6.
Find the coefficient of \(x^6y^3\) in \((x+y)^9\text{.}\)
7.
Find the coefficient of \(x^7\) in \((2x+3)^{10}\text{.}\)
8.
Express \(\sum_{k=0}^n{n\choose k}5^k\) in closed form (without the summation symbol and without ellipses,…).
9.
Express \(\sum_{k=0}^m{m\choose k}2^{m-k}x^k\) in closed form (without the summation symbol and without ellipses,…).
10.
Use Pascal’s Formula to prove by mathematical induction that if \(n\) is an integer and \(n\geq 1\text{,}\) then
\begin{equation*}
\sum_{i=2}^{n+1}{i\choose 2}={2\choose 2}+{3\choose 2}+\ldots +{{n+1}\choose 2}={{n+2}\choose 3}.
\end{equation*}
11.
Think of a set with \(m+n\) elements as composed of two parts, one with \(m\) elements and one with \(n\) elements. Give a combinatorial argument to show that
\begin{equation*}
{{m+n}\choose r}={m\choose 0}{n\choose r}+{m\choose 1}{n\choose r-1}+\ldots +{m\choose r}{n\choose 0}.
\end{equation*}
Hint.
Think of counting a single set in two different ways, where one side of the equation represents one way and the other side represents the other way. Since they both count the same set, they should be equal.
12.
Use the Binomial Theorem to prove for all integers \(n\geq 1\text{,}\)
\begin{equation*}
{n\choose 0}-{n\choose 1}+{n\choose 2}-\ldots +(-1)^n{n\choose n}=0.
\end{equation*}
Hint.
Use the fact that \(1+(-1)=0\text{.}\)
13.
Use the Binomial Theorem to prove for all integers \(n\geq 0\text{,}\)
\begin{equation*}
3^n={n\choose 0}+2{n\choose 1}+2^2{n\choose 2}+\ldots +2^n{n\choose n}.
\end{equation*}
You have attempted of activities on this page.
