Combinatorial identity

Vandermonde's Identity

Vandermonde's Identity states that $\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r$ , which can be proven combinatorially by noting that any combination of $r$ objects from a group of $m+n$ objects must have some $0\le k\le r$ objects from group $m$ and the remaining from group $n$ .

Another Identity

$\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}$

Hat Proof

We have $2k$ different hats. We split them into two groups, each with k hats: then we choose $i$ hats from the first group and $k-i$ hats from the second group. This may be done in $\binom{k}{i}^2$ ways. Evidently, to generate all possible choices of $k$ hats from the $2k$ hats, we must choose $i=0,1,\cdots,k$ hats from the first $k$ and the remaining $k-i$ hats from the second $k$ ; the sum over all such $i$ is the number of ways of choosing $k$ hats from $2k$ . Therefore $\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}$ , as desired.

Page

Toolbox

Search

Combinatorial identity

Contents

Vandermonde's Identity

Another Identity

Hat Proof

Examples

See also