Binomial Coefficients

We will now look more into binomial coefficients which we will formally define.

Definition: If $n$ and $k$ are nonnegative integers that satisfy $0 \leq k \leq n$ then the Binomial Coefficient $\binom{n}{k}$ read as "$n$ choose $k$" is defined to be $\binom{n}{k} = \frac{n!}{k! (n - k)!}$.

On the Binomial Coefficient Identities page we will prove the following identities to the binomial coefficients:

• $\displaystyle{\binom{n}{k} = \frac{n^{\underline{k}}}{k!}}$.

• $\displaystyle{\binom{n}{k} = \binom{n}{n-k}}$.

• $\displaystyle{\binom{n}{k} = \frac{n}{k} \cdot \binom{n-1}{k-1}}$, $k \geq 1$

For now, we will look primarily at the somewhat symmetric properties of the binomial coefficients. For a fixed nonnegative integer $n$, consider the finite sequence of binomial coefficients:

(1)

\begin{align} \quad \left ( \binom{n}{0}, \binom{n}{1}, ..., \binom{n}{n-1}, \binom{n}{n} \right ) \end{align}

One interesting property of this sequence of binomial coefficients is that it is unimodal, that is this finite sequence of real numbers first increases and then decreases at the halfway point to form a single peak. For example, if $n = 6$ then the finite sequence of corresponding binomial coefficients is:

(2)

\begin{align} \quad \left ( \binom{6}{0}, \binom{6}{1}, \binom{6}{2}, ..., \binom{6}{5}, \binom{6}{6} \right ) = \left (1, 6, 15, 20, 15, 6, 1 \right ) \end{align}

The graph of the seven terms of this finite sequence is given below with a horizontal $k$ axis and a vertical $\binom{6}{k}$ axis.

We will now prove that every sequence of binomial coefficients $\binom{n}{k}$ is unimodal.

Theorem 1: For $n$ and $k$ as nonnegative integers satisfying $0 \leq k \leq n$ we have that the finite sequence of binomial coefficients $\left ( \binom{n}{0}, \binom{n}{1}, ..., \binom{n}{n-1}, \binom{n}{n} \right )$ is unimodal.

• Since for each nonnegative integer $n$ we use the identity $\binom{n}{k} = \binom{n}{n-k}$ for $0 \leq k \leq n$ gives us symmetry in the middle of each finite sequence of binomial coefficients $\binom{n}{k}$ then we only need to show that the subsequence of the first half terms is increasing. The symmetry we have already proved then implies that the second half of the terms in the full sequence is decreasing.

• For $k = 0, 1, 2, ..., n - 1$ consider the ratio:

(3)

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

• Consider when $R < 1$. We will equivalently have $\binom{n}{k} < \binom{n}{k+1}$ which implies $k < n - k$, that is $2k < n$ i.e., $k < \frac{n}{2}$. In other words, when $k < \frac{n}{2}$ we have that $\binom{n}{k} < \binom{n}{k+1}$ so the finite sequence of the first $\frac{n}{2}$ terms are increasing (if $n$ is even) or the first $\frac{n-1}{2}$ terms are increasing (if $n$ is odd) which completes our proof. $\blacksquare$