# Sum over k of r Choose m+k by s Choose n+k/Proof 1

## Theorem

Let $s \in \R, r \in \Z_{\ge 0}, m, n \in \Z$.

Then:

$\displaystyle \sum_k \binom r {m + k} \binom s {n + k} = \binom {r + s} {r - m + n}$

## Proof

 $\displaystyle \sum_k \binom r {m + k} \binom s {n + k}$ $=$ $\displaystyle \sum_k \binom r {r - m - k} \binom s {s - n - k}$ Symmetry Rule for Binomial Coefficients $\displaystyle$ $=$ $\displaystyle \sum_k \binom r k \binom s {s - n - \left({r - m - k}\right)}$ Change of Index Variable of Summation $\displaystyle$ $=$ $\displaystyle \sum_k \binom r k \binom s {r - m - k + n}$ Symmetry Rule for Binomial Coefficients $\displaystyle$ $=$ $\displaystyle \sum_k \binom r k \binom s {\left({r - m + n}\right) - k}$ $\displaystyle$ $=$ $\displaystyle \binom {r + s} {r - m + n}$ Chu-Vandermonde Identity

$\blacksquare$