Sum over k of r Choose k by s Choose k by k

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Then:

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

where $\dbinom r k$ etc. are binomial coefficients.


Proof

\(\ds \sum_k \binom r k \binom s k k\) \(=\) \(\ds \sum_k \binom r k \binom {s - 1} {k - 1} s\) Factors of Binomial Coefficient
\(\ds \) \(=\) \(\ds s \sum_k \binom r k \binom {s - 1} {k - 1}\) as $s$ is constant
\(\ds \) \(=\) \(\ds s \binom {r + s - 1} {r - 1}\) Sum over $k$ of $\dbinom r {m + k} \dbinom s {n + k}$: $s \gets s - 1$, $m \gets 0$, $n \gets -1$

$\blacksquare$


Sources