Sums of Binomial Coefficients

On the Binomial Coefficient Identities page we proved that if $n$ and $k$ are nonnegative integers such that $0 \leq k \leq n$ then the following identities hold for the binomial coefficient $\binom{n}{k}$:

• $\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$

We will now look at some useful equalities of various sums of the binomial coefficients.

Theorem 1: If $n$ and $k$ and nonnegative integers that satisfy $0 \leq k \leq n$ then $\displaystyle{\sum_{k=0}^{n} k \cdot \binom{n}{k} = 0 \cdot \binom{n}{0} + 1 \cdot \binom{n}{1} + ... + n \cdot \binom{n}{n} = n \cdot 2^{n-1}}$.

• Proof: We start by noticing that for $k = 0$ we get $k \cdot \binom{n}{k} = 0 \cdot \binom{n}{0} = 0$. Therefore $\sum_{k=0}^{n} k \cdot \binom{n}{k} = \sum_{k=1}^{n} k \cdot \binom{n}{k}$. We then apply the identity $\binom{n}{k} = \frac{n}{k} \cdot \binom{n-1}{k-1}$ and the identity that $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ to get:

(1)

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

Theorem 2: If $n$ and $k$ are nonnegative integers that satisfy $0 \leq k \leq n$ then $\sum_{j=0}^{n} \binom{j}{k} = \binom{n+1}{k+1}$.

Note that $\sum_{j=0}^{n} \binom{j}{k} = \sum_{j=1}^{n} \binom{j}{k}$ since $\binom{0}{k} = 0$.

• Proof: We apply Pascal's identity to the binomial coefficient $\binom{j+1}{k+1}$ to get that:

(2)

\begin{align} \quad \binom{j+1}{k+1} = \binom{j}{k} + \binom{j}{k+1} \\ \quad \binom{j}{k} = \binom{j+1}{k+1} - \binom{j}{k+1} \end{align}

• Substituting this into the series $\sum_{j=0}^{n} \binom{j}{k}$ gives us:

(3)

\begin{align} \quad \sum_{j=0}^{n} \binom{j}{k} = \sum_{j=0}^{n} \left ( \binom{j+1}{k+1} - \binom{j}{k+1} \right ) = \left ( \binom{1}{k+1} - \binom{0}{k+1} \right ) + \left ( \binom{2}{k+1} - \binom{1}{k+1}\right ) + ... + \left ( \binom{n+1}{k+1} - \binom{n}{k+1} \right ) \end{align}

• The series above is a finite telescoping series where many of the intermediary terms cancel out. We therefore get:

(4)

\begin{align} \quad \sum_{j=0}^{n} \binom{j}{k} = \binom{n+1}{k+1} - \binom{0}{k+1} = \binom{n+1}{k+1} \quad \blacksquare \end{align}

Theorem 2 establishes an important relationship for numbers on Pascal's triangle. In particular, we can determine the sum of binomial coefficients of a vertical column on Pascal's triangle to be the binomial coefficient that is one down and one to the right as illustrated in the following diagram:

In the image above, we have that $n$ varies from $0$ to $5$ and $k = 1$ so by applying Theorem 2 we see that:

(5)

\begin{align} \quad \sum_{j=0}^{5} \binom{j}{1} = \binom{0}{1} + \binom{1}{1} + \binom{2}{1} + \binom{3}{1} + \binom{4}{1} + \binom{5}{1} = \binom{6}{2} \end{align}

One useful application of Theorem 2 is that the column $k = 2$ of Pascal's triangle gives us the sums of positive integers as we prove in the following corollary.

Corollary 1: For all positive integers $n$, $\sum_{j=1}^{n} j = \binom{n+1}{2}$.

• Proof: By setting $k = 1$ in Theorem 2 we get:

(6)

\begin{align} \quad \sum_{j=0}^{n} \binom{j}{1} = \sum_{j=1}^{n} \binom{j}{1} = \binom{1}{1} + \binom{2}{1} + ... + \binom{n}{1} = 1 + 2 + ... + n = \sum_{j=1}^{n} j = \binom{n+1}{2} \quad \blacksquare \end{align}