# Sum of Binomial Coefficients over Upper Index

## Theorem

Let $m \in \Z$ be an integer such that $m \ge 0$.

Then:

 $\displaystyle \sum_{j \mathop = 0}^n \binom j m$ $=$ $\displaystyle \binom {n + 1} {m + 1}$ $\displaystyle$ $=$ $\displaystyle \dbinom 0 m + \dbinom 1 m + \dbinom 2 m + \cdots + \dbinom n m = \dbinom {n + 1} {m + 1}$

where $\displaystyle \binom j m$ denotes a binomial coefficient.

## Proof 1

Proof by induction:

For all $n \in \N$, let $\map P n$ be the proposition:

$\displaystyle \sum_{k \mathop = 0}^n \binom k m = \binom {n + 1} {m + 1}$

### Basis for the Induction

$\map P 0$ says:

$\dbinom 0 m = \dbinom 1 {m + 1}$

When $m = 0$ we have by definition:

$\dbinom 0 0 = 1 = \dbinom 1 1$

When $m > 0$ we also have by definition:

$\dbinom 0 m = 0 = \dbinom 1 {m + 1}$

This is our basis for the induction.

### Induction Hypothesis

Now we need to show that, if $\map P r$ is true, where $r \ge 0$, then it logically follows that $\map P {r + 1}$ is true.

So this is our induction hypothesis:

$\displaystyle \sum_{k \mathop = 0}^r \binom k m = \binom {r + 1} {m + 1}$

Then we need to show:

$\displaystyle \sum_{k \mathop = 0}^{r + 1} \binom k m = \binom {r + 2} {m + 1}$

### Induction Step

This is our induction step:

 $\displaystyle \sum_{k \mathop = 0}^{r + 1} \binom k m$ $=$ $\displaystyle \sum_{k \mathop = 0}^r \binom k m + \binom {r + 1} m$ $\displaystyle$ $=$ $\displaystyle \binom {r + 1} {m + 1} + \binom {r + 1} m$ Induction Hypothesis $\displaystyle$ $=$ $\displaystyle \binom {r + 2} {m + 1}$ Pascal's Rule

So $\map P r \implies \map P {r + 1}$ and the result follows by the Principle of Mathematical Induction.

Therefore:

$\displaystyle \forall m, n \in \Z, m \ge 0, n \ge 0: \sum_{k \mathop = 0}^n \binom k m = \binom {n + 1} {m + 1}$

$\blacksquare$

## Proof 2

 $\displaystyle \sum_{0 \mathop \le j \mathop \le n} \binom j m$ $=$ $\displaystyle \sum_{0 \mathop \le m + j \mathop \le n} \binom {m + j} m$ Translation of Index Variable of Summation $\displaystyle$ $=$ $\displaystyle \sum_{-m \mathop \le j \mathop < 0} \binom {m + j} m + \sum_{0 \mathop \le j \mathop \le n - m} \binom {m + j} m$ $\displaystyle$ $=$ $\displaystyle 0 + \sum_{0 \mathop \le \mathop j \mathop \le n - m} \binom {m + j} m$ Definition of Binomial Coefficient: negative lower index $\displaystyle$ $=$ $\displaystyle \binom {m + \left({n - m}\right) + 1} {m + 1}$ Rising Sum of Binomial Coefficients $\displaystyle$ $=$ $\displaystyle \binom {n + 1} {m + 1}$

$\blacksquare$