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.
\]

Comments

comments

Tagged with:
Posted in Combinatorics