Sum of Binomial Coefficients over Upper Index/Proof 2
Jump to navigation
Jump to search
Theorem
\(\ds \sum_{j \mathop = 0}^n \binom j m\) | \(=\) | \(\ds \binom {n + 1} {m + 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dbinom 0 m + \dbinom 1 m + \dbinom 2 m + \cdots + \dbinom n m = \dbinom {n + 1} {m + 1}\) |
Proof
\(\ds \sum_{0 \mathop \le j \mathop \le n} \binom j m\) | \(=\) | \(\ds \sum_{0 \mathop \le m + j \mathop \le n} \binom {m + j} m\) | Translation of Index Variable of Summation | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{-m \mathop \le j \mathop < 0} \binom {m + j} m + \sum_{0 \mathop \le j \mathop \le n - m} \binom {m + j} m\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 0 + \sum_{0 \mathop \le \mathop j \mathop \le n - m} \binom {m + j} m\) | Definition of Binomial Coefficient: negative lower index | |||||||||||
\(\ds \) | \(=\) | \(\ds \binom {m + \left({n - m}\right) + 1} {m + 1}\) | Rising Sum of Binomial Coefficients | |||||||||||
\(\ds \) | \(=\) | \(\ds \binom {n + 1} {m + 1}\) |
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: $\text{E} \ (11)$