Summations of Products of Binomial Coefficients

From ProofWiki
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

$\displaystyle \sum_k \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:

$\displaystyle \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:

$\displaystyle \sum_k \binom r k \binom {s + k} n \left({-1}\right)^{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:

$\displaystyle \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:

$\displaystyle \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:

$\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \left({n - k}\right)} {n - k} \frac r {r - t k} = \binom {r + s - t n} n$