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

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $m, n \in \Z_{\ge 0}$.


Then:

$\ds \sum_{k \mathop \in \Z} \binom {m - r + s} k \binom {n + r - s} {n - k} \binom {r + k} {m + n} = \binom r m \binom s n$


Proof

\(\ds \) \(\) \(\ds \sum_{k \mathop \in \Z} \binom {m - r + s} k \binom {n + r - s} {n - k} \binom {r + k} {m + n}\)
\(\ds \) \(=\) \(\ds \sum_{k \mathop \in \Z} \binom {m - r + s} k \binom {n + r - s} {n - k} \paren { \sum_{j \mathop \in \Z} \binom r {m + n - j} \binom k j}\) Chu-Vandermonde Identity
\(\ds \) \(=\) \(\ds \sum_{k \mathop \in \Z} \sum_{j \mathop \in \Z} \paren {\binom {m - r + s} k \binom k j } \binom {n + r - s} {n - k} \binom r {m + n - j}\) rearranging
\(\ds \) \(=\) \(\ds \sum_{k \mathop \in \Z} \sum_{j \mathop \in \Z} \binom {m - r + s} j \binom {m - r + s - j} {k - j} \binom {n + r - s} {n - k} \binom r {m + n - j}\) Product of $\dbinom r m$ with $\dbinom m k$
\(\ds \) \(=\) \(\ds \sum_{j \mathop \in \Z} \binom {m - r + s} j \binom r {m + n - j} \paren {\sum_{k \mathop \in \Z} \binom {m - r + s - j} {k - j} \binom {n + r - s} {n - k} }\) grouping
\(\ds \) \(=\) \(\ds \sum_{j \mathop \in \Z} \binom {m - r + s} j \binom r {m + n - j} \binom {m + n - j} {n - j}\) Chu-Vandermonde Identity
\(\ds \) \(=\) \(\ds \sum_{j \mathop \in \Z} \binom {m - r + s} j \binom r {m + n - j} \binom {m + n - j} m\) Symmetry Rule for Binomial Coefficients
\(\ds \) \(=\) \(\ds \sum_{j \mathop \in \Z} \binom {m - r + s} j \binom r m \binom {r - m} {n - j}\) Product of $\dbinom r m$ with $\dbinom m k$
\(\ds \) \(=\) \(\ds \binom r m \paren {\sum_{j \mathop \in \Z} \binom {m - r + s} j \binom {r - m} {n - j} }\)
\(\ds \) \(=\) \(\ds \binom r m \binom s n\) Chu-Vandermonde Identity

$\blacksquare$


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_over_k_of_m%2Br%2Bs_Choose_k_by_n%2Br-s_Choose_n-k_by_r%2Bk_Choose_m%2Bn&oldid=605669"