# 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:

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:

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

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

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)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: