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.

\]