Sum over k of r Choose k by s Choose k by k
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
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Example $1$