A Double Sum of Binomials
Prove the following summation of binomial coefficients.
\[
\sum_{i=0}^n \sum_{j=0}^m {i+j \choose j} = {n + m +2 \choose n+1} – 1.
\]
First, by Pascal’s rule that \({i+j \choose j} = {i+j-1 \choose j} + {i+j-1 \choose j-1} \), the inner summation
\[
\sum_{j=0}^m {i+j \choose j} = {i+m+1 \choose m}.
\]
Similarly,
\[
\sum_{i=0}^n {i+m+1 \choose m} = \sum_{i=0}^n {i+m+1 \choose i+1}
= \sum_{i=0}^{n+1} {i+m+1 \choose i} – 1
= {n+m+2 \choose n+1} – 1.
\]