Chapter 20 Binomial Theorem
Exercises Practice Problems
1. Nested Sets.
In this problem, you will prove the following identity in two different ways
Prove this equation using the binomial theorem. Solution.
Take \(x=2\) and \(y=1\) to get
\begin{equation*} (2+1)^n = \sum_{k=0}^n { n \choose k} 2^k \end{equation*}-
Give a combinatorial proof of this equation by showing that each side counts the number of ways to choose sets \(A,B\) where \(\emptyset \subseteq A \subseteq B \subseteq [n]\text{.}\)
The left hand side is \(3^n\text{.}\) Explain why there are three choices for where to place every element of \([n]\text{.}\) Solution.
For each of the \(n\) elements, there are three possible places it can go: \(A\text{,}\) \(B \backslash A\) or \(\overline{B}\text{.}\) We must make this choice a total on \(n\) times, so the number of ways to do this is \(3^n\) by the product principle.
The right hand is \(\sum_{k=0}^n 2^k { n \choose k}.\) This time, we create the sets \(A \subseteq B\) in a different way. Namely, first we decide what the size of \(B\) will be, and use \(k\) to denote this size. With this in mind, interpret the right hand side of this equation. Solution.
Here is the recipe.
First, choose a value for \(k\) where \(0 \leq k \leq n\text{.}\)
Next, choose the \(k\) elements in \(B\text{.}\)
Finally, choose a subset \(A\) of the \(k\)-set \(B\)
The summation sign (addition principle) considers all possible choices for the size \(k\text{.}\) Once we have determined \(k\text{,}\) there are \({n \choose k}\) ways to pick the subset \(B\text{.}\) Then there are \(2^k\) ways to choose the subset \(A \subset B\text{.}\)
2. Rectangles Galore.
The following \(2 \times 2\) grid contains 9 rectangles (many of them are squares). Draw them all.
Solution.
Prove that an \(m \times n\) grid contains \({m+1 \choose 2}{n+1 \choose 2}\) rectangles. Solution.
Creating a rectangle requires choosing two vertical lines (to be the left and right boundaries) and two horizontal lines (to be the upper and lower boundaries). There are a total of \(n+1\) vertical lines and \(m+1\) horizontal lines. Therefore the total number of rectangles is \({m+1 \choose 2}{n+1 \choose 2}\text{.}\)
3. Diagonals in an \(n\)-gon.
Consider a convex \(n\)-gon with its vertices labeled by the elements of \([n]\text{.}\)
How many distinct diagonals are are there? Solution.
In order to create a diagonal, we must chose two vertices that are not adjacent. We have \(n\) choices for our first vertex, and then \(n-3\) choices for our second vertex (since we cannot re-pick our vertex, or choose one of its two neighbors. The order that we pick these vertices does not matter, so we must divide by 2. The answer is
\begin{equation*} \frac{n(n-3)}{2}. \end{equation*}How may pairs of crossing diagonals are there? Solution.
The answer is
\begin{equation*} { n \choose 4}. \end{equation*}Once you have picked 4 vertices, there is a unique way to draw a pair of crossing diagonals between them.