Summations of Products of Binomial Coefficients

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$