Binomial identities

Section 9.2 Binomial identities

Now convinced that the binomial coefficient \({{n}\choose{r}}\) counts the number of bit strings with a fixed number of ones (equivalently: subsets of a fixed size), we may draw several helpful conclusions. These binomial identities are theorems about binomial coefficients. Perhaps most significantly, we will learn why we call them “binomial coefficients.”

Our first two theorems come directly from the example in the last section.

Theorem 9.2.1.

Let \(n \in \mathbf{N}\text{,}\) then

\begin{equation*} {{n}\choose{0}} = {{n}\choose{n}} = 1. \end{equation*}

Proof.

There is just one \(n\)-digit bit string with all zeros (or all ones).

Theorem 9.2.2.

Let \(n \in \mathbf{N}\) and \(0 \le r \le n\text{.}\) Then,

\begin{equation*} {{n}\choose{r}} = {{n}\choose{n-r}}. \end{equation*}

Proof.

The bit string with \(n\) digits and exactly \(r\) ones corresponds to the bit string with exactly \(r\) zeros in the following way: swap all the zeros with ones and vice-versa. So, there are the same number of each. However, a bit string with \(r\) zeros has \(n-r\) ones. Therefore, the number of bit strings with \(r\) ones is the same as the number of bit strings with \(n-r\) ones.

Our next theorem is an extremely important recurrence relation on the binomial coefficients. The theorem is typically attributed to the 17th century French mathematician Blaise Pascal. However, it was known much earlier to Islamic, Chinese, and Indian mathematicians, including Pingala, the Indian mathematician who used binomial coefficients to study poetic meter. It is a recurring problem in mathematics that white Europeans are credited with ideas they did not invent. Therefore, we will call this the recurrence relation for the binomial coefficients. (It is also just more descriptive not to name things after people.)

Theorem 9.2.3. The binomial coefficient recurrence relation.

Suppose that \(n \in \mathbf{N}\text{,}\) \(n \ge 1\text{,}\) and \(1 \le r \le n\text{.}\) Then,

\begin{equation*} {{n}\choose{r}} = {{n-1}\choose{r-1}} + {{n-1}\choose{r}}. \end{equation*}

Proof.

As you know, there are \({{n}\choose{r}}\) bit strings of length \(n\) with exactly \(r\) ones. We claim that there are also

\begin{equation*} {{n-1}\choose{r-1}}+{{n-1}\choose{r}} \end{equation*}

such strings. If we can prove this claim, then the two numbers must be equal.

Suppose we would like to make a bit string of length \(n\) with exactly \(r\) ones. We must make a choice for the first digit of the string.

If we choose a one to be the first digit of the string, then the remaining \(n-1\) characters must have \(r-1\) ones. There are \({{n-1}\choose{r-1}}\) ways to make this choice. (Note that we are constructing a \(n\)-digit string recursively by writing down a one and then writing down a \((n-1)\)-digit string.)

Likewise, if we choose a zero to be the first digit of the string, then the remaining \(n-1\) characters must have \(r\) ones. There are \({{n-1}\choose{r}}\) ways to make this choice.

Our first digit must be 0 or 1 and cannot be both, so there are

\begin{equation*} {{n-1}\choose{r-1}}+{{n-1}\choose{r}} \end{equation*}

total choices by the addition principle. Therefore,

\begin{equation*} {{n}\choose{r}} = {{n-1}\choose{r-1}} + {{n-1}\choose{r}}. \end{equation*}

That proof is a little abstract, but the great news is that we can easily write down a few bit strings to see it in action. This is the reason for the choice to pass everything to bit strings in the last section.

Example 9.2.4.

Recall that there are exactly \({{5}\choose{2}}=10\) bit strings with five digits and two ones.

Observe that \({{4}\choose{1}}=4\) of these strings begin with a one: \(11000\text{,}\) \(10100\text{,}\) \(10010\text{,}\) and \(10001\text{.}\) Once we fix the first digit, we are left to write down a four digit string with a single one.

Next, notice that \({{4}\choose{2}}=6\) of these strings begin with a zero: \(01100\text{,}\) \(01010\text{,}\) \(01001\text{,}\) \(00110\text{,}\) \(00101\text{,}\) and \(00011\text{,}\) because we must find a four digit string with two ones after fixing the first zero.

Therefore,

\begin{equation*} {{5}\choose{2}} = {{4}\choose{1}} + {{4}\choose{2}}. \end{equation*}

This recurrence relation suggests a helpful visual representation of the binomial coefficients. For reasons explained above, we will call it the binomial triangle instead of giving it anyone's name.

The \(r\)-th value in the \(n\)-th row of the triangle is \({{n}\choose{r}}\text{,}\) and the tip of the triangle corresponds to the row \(n=0\text{.}\) By the first theorem, the sides of the triangle will all be equal to \(1\text{;}\) by the recurrence relation, any interior number will be the sum of the two above it.

\begin{equation*} 1 \end{equation*}

\begin{equation*} 1 \; \; 1 \end{equation*}

\begin{equation*} 1 \; \; 2 \; \; 1 \end{equation*}

\begin{equation*} 1 \; \; 3 \; \; 3 \; \; 1 \end{equation*}

\begin{equation*} 1 \; \; 4 \; \; 6 \; \; 4 \; \; 1 \end{equation*}

\begin{equation*} 1 \, \; 5 \; 10 \; 10 \; 5 \; \, 1 \end{equation*}

\begin{equation*} 1 \; 6 \; 15 \; 20 \; 15 \; 6 \; 1 \end{equation*}

Above, we have represented the binomial coefficients \({{n}\choose{r}}\) from \(n=0\) to \(n=6\text{.}\) For example, the second element in the fifth row is \(10\text{,}\) which is \({{5}\choose{2}}\text{.}\) We could continue the pattern for higher values of \(n\) if needed.

When we need a single value of \({{n}\choose{r}}\text{,}\) we can use the formula we developed in the last chapter. However, when we need many values at once, the triangle is convenient.

“Wait,” you say. “When will we need many values at once?”

Example 9.2.5.

What is \((x+y)^2\) expanded and simplified?

Depending on your comfort with algebra, you may quickly or slowly be able to work out that

\begin{equation*} (x+y)^2 = x^2 + 2xy + y^2. \end{equation*}

How about \((x+y)^3\text{?}\) This one is a little worse, but we can use the distributive property to expand the expression.

\begin{align*} (x+y)^3 \amp = (x+y)(x+y)(x+y)\\ \amp = xxx + xxy + xyx + yxx + xyy + yxy + yyx + yyy\\ \amp = x^3 + 3x^2y + 3xy^2 + y^3. \end{align*}

Let us be explicit about how this expression is expanded. For each of the \(n=3\) factors of the polynomial, we choose a number \(r\) of the factors to contribute a \(y\) and \(n-r\) of the factors to contribute an \(x\text{.}\) The eight resulting strings, such as \(xxy\) and \(yxx\text{,}\) are combinatorially identical to their binary counterparts \(001\) and \(100\text{.}\) Therefore there are \({{3}\choose{1}}=3\) ways to choose a single \(y\text{,}\) and because of the rules of real number algebra all three of these strings get combined into \(3x^2y\text{.}\)

It is no surprise then that the coefficients \(1, 3, 3, 1\) are exactly the third row of the binomial triangle.

To conclude the example, convince yourself that

\begin{equation*} (x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4. \end{equation*}

The expression \(x+y\) is called a binomial. Now we will see why we call these numbers “binomial coefficients.”

Theorem 9.2.6. The binomial theorem.

Let \(x\) and \(y\) be any numbers and let \(n \in \mathbf{N}\text{.}\) Then,

\begin{equation*} (x+y)^n = \sum_{r=0}^n {{n}\choose{r}} x^{n-r}y^r. \end{equation*}

Proof.

When we expand the polynomial \((x+y)^n\) the result is a sum of terms that each contain \(n\) factors, \(r\) of which are \(y\) and \(n-r\) of which are \(x\text{.}\) Upon simplifying the polynomial, such a string reduces to the form \(x^{n-r}y^r\text{.}\) The coefficient of each term is the number of those strings.

Fix such a string reducing to \(x^{n-r}y^r\text{.}\) Then, there exists one and only one bit string of length \(n\) with \(r\) ones and \(n-r\) zeros by writing a one wherever there is a \(y\) in the string and writing a zero wherever there is a \(x\text{.}\) There are \({{n}\choose{r}}\) such bit strings, and hence the coefficient of \(x^{n-r}y^r\) must be \({{n}\choose{r}}\text{.}\)

In the example from the last section we got the sense that the sum of the binomial coefficients across a fixed row should equal \(2^n\text{.}\) We could prove this combinatorially, by proving that

\begin{equation*} \sum_{r=0}^n {{n}\choose{r}} \end{equation*}

and \(2^n\) count the same number of objects (bit strings or subsets). On the other hand, the binomial theorem provides us with a powerful way to prove this fact shockingly quickly.

Theorem 9.2.7.

For all \(n \in \mathbf{N}\text{,}\)

\begin{equation*} \sum_{r=0}^n {{n}\choose{r}} = 2^n. \end{equation*}

Proof.

Per the binomial theorem,

\begin{equation*} \sum_{r=0}^n {{n}\choose{r}} x^{n-r}y^r = (x+y)^n \end{equation*}

for any choice of numbers \(x\) and \(y\text{.}\) So, choose \(x=y=1\text{.}\) Then,

\begin{equation*} \sum_{r=0}^n {{n}\choose{r}} 1^{n-r}1^r = (1+1)^n. \end{equation*}

The left side of the equation is

\begin{equation*} \sum_{r=0}^n {{n}\choose{r}} \end{equation*}

and the right side is \(2^n\text{.}\) Thus the proof is complete.

We may use the binomial theorem to prove a variety of identities involving sums of binomial coefficients by making judicious choices for \(x\) and \(y\text{.}\)