Sum of Binomial Coefficients over Upper Index

From ProofWiki
Jump to: navigation, search

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:

$\dbinom 0 m + \dbinom 1 m + \dbinom 2 m + \cdots + \dbinom n m = \dbinom {n + 1} {m + 1}$


Proof

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

$\blacksquare$


Sources