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

From ProofWiki
Jump to navigation Jump to search

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$


Sources