= Solution
For nonnegative <integers> $n,m$, the <binomial coefficient> $\binom nm$ counts the $m$-element <subsets> of a fixed $n$-element set. It is zero when $m>n$, and $\binom n0=1$, including $n=0$. For $0\le m\le n$, taking the complement is a <bijection> from $m$-element <subsets> to $(n-m)$-element <subsets>; taking a complement twice gives the identity. Hence
$$
\boxed{\binom nm=\binom n{n-m}.}
$$
For $0\le l\le k\le n$, count ordered pairs $(L,K)$ of <subsets> of an $n$-element set with $L\subseteq K$, $|L|=l$ and $|K|=k$. Choosing $K$ first and then $L$ gives $\binom nk\binom kl$. Choosing $L$ first and then the $k-l$ additional elements of $K$ from its complement gives $\binom nl\binom{n-l}{k-l}$. These count the same pairs, proving the <nested-subset binomial identity>:
$$
\boxed{\binom nk\binom kl=\binom nl\binom{n-l}{k-l}.}
$$
For the <Vandermonde identity>, let disjoint sets $A,B$ have cardinalities $m,n$. A $k$-element <subset> of $A\cup B$ contains some number $i$ of elements of $A$. For a fixed $i$, there are $\binom mi\binom n{k-i}$ choices. The classes for different $i$ are disjoint and exhaust all $k$-element <subsets>, so <double counting> gives
$$
\boxed{\sum_{i=0}^k\binom mi\binom n{k-i}=\binom{m+n}k.}
$$
The zero convention makes this valid for all nonnegative $m,n,k$, even if $k>m+n$. No factorial cancellation is needed for either counting proof.
Back to article page
