Binomial Coefficient Identities

Recall from the Binomial Coefficients page that the binomial coefficient $\binom{n}{k}$ for nonnegative integers $n$ and $k$ that satisfy $0 \leq k \leq n$ is defined to be:

(1)

\begin{align} \quad \binom{n}{k} = \frac{n!}{k!(n-k)!} \end{align}

We will now look at some rather useful identities regarding the binomial coefficients.

Theorem 1: If $n$ and $k$ are nonnegative integers that satisfy $0 \leq k \leq n$ then $\displaystyle{\binom{n}{k} = \frac{n^{\underline{k}}}{k!}}$.

Recall that $n^{\underline{k}}$ represents a falling factorial.

• Proof: We simplify the lefthand side of the equation to get:

(2)

\begin{align} \quad \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n \cdot (n - 1) \cdot ... \cdot 2 \cdot 1}{k! \cdot (n - k) \cdot (n - k - 1) \cdot ... \cdot 2 \cdot 1} = \frac{n \cdot (n - 1) \cdot ... \cdot (n - k + 1)}{k!} = \frac{n^{\underline{k}}}{k!} \quad \blacksquare \end{align}

Theorem 2: If $n$ and $k$ are nonnegative integers that satisfy $0 \leq k \leq n$ then $\displaystyle{\binom{n}{k} = \binom{n}{n-k}}$.

We will prove Theorem 2 in two different ways. The first proof will be a purely algebraic one while the second proof will use combinatorial reasoning.

• Proof 1: This time we simplifying the righthand side of the equation to get:

(3)

\begin{align} \quad \binom{n}{n-k} = \frac{n!}{(n-k)!((n - (n-k))!} = \frac{n!}{k!(n-k)!} = \binom{n}{k} \quad \blacksquare \end{align}

• Proof 2: The binomial coefficient $\binom{n}{k}$ tells us the number of ways to choose $k$ objects from $n$ objects total, while the binomial coefficient $\binom{n}{n - k}$ tells us the number of ways to NOT choose $k$ objects (and hence choose $n - k$ of the remaining objects) from the $n$ objects total. The number of ways that both tasks can be done should be equal and so $\binom{n}{k} = \binom{n}{n-k}$. $\blacksquare$

Theorem 3: If $n$ and $k$ are nonnegative integers that satisfy $1 \leq k \leq n$ then $\displaystyle{\binom{n}{k} = \frac{n}{k} \cdot \binom{n-1}{k-1}}$.

Once again we will prove Theorem 3 in two different ways like before.

• Proof 1: We manipulate the lefthand side of the equation above to get:

(4)

\begin{align} \quad \binom{n}{k} = \frac{n!}{k!(n - k)!} = \frac{n}{k} \cdot \frac{(n - 1)!}{(k - 1)! \cdot (n - k)!} = \frac{n}{k} \cdot \frac{(n - 1) \cdot (n - 2) \cdot ... \cdot 2 \cdot 1}{(k - 1)! \cdot (n - k) \cdot (n - k - 1) \cdot ... \cdot 2 \cdot 1} \\ = \frac{n}{k} \cdot \frac{(n-1) \cdot (n - 2 \cdot) ... \cdot (n - k + 1)}{(k-1)!} = \frac{n}{k} \cdot \frac{(n - 1)^{\underline{k-1}}}{(k - 1)!} \end{align}

• We apply Theorem 1 and see that $\frac{(n - 1)^{\underline{k-1}}}{(k - 1)!} = \binom{n - 1}{k - 1}$. Therefore:

(5)

\begin{align} \quad \binom{n}{k} = \frac{n}{k} \cdot \binom{n-1}{k-1} \quad \blacksquare \end{align}

• Proof 2: Consider the number $\binom{n}{k} \cdot k$. This number combinatorially says that out of $n$ objects we choose $k$ and then choose a specific $k$ out of our choices. Now consider the number $n \cdot \binom{n-1}{k-1}$. This number combinatorially says that we choose any of the $n$ objects and out of the remaining $n - 1$ objects we choose $k - 1$. The number of ways in which these objects can be chosen are equal and therefore:

(6)

\begin{align} \quad \binom{n}{k} \cdot k = n \cdot \binom{n-1}{k-1} \\ \quad \binom{n}{k} = \frac{n}{k} \cdot \binom{n-1}{k-1} \quad \blacksquare \end{align}