Sum over k of r Choose m+k by s Choose n+k

Theorem

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

Then:

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

where $\dbinom r {m + k}$ etc. are binomial coefficients.

Proof

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

$\blacksquare$