Summations of Products of Binomial Coefficients
Jump to navigation
Jump to search
Theorem
This page gathers together some identities concerning summations of products of binomial coefficients.
In the following, unless otherwise specified:
- $k, m, n \in \Z$
- $r, s, t \in \R$.
Chu-Vandermonde Identity
- $\ds \sum_{k \mathop = 0}^n \binom r k \binom s {n - k} = \binom {r + s} n$
Sum over $k$ of $\dbinom r {m + k}$ by $\dbinom s {n + k}$
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}$
Sum over $k$ of $\dbinom r k$ by $\dbinom {s + k} n$ by $\left({-1}\right)^{r - k}$
Let $s \in \R, r \in \Z_{\ge 0}, n \in \Z$.
Then:
- $\ds \sum_k \binom r k \binom {s + k} n \paren {-1}^{r - k} = \binom s {n - r}$
Sum over $k$ of $\dbinom {r - k} m$ by $\dbinom s {k - t}$ by $\left({-1}\right)^{k - t}$
Let $s \in \R, r, t, m \in \Z_{\ge 0}$.
Then:
- $\ds \sum_{k \mathop = 0}^r \binom {r - k} m \binom s {k - t} \paren {-1}^{k - t} = \binom {r - t - s} {r - t - m}$
Sum over $k$ of $\dbinom {r - k} m$ by $\dbinom {s + k} n$
Let $m, n, r, s \in \Z_{\ge 0}$ such that $n \ge s$.
Then:
- $\ds \sum_{k \mathop = 0}^r \binom {r - k} m \binom {s + k} n = \binom {r + s + 1} {m + n + 1}$
Sum over $k$ of $\dbinom {r - t k} k$ by $\dbinom {s - t \left({n - k}\right)} {n - k}$ by $\dfrac r {r - t k}$
Let $r, s, t \in \R, n \in \Z$.
Then:
- $\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + s - t n} n$