Skip to main content

Section 9.4 The Arithmetic Triangle

In Chapter 2, we saw three counting techniques: steps (where we multiply), cases (where we add), and subsets (where we use binomial coefficients). In Section 9.1 and Section 9.3, we worked with sums and products. In this section, we revisit the binomial coefficients, defined in Definition 2.3.5, which are
\begin{equation*} \binom{n}{k} = \text{ the number of ways to select a subset of } k \text{ elements from a set of } n \text{ elements } \end{equation*}
for nonnegative integers \(n\) and \(k\text{.}\) We introduce the arithmetic triangle.
 1 
The arithmetic triangle was formerly known as Pascal’s triangle, and the generic name honors that the arithmetic triangle was known in Asia, the middle East, and Europe countries centuries before Pascal lived.
We examine the recursion that generates the arithmetic triangle, which is useful for computation, and search for patterns among the binomial coefficients, including summations. We also explain the origin of the name “binomial coefficient” and we derive an explicit formula for the binomial coefficients which is of theoretical use.

Subsection 9.4.A The Arithmetic Triangle

How do we calculate the value of \(\binom{n}{k}\text{?}\) Let’s first look at an example using the definition.

Example 9.4.1 Evaluating a binomial coefficient by listing subsets.

Evaluate \(\binom{7}{4}\) without using computational technology.
Solution.
By Definition 2.3.5, we can count all 4-element subsets of a set with seven elements, say \(\{1,2,3,4,5,6,7\}\text{.}\) We list these subsets in Table 9.4.2.
Table 9.4.2. The 4-element subsets of the set \(\{1,2,3,4,5,6,7\}\)
\(\{1,2,3,4\}\) \(\{1,2,3,5\}\) \(\{1,2,3,6\}\) \(\{1,2,3,7\}\) \(\{1,2,4,5\}\)
\(\{1,2,4,6\}\) \(\{1,2,4,7\}\) \(\{1,2,5,6\}\) \(\{1,2,5,7\}\) \(\{1,2,6,7\}\)
\(\{1,3,4,5\}\) \(\{1,3,4,6\}\) \(\{1,3,4,7\}\) \(\{1,3,5,6\}\) \(\{1,3,5,7\}\)
\(\{1,3,6,7\}\) \(\{1,4,5,6\}\) \(\{1,4,5,7\}\) \(\{1,4,6,7\}\) \(\{1,5,6,7\}\)
\(\{2,3,4,5\}\) \(\{2,3,4,6\}\) \(\{2,3,4,7\}\) \(\{2,3,5,6\}\) \(\{2,3,5,7\}\)
\(\{2,3,6,7\}\) \(\{2,4,5,6\}\) \(\{2,4,5,7\}\) \(\{2,4,6,7\}\) \(\{2,5,6,7\}\)
\(\{3,4,5,6\}\) \(\{3,4,5,7\}\) \(\{3,4,6,7\}\) \(\{3,5,6,7\}\) \(\{4,5,6,7\}\)
There are 35 subsets, so \(\binom{7}{4}=35\text{.}\)
There are some values of binomial coefficients that we can compute from the definition.

Example 9.4.3 Border values of binomial coefficients.

 
  1. Explain why \(\binom{n}{0}=1\) and \(\binom{n}{n}=1\) using the definition of the binomial coefficients.
    Solution.
    Given a set with \(n\) elements, there is only one 0-element subsets, namely the empty set \(\varnothing\text{.}\) Similarly, there is only one \(n\)-element subset, namely the set itself.
  2. Explain why \(\binom{n}{1}=n\) using the definition of the binomial coefficients.
    Solution.
    Given a set with \(n\) elements, there are \(n\) 1-element subsets, one for each element of the set.
Listing the \(k\)-element subsets of a set with \(n\) elements is tedious, even for small values of \(n\) and \(k\text{,}\) and it is impractical for any larger values. We would like a more efficient way to calculate the values of \(\binom{n}{k}\) by hand for small values of \(n\) and \(k\text{.}\) For larger values, we seek a recursive definition to compute the values. We begin with a way to list binomial coefficients in a triangular array.

Definition 9.4.4 The arithmetic triangle.

The arithmetic triangle is an array of binomial coefficients, where each row has, in order, the values \(\binom{n}{k}\text{,}\) for \(k=0,1,2, \ldots, n\text{.}\)
For example, the first row has a single value, \(\binom{0}{0}=1\text{.}\) The second row has, in order, the values \(\binom{1}{0}=1\) and \(\binom{1}{1}=1\text{.}\) The third row has, in order, the values \(\binom{2}{0}=1\text{,}\) \(\binom{2}{1}=2\text{,}\) and \(\binom{2}{2}=1\text{.}\)
Figure 9.4.5 shows the first eight rows of the expanded version of the arithmetic triangle that includes the binomial coefficients and their values, which can be crowded to read. Figure 9.4.6 shows the first eight rows of the standard, easier-to-read version that lists only the values.
\begin{equation*} \tbinom{0}{0}=1 \end{equation*}
\begin{equation*} \tbinom{1}{0}=1 \hspace{.07in} \tbinom{1}{1}=1 \end{equation*}
\begin{equation*} \tbinom{2}{0}=1 \hspace{.07in} \tbinom{2}{1}=2 \hspace{.07in} \tbinom{2}{2}=1 \end{equation*}
\begin{equation*} \tbinom{3}{0}=1 \hspace{.07in} \tbinom{3}{1}=3 \hspace{.07in} \tbinom{3}{2}=3\hspace{.07in} \tbinom{3}{3}=1 \end{equation*}
\begin{equation*} \tbinom{4}{0}=1 \hspace{.07in} \tbinom{4}{1}=4 \hspace{.07in} \tbinom{4}{2}=6 \hspace{.07in} \tbinom{4}{3}=4\hspace{.07in} \tbinom{4}{4}=1 \end{equation*}
\begin{equation*} \tbinom{5}{0}=1 \hspace{.07in} \tbinom{5}{1}=5 \hspace{.07in} \tbinom{5}{2}=10 \hspace{.07in} \tbinom{5}{3}=10\hspace{.07in} \tbinom{5}{4}=5\hspace{.07in} \tbinom{5}{5}=1 \end{equation*}
\begin{equation*} \tbinom{6}{0}=1 \hspace{.07in} \tbinom{6}{1}=6\hspace{.07in} \tbinom{6}{2}=15 \hspace{.07in} \tbinom{6}{3}=20\hspace{.07in} \tbinom{6}{4}=15\hspace{.07in} \tbinom{6}{5}=6\hspace{.07in} \tbinom{6}{6}=1 \end{equation*}
\begin{equation*} \tbinom{7}{0}=1 \hspace{.07in} \tbinom{7}{1}=7\hspace{.07in} \tbinom{7}{2}=21 \hspace{.07in} \tbinom{7}{3}=35\hspace{.07in} \tbinom{7}{4}=35\hspace{.07in} \tbinom{7}{5}=21\hspace{.07in} \tbinom{7}{6}=7\hspace{.07in} \tbinom{7}{7}=1 \end{equation*}
Figure 9.4.5. The first eight rows of the arithmetic triangle in expanded format.
\begin{equation*} 1 \end{equation*}
\begin{equation*} 1 \hspace{.23in} 1 \end{equation*}
\begin{equation*} 1 \hspace{.23in} 2 \hspace{.23in} 1 \end{equation*}
\begin{equation*} 1 \hspace{.23in} 3 \hspace{.23in} 3\hspace{.23in} 1 \end{equation*}
\begin{equation*} 1 \hspace{.23in} 4 \hspace{.23in} 6 \hspace{.23in} 4\hspace{.23in}1 \end{equation*}
\begin{equation*} 1 \hspace{.23in} 5 \hspace{.23in} 10 \hspace{.23in} 10\hspace{.23in} 5\hspace{.23in} 1 \end{equation*}
\begin{equation*} 1 \hspace{.23in} 6\hspace{.23in} 15 \hspace{.23in} 20\hspace{.23in}15\hspace{.23in} 6\hspace{.23in} 1 \end{equation*}
\begin{equation*} 1 \hspace{.23in} 7\hspace{.23in} 21 \hspace{.23in} 35\hspace{.23in} 35\hspace{.23in}21\hspace{.23in} 7\hspace{.23in} 1 \end{equation*}
Figure 9.4.6. The first eight rows of the arithmetic triangle in standard format.
We can use the arithmetic triangle to evaluate binomial coefficients.

Example 9.4.7 Using the arithmetic triangle to evaluate binomial coefficients.

Use the arithmetic triangle drawn in Figure 9.4.6 to evaluate each binomial coefficient. If you are not sure where to look in the triangle, refer to Figure 9.4.5.
  1. Evaluate \(\displaystyle \binom{4}{2}\text{.}\)
    Solution.
    The row that starts with 1, 4 lists
    \begin{equation*} \binom{4}{0}=1, \binom{4}{1}=4, \binom{4}{2}=6, \ldots\text{.} \end{equation*}
    This answer agrees with our list of the 2-element subsets of \(\{1,2,3,4\}\) from Example 2.3.7.
  2. Evaluate \(\displaystyle \binom{6}{4}\text{.}\)
    Solution.
    The row that starts with 1, 6 lists \(\displaystyle \binom{6}{k}\) for \(k=0, 1, 2, 3, 4, \ldots\text{.}\) Because the list begins at \(k=0\text{,}\) the fifth number in that row gives
    \begin{equation*} \displaystyle \binom{6}{4}=15\text{.} \end{equation*}
Try working with the arithmetic triangle.

Activity 9.4.A The arithmetic triangle.

 
  1. Copy the first eight rows of the arithmetic triangle.
  2. Use the arithmetic triangle to evaluate each of the following binomial coefficients and circle the corresponding entries in the triangle.
    \begin{equation*} \binom{5}{4}, \binom{7}{5}, \binom{3}{0}, \binom{6}{1}, \binom{2}{2}\text{.} \end{equation*}
  3. There is a way to calculate the row that starts with 1, 7 from the row above it. Can you see how? (Do not spoil the surprise for others if you already know the answer.) Hint: Each entry of the row is calculated using two nearby entries from the previous row.
  4. Use the pattern from (c) to write the next row that starts with 1, 8.
  5. Use your new row to evaluate each of the following binomial coefficients:
    \begin{equation*} \binom{8}{2}, \binom{8}{4}, \binom{8}{5}\text{.} \end{equation*}
  6. Write a formula for how to calculate the row that stars \(1, n\) from the row above it. Your formula should be in the form \(\displaystyle \binom{n}{k} =\text{.}\) Hint: The entries from the row above will involve \(n-1\) and \(k\)s.
Make sure to complete Activity 9.4.A before reading on because we are going to share the key observation.

Remark 9.4.9 Generating the arithmetic triangle.

We can generate the arithmetic triangle as follows.
  1. The first row is 1.
  2. The entry in each subsequent row is the sum of the two entries above it in the previous row, with the understanding that a missing entry equals zero.
We state this recursion formally.
Let’s see this formula in action.

Example 9.4.11 Adding another row to the arithmetic triangle.

Use Theorem 9.4.10 to write the row of the arithmetic triangle that begins with 1, 8.
Solution.
We begin with a copy of the row that begins with 1, 7 from Figure 9.4.6. We add neighboring entries to calculate the entries of the next row:
\begin{equation*} 0+1=1 1+7=8 7 +21 = 28 21+35 = 56 35+35=70 \end{equation*}
\begin{equation*} 35+21 = 56 21+7 = 28 7+1 = 8 1 + 0 = 1 \end{equation*}
The result is shown in Figure 9.4.12.
Figure 9.4.12. Generating another row of the arithmetic triange.

Subsection 9.4.B Patterns in the Arithmetic Triangle

There are many patterns that involve binomial coefficients.

Activity 9.4.B Looking for patterns in the arithmetic triangle.

 
  1. Do you notice a symmetry in the arithmetic triangle? State your observation as a conjecture of the form \(\binom{n}{k}=\binom{n}{}\text{.}\)
  2. Calculate the sum of the entries in each of row of the arithmetic triangle. What did you notice? State your observation as a conjecture, using summation notation for the sum.
  3. Conjecture an explicit formula for the sum
    \begin{equation*} \sum_{k=0}^n(-1)^k\binom{n}{k} \end{equation*}
    for \(n \ge 0\text{.}\) Hint: Calculate the sum when \(n=3\) and \(n=4\) first.
Let’s look at the first two patterns from Activity 9.4.B. We begin with the left-right symmetry.
We can use this theorem to evaluate binomial coefficients.

Example 9.4.15 Using the symmetry in the arithmetic triangle.

 
  1. Evaluate \(\binom{n}{n-1}\) for a integer \(n\ge 1\text{.}\)
    Solution.
    We saw in Example 9.4.3 that \(\binom{n}{1}=1\text{.}\) Using symmetry Theorem 9.4.14, we get
    \begin{equation*} \binom{n}{n-1} = \binom{n}{n-(n-1)} = \binom{n}{1} = n \end{equation*}
  2. Explain why \(\binom{n}{n-2} = \binom{n}{2}\text{.}\)
    Solution.
    Using symmetry Theorem 9.4.14, we get
    \begin{equation*} \binom{n}{n-2} = \binom{n}{n-(n-2)}=\binom{n}{2} \end{equation*}
Next, let’s look at the row sums.

Example 9.4.16 Sums of rows of the arithmetic triangle.

 
  1. Calculate the sum of the entries in the eighth row of the arithmetic triangle.
    Solution.
    We add the entries to get
    \begin{equation*} 1+7+21+35+35+21+7+1 =128\text{.} \end{equation*}
  2. What did you notice? Conjecture an explicit formula for the sum.
    Solution.
    We notice that
    \begin{equation*} \sum_{k=0}^7\binom{7}{k} = 1+7+21+35+35+21+7+1 =128 = 2^7\text{.} \end{equation*}
    We conjecture that
    \begin{equation*} \sum_{k=0}^n\binom{n}{k}=2^n \end{equation*}
Let’s state our conjecture. We prove it in Exercise 17 and using a different method in Section 9.5.
Here is another summation pattern that involves the binomial coefficients.

Example 9.4.18 Hockey stick.

 
  1. Use the arithmetic triangle to evaluate \(\displaystyle \sum_{k=2}^5 \binom{k}{2}\text{.}\)
    Solution.
    \begin{equation*} \sum_{k=2}^5 \binom{k}{2} = \binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2} = 1 + 3 + 6 + 10 = 20 \end{equation*}
  2. Use the arithmetic triangle to evaluate \(\displaystyle \sum_{k=3}^7 \binom{k}{3}\text{.}\)
    Solution.
    \begin{equation*} \sum_{k=3}^7 \binom{k}{3} = \binom{3}{3} + \binom{4}{3} + \binom{5}{3} + \binom{6}{3} + \binom{7}{3} = 1 + 4 + 10 + 20 + 35 = 70 \end{equation*}
  3. Conjecture an explicit formula for the sum \(\displaystyle \sum_{k=m}^n \binom{k}{m}\text{.}\)
    Solution.
    From (a) we know
    \begin{equation*} \sum_{k=2}^5 \binom{k}{2} = 20 = \binom{6}{3}\text{.} \end{equation*}
    From (b) we know
    \begin{equation*} \sum_{k=3}^7 \binom{k}{3} = 70 = \binom{8}{4}\text{.} \end{equation*}
    Based on these two examples, it is reasonable to conjecture that
    \begin{equation*} \sum_{k=m}^n \binom{k}{m} = \binom{n+1}{m+1} \end{equation*}
  4. Why is this called the “hockey stick” theorem?
    Solution.
    For example, the sum from (a) is highlighted in Figure 9.4.19. The shape of the encircling polygon looks like a hockey stick.
    Figure 9.4.19. An example of a hockey stick sum.

Subsection 9.4.C The Binomial Theorem

The binomial coefficients get their name from polynomials involving two variables that have the binomial coefficients as their coefficients.
 2 
The word “binomial” literally means two names, like \(x\) and \(y\text{.}\)
In our first activity, we look at polynomials in one variable.

Activity 9.4.C Powers of \(n+1\).

 
  1. Expand and simplify \((n+1)^2\text{.}\) Hint: Start by writing
    \begin{equation*} (n+1)^2=(n+1)(n+1). \end{equation*}
  2. Expand and simplify \((n+1)^3\text{.}\) Hint: Multiply \((n+1)\) times your answer to (a).
  3. Check that you found the first two formulas listed here:
    \begin{align*} (n+1)^2 \amp =n^2+2n+1\\ (n+1)^3 \amp =n^3 +3n^2+3n+1\\ (n+1)^4 \amp =n^4+4n^3+6n^2+4n+1 \end{align*}
    We provided the third equation so that you have another example. Based on these examples, what is the connection between \((n+1)^m\) and the binomial coefficients? Explain in words.
  4. Conjecture a formula for \((n+1)^m\) using summation notation. Hint: The powers on \(n\) decrease, so try using \(x^{m-k}\) in your formula.
In Activity 9.4.C, we observe that the coefficients of \((n+1)^m\) are the binomial coefficients.

Remark 9.4.21 Special case of the binomial theorem.

For any integer \(n\) and nonnegative integer \(m\text{,}\) we have
\begin{equation*} (n+1)^m = \sum_{k=0}^m \binom{m}{k}n^{m-k} \end{equation*}
Let’s look at an example.

Example 9.4.22 Using the special case of the binomial theorem.

Expand \((n+1)^7\) using Remark 9.4.21.
Solution.
We get
\begin{align*} (n+1)^7 \amp = \sum_{k=0}^7n^{7-k}\\ \amp = \binom{7}{0}n^7 + \binom{7}{1}n^6 + \binom{7}{2} n^5 + \binom{7}{3}n^4 + \binom{7}{4} n^3 + \binom{7}{5}n^2+ \binom{7}{6}n + \binom{7}{7}\\ \amp = n^7 + 7n^6 + 21n^5 + 35n^4 + 35n^3 + 21 n^2 + 7n+1\text{.} \end{align*}
The coefficients 1, 7, 21, 35, 35, 21, 7, and 1 come from the eighth row of the arithmetic triangle Figure 9.4.6.
The pattern works for the sum of two real numbers, \(x\) and \(y\text{,}\) raised to a nonnegative integer power.
Notice that if \(x=n\) and \(y=1\text{,}\) then we have the special case in Remark 9.4.21. Let’s practice using this theorem.

Example 9.4.24 Practice using binomial theorem.

Use the binomial theorem Theorem 9.4.23 to expand \((x-2)^3\) and simplify your answer.
Solution.
Our coefficients come from the row beginning 1, 3 in Figure 9.4.6. We use \(m=3\text{,}\) \(x=x\text{,}\) and \(y=-2\) in the binomial theorem to get
\begin{equation*} (x+2)^3=1x^3(-2)^0+3x^3(-2)^1+3x^2(-2)^2+1x^0(-2)^3= n^3-6n^2+12n-8\text{.} \end{equation*}
We can use the Binomial Theorem to prove an explicit formula for a summation.

Example 9.4.25 Using the Binomial Theorem to prove a sum formula.

Use the Binomial Theorem Theorem 9.4.23 to prove our conjecture from Activity 9.4.B (c):
\begin{equation*} \sum_{k=0}^n(-1)^k\binom{n}{k}=0 \end{equation*}
for \(n \ge 0\text{.}\)
Solution.
We use \(x=1\text{,}\) \(y=-1\text{,}\) and \(m=n\) to get
\begin{equation*} (1+(-1))^n=\sum_{k=0}^n\binom{n}{k}1^{n-k}(-1)^k\text{.} \end{equation*}
When we simplify each side we get
\begin{equation*} 0=\sum_{k=0}^n(-1)^k\binom{n}{k} \end{equation*}

Subsection 9.4.D Explicit Formula for Binomial Coefficients

When we count, we often leave binomial coefficients in our answers. If we need an exact value, then we can use computational technology. The fastest way to evaluate binomial coefficients by hand and the method that computational technology uses is the recursive formula Theorem 9.4.10.
There is also an explicit formula for binomial coefficients. Although this formula is impractical for large values of \(n\) and \(k\text{,}\) it can be useful for theoretical purposes. Let’s derive that explicit formula.

Activity 9.4.D Explicit formula for binomial coefficients.

Suppose there are 100 movies and we want to rank our top ten as movie #1, movie #2, …, movie #10.
  1. One option is to choose movie #1, and then choose movie #2, and so on. How many ways are there to rank the movies this way? It is okay to have … in your answer.
  2. Rewrite your answer as a fraction where the numerator is \(100!\) and the denominator is another factorial.
  3. An alternative way to pick your top ten movies would be to first select the ten movies you like best (Step 1), and then to order them from #1 to #10 (Step 2). How many ways are there to rank the movies this way?
  4. Since we are counting the same quantity, the answers you found in (b) and (c) must be equal. Write that equation here.
  5. Solve your equation for \(\binom{100}{10}\text{.}\) What formula did we just prove?
  6. Conjecture the explicit formula for \(\binom{n}{k}\text{.}\)
  7. Test your formula by using it to check by hand that \(\binom{7}{4} = 35\text{,}\) as we saw in Table 9.4.2.
In Activity 9.4.D we derived an explicit formula for the binomial coefficients.
Let’s look at how we might prove Theorem 9.4.27 using a combinatorial proof.

Example 9.4.28 Combinatorial proof of the explicit formula for the binomial coefficients.

Use a combinatorial proof Theorem 2.3.13 to prove Theorem 9.4.27.
Solution.
Proof. We use a combinatorial proof. Consider the following situation there are \(n\) movies. How many ways are there to rank our top \(k\) as movie #1, movie #2, …, movie #\(k\text{?}\)
First, we have \(n\) choices for movie #1, and then \(n-1\) choices for movie #2, and so on until \(n-(k-1)\) choices for movie #\(k\text{.}\) Note that \(n-0, n-1, \ldots, n-(k-1)\) is a list of \(k\) rankings. Since steps multiply Theorem 2.2.3, there are
\begin{equation*} n(n-1)\ldots(n-(k-1)) \end{equation*}
ways to rank our top \(k\) movies. We can write this product in terms of factorials. There are
\begin{equation*} n(n-1)\ldots(n-(k-1)) = \frac{n(n-1)\ldots(n-(k-1))(n-k)\ldots(3)(2)(1)} {(n-k)\ldots(3)(2)(1)} = \frac{n!}{(n-k)!} \end{equation*}
ways to rank our top \(k\) movies.
On the other hand, we can first pick the \(k\) movies as a set in \(\binom{n}{k}\) ways and then rank these \(k\) movies in \(k(k-1)\ldots(3)(2)(1) = k!\) ways. Since steps multiply Theorem 2.2.3, there are
\begin{equation*} \binom{n}{k}k! \end{equation*}
ways to rank our top \(k\) movies.
Since we counted the same quantity in two different ways, it follows that
\begin{equation*} \frac{n!}{(n-k)!}=\binom{n}{k}k! \end{equation*}
Dividing each side of this equation by \(k!\) we get
\begin{equation*} \binom{n}{k} = \frac{n!}{k!(n-k)!} \end{equation*}
as desired.
This formula is primarily useful for theoretical examples.

Example 9.4.29 Using the explicit formula for binomial coefficients.

 
  1. Use the explicit formula for the binomial coefficients Theorem 9.4.27 to evaluate \(\binom{8}{4}\text{.}\)
    Solution.
    We have \(n=8\text{,}\) \(k=4\) and \(n-k=8-4=4\) and so
    \begin{equation*} \binom{8}{4} = \frac{8!}{4! 4!} = \frac{8\cdot 7 \cdot 6 \cdot 5 \cdot \cancel{4} \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}} {4 \cdot 3 \cdot 2 \cdot 1 \cdot \cancel{4} \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}} = \frac{\cancel{8}\cdot 7 \cdot 6 \cdot 5}{\cancel{4} \cdot 3 \cdot \cancel{2} \cdot 1} = \frac{7 \cdot 6 \cdot 5}{3} =7 \cdot 2 \cdot 5 =70 \end{equation*}
    Looking back at Example 9.4.11 we confirm \(\binom{8}{4}=70\text{.}\) Remember that the index begins at \(k=0\) so the 5th entry corresponds to \(k=4\text{.}\)
  2. Use the explicit formula for the binomial coefficients Theorem 9.4.27 to show that
    \begin{equation*} \binom{n}{2} = \frac{n(n-1)}{2}\text{.} \end{equation*}
    Solution.
    We have \(k=2\) and \(n-k = n-2\text{.}\) It is useful to note that
    \begin{equation*} n! = n(n-1)(n-2)(n-3) \cdots (3)(2)(1) = n(n-1)(n-2)! \end{equation*}
    Thus,
    \begin{equation*} \binom{n}{2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1)(n-2)!}{2(n-2)!} = \frac{n(n-1)\cancel{(n-2)!}}{2\cancel{(n-2)!}} = \frac{n(n-1)}{2}\text{.} \end{equation*}
  3. Use the explicit formula for the binomial coefficients Theorem 9.4.27 to prove algebraically that
    \begin{equation*} \binom{2n}{2} = 2\binom{n}{2} + n^2 \end{equation*}
    Solution.
    First,
    \begin{equation*} \displaystyle \binom{2n}{2} = \frac{(2n)!}{2!(2n-2)!} = \frac{(2n)(2n-1)\cancel{(2n-2)!}}{2\cancel{(2n-2)!}} =\frac{\cancel{2}n(2n-1)}{\cancel{2}} = n(2n-1) \end{equation*}
    Next, using (b) we have
    \begin{equation*} 2\binom{n}{2} + n^2 = \cancel{2} \frac{n(n-1)}{\cancel{2}} + n^2 = n(n-1)+ n^2 = n^2-n+n^2=2n^2-n = n(2n-1) \end{equation*}
    Since we got the same answer, it follows that \(\displaystyle \binom{2n}{2} = 2\binom{n}{2} + n^2\text{.}\)

Subsection 9.4.E Exercises

Subsubsection Exercises for 9.4.A The Arithmetic Triangle

1. Practice.

Use the arithmetic triangle from Figure 9.4.6 and the next row found in Example 9.4.11 to evaluate the following binomial coefficients:
\begin{equation*} \binom{8}{1}, \binom{7}{2}, \binom{4}{3}, \binom{4}{4}, \binom{2}{0}, \binom{5}{3}\text{.} \end{equation*}
Hint: If you are not sure where to look, consult Figure 9.4.5.
Check.
The answers, in some order, are \(1, 1, 4, 8, 10\text{,}\) and 21.

2. Practice.

 
  1. Draw the arithmetic triangle from Figure 9.4.6 and use Theorem 9.4.10 to continue the triangle through the row that begins with 1, 10.
  2. Use your answer to 2.(a) to evaluate the following binomial coefficients and circle the corresponding entries in the triangle.
    \begin{equation*} \binom{9}{4}, \binom{9}{7}, \binom{10}{4}, \binom{10}{5}\text{.} \end{equation*}
Check.
The answers, in some order, are \(36, 126, 210\text{,}\) and 252.

3. Understand.

Evaluate the first six terms of each sequence.
  1. \(\displaystyle a_n= \binom{n}{3}\) for \(n \ge 3\text{.}\)
  2. \(\displaystyle b_k = \binom{2k}{3}\) for \(k \ge 2\)
  3. \(\displaystyle c_m = \binom{m+4}{m}\) for \(m \ge 0\text{.}\)
Check.
  1. Hint: The second term is 4.
  2. Hint: The third term is 56.
  3. Hint: The fifth term is 126.

4. Understand.

Write a simple explicit rule that generates each sequence. Hint: Write each term as a binomial coefficient.
  1. The sequence \(a\) begins \(1, 3, 6, 10, 15, 21, \ldots\)
  2. The sequence \(b\) begins \(1, 4, 10, 20, 35, 56, \ldots\)
Check.
  1. Hint: The answer is of the form \(\binom{}{2}\) where the upper number depends on \(n\text{.}\)
  2. Hint: The answer is of the form \(\binom{}{3}\) where the upper number depends on \(n\text{.}\)

5. Recap.

Do you know …
  1. What the binomial coefficients count?
  2. How to create the first 7-10 rows of the arithmetic triangle using Theorem 9.4.10?
  3. Which row of the arithmetic triangle and which entry in that row to use to evaluate \(\binom{n}{k}\text{?}\)
  4. How to evaluate or model with sequences involving binomial coefficients?

6. Explore.

Write a simple explicit rule that generates each sequence. Hint: Write each term as a binomial coefficient.
  1. The sequence \(c\) begins \(1, 2, 6, 20, 70, \ldots\)
  2. The sequence \(d\) begins \(1, 15, 70, 210, \ldots\)

Subsubsection Exercises for 9.4.B Patterns in the Arithmetic Triangle

7. Practice.

  Use the arithmetic triangle to evaluate each sum.
  1. \(\displaystyle \displaystyle \sum_{k=0}^4\binom{4}{k}^2\)
  2. \(\displaystyle \displaystyle \sum_{k=0}^4k\binom{4}{k}\)
  3. \(\displaystyle \displaystyle \sum_{k=0}^4k\binom{4}{k}^2\)
Check.
The answers, in some order, are 32, 70, and 140.

8. Understand.

 
  1. Check that \(\displaystyle 7\mid \binom{7}{k}\) for \(0 \lt k \lt 7\text{.}\)
  2. Does \(\displaystyle 3\mid \binom{3}{k}\) for \(0 \lt k \lt 3\text{?}\) Justify your answer.
  3. Does \(\displaystyle 4\mid \binom{4}{k}\) for \(0 \lt k \lt 4\text{?}\) Justify your answer.
  4. Does \(\displaystyle 5\mid \binom{5}{k}\) for \(0 \lt k \lt 5\text{?}\) Justify your answer.
  5. Which integers \(n\) have \(\displaystyle n \mid \binom{n}{k}\) for all \(0 \lt k \lt n\text{?}\)
Check.
  1. Check \(7 \mid 7\text{,}\) \(7 \mid 21\text{,}\) and \(7 \mid 35\text{.}\)
  2. Hint: Yes
  3. Hint: No
  4. Hint: Yes
  5. Hint: What do 3, 5, and 7 have in common? What other integers does it work for?

9. Understand.

 
  1. Calculate the first four partial sums of \(\displaystyle \sum_{k=0}^n\binom{n}{k}^2\text{.}\) Caution: Since the terms we are adding depend on \(n\text{,}\) you need to find each partial sum on its own. You cannot using the previous partial sum.
  2. Make a conjecture about an explicit formula for the sum \(\displaystyle \sum_{k=0}^n\binom{n}{k}^2\text{.}\)
Check.
  1. Hint: The third partial sum is 6.
  2. Hint: The answer is a binomial coefficient.

10. Understand.

 
  1. Calculate the first four partial sums of \(\displaystyle \sum_{k=0}^nk\binom{n}{k}\text{.}\) Caution: Since the terms we are adding depend on \(n\text{,}\) you need to find each partial sum on its own. You cannot using the previous partial sum.
  2. Make a conjecture about an explicit formula for the sum \(\displaystyle \sum_{k=0}^nk\binom{n}{k}\text{.}\) Hint: Factor \(n\) to see the pattern.
Check.
  1. Hint: The fourth partial sum is 12.
  2. Hint: It involves a power of two, but not \(2^n\text{.}\)

11. Understand.

 
  1. Calculate the first four partial sums of \(\displaystyle \sum_{k=0}^nk\binom{n}{k}^2\text{.}\) Caution: Since the terms we are adding depend on \(n\text{,}\) you need to find each partial sum on its own. You cannot using the previous partial sum.
  2. Make a conjecture about an explicit formula for the sum \(\displaystyle \sum_{k=0}^nk\binom{n}{k}^2\text{.}\) Hint: Factor \(n\) to see the pattern.

12. Recap.

Do you know …
  1. Why the arithmetic triangle has left-right symmetry?
  2. How to evaluate sums involving binomial coefficients?
  3. How to use partial sums to conjecture an explicit formula for a sum?
  4. What the sum of the entries of a row of the arithmetic triangle equals?

13. Explore.

The Fibonacci numbers appear as the sum of integers in the arithmetic triangle. Find them and express your answer as \(F_n=\) a sum involving binomial coefficients. Hint: Look at an angle.

Subsubsection Exercises for 9.4.C The Binomial Theorem

14. Practice.

In Activity 9.4.C, we found that \((n+1)^3=n^3+3n^2+3n+1\text{.}\)
  1. Expand and simplify \((n+1)^4\text{.}\) Hint:
    \begin{equation*} (n+1)^4=(n+1)(n+1)^3=(n+1)(n^3+3n^2+3n+1)\text{.} \end{equation*}
  2. The coefficients of your answer are in a row of the arithmetic triangle. Which row?
Check.
Hint: The answer is in Activity 9.4.C. Make sure you show work.

16. Understand.

Use the Binomial Theorem to prove
\begin{equation*} \sum_{k=0}^n \binom{n}{k} = 2^n \end{equation*}
for \(n \ge 0\text{.}\) Hint: Expand \((1+1)^n\text{.}\)
Check.
Hint: \(1+1 = 2\) and \(1^k=1\text{.}\)

17. Understand.

Use the Binomial Theorem to find an explicit formula for \(\displaystyle \sum_{k=0}^n 2^k\binom{n}{k}\) for \(n \ge 0\text{.}\) Hint: Expand \((1+2)^n\text{.}\)
Check.
Hint: \(1+2=3\text{.}\)

19. Recap.

Do you know …
  1. What the binomial theorem says?
  2. How to use the binomial theorem to expand expressions such as \((n+1)^4\) or \((n-1)^4\) without multiplying out by hand?
  3. How to use the binomial theorem to prove explicit formulas for sums involving binomial coefficients?

20. Explore.

If you have completed Exercise 18, then you may use those answers here. For each function, evaluate and simplify the difference quotient
\begin{equation*} \frac{f(x+h)-f(x)}{h} \end{equation*}
so that there are no fractions. Next, evaluate your answer when \(h=0\text{.}\) Your final answer should be an expression involving \(x\text{.}\)
  1. \(f: \mathbb{R} \to \mathbb{R}\) defined by \(f(x) = x^2\text{.}\)    Hint: Your work should begin
    \begin{equation*} \frac{f(x+h)-f(x)}{h}=\frac{(x+h)^2-(x)^2}{h}= \end{equation*}
  2. \(f: \mathbb{R} \to \mathbb{R}\) defined by \(f(x) = x^3\text{.}\)
  3. \(f: \mathbb{R} \to \mathbb{R}\) defined by \(f(x) = x^4\text{.}\)
  4. For readers who have studied calculus, explain why these answers are correct.

Subsubsection Exercises for 9.4.D Explicit Formula for Binomial Coefficients

21. Practice.

Use Theorem 9.4.27 to evaluate each binomial coefficient by hand. Show work. You may use computational technology to check.
  1. \(\displaystyle \binom{12}{3}\)
  2. \(\displaystyle \binom{12}{4}\)
Check.
  1. Hint: The number is just over 200.
  2. Hint: The answer is just less than 500.

24. Understand.

Write a combinatorial proof of Theorem 9.4.14 using Theorem 2.3.13:
\begin{equation*} \binom{n}{k} = \binom{n}{n-k}\text{.} \end{equation*}
Hint: Out of a group of \(n\) people, pick a group of \(k\) people. A less direct way to pick the group is to say who is not in the group.

25. Recap.

Do you know …
  1. What the explicit formula for \(\binom{n}{k}\) is?
  2. How to use the explicit formula to evaluate \(\binom{n}{k}\) for small values of \(n\) and \(k\text{.}\)
  3. What the steps are in a combinatorial proof Theorem 2.3.13?

26. Explore.

Write a combinatorial proof of Theorem 9.4.10 using Theorem 2.3.13:
\begin{equation*} \binom{n}{k} = \binom{n-1}{k-1} + \binom{n}{k}\text{.} \end{equation*}
Hint: How many \(k\)-elements subsets does the set \(\{1,2,\ldots,n\}\) have? For a less direct count, consider cases based on whether or not \(n\) is in the subset.
Check.
Hints: Make sure you follow the proof format. You can use the hint to write the story. First, explain why the answer is \(\binom{n}{k}\text{.}\) Next, follow the hint to break it into cases. Explain why one case gives \(\binom{n-1}{k-1}\) and why the other case gives \(\binom{n-1}{k}\text{.}\)

27. Explore.

Use Theorem 9.4.27 to prove each identity algebraically.
  1. \(\displaystyle \displaystyle (n-m)\binom{n}{m} = n \binom{n-1}{m}\)
  2. \(\displaystyle \displaystyle \binom{n}{m}\binom{m}{2}=\binom{n}{2}\binom{n-2}{m-2}\)
PrevTopNext