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:

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

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

$=$

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

$\ds $

$=$

$\ds \sum_k \binom r k \binom s {s - n - \left({r - m - k}\right)}$

$\ds $

$=$

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

$\ds $

$=$

$\ds \sum_k \binom r k \binom s {\left({r - m + n}\right) - k}$

$\ds $

$=$

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

$\blacksquare$