# Sum of Binomial Coefficients over Upper Index

From ProofWiki

## Theorem

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

Then:

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

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

That is:

- $\displaystyle \binom 0 m + \binom 1 m + \binom 2 m + \cdots + \binom n m = \binom {n+1} {m+1}$

## Proof

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \sum_{0 \mathop \le j \mathop \le n} \binom j m\) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \sum_{0 \mathop \le m + j \mathop \le n} \binom {m + j} m\) | \(\displaystyle \) | \(\displaystyle \) | Permutation of Indices | ||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\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 \) | |||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle 0 + \sum_{0 \mathop \le \mathop j \mathop \le n - m} \binom {m + j} m\) | \(\displaystyle \) | \(\displaystyle \) | Definition of binomial coefficient: negative lower index | ||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \binom {m + \left({n - m}\right) + 1} {m + 1}\) | \(\displaystyle \) | \(\displaystyle \) | Rising Sum of Binomial Coefficients | ||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \binom {n + 1} {m + 1}\) | \(\displaystyle \) | \(\displaystyle \) |

$\blacksquare$

## Sources

- Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(1968): $\S 1.2.6 \ \text{E}$ - Larry C. Andrews:
*Special Functions of Mathematics for Engineers*(1992)... (previous)... (next): $\S 1.2.4$: Factorials and binomial coefficients: $1.34$