Past exam of the mathematics course of the University of Cambridge / 2005 / ia / Paper 4 / 2E / Solution

For nonnegative integers $n,m$, the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ counts the $m$-element subsets of a fixed $n$-element set. It is zero when $m>n$, and $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=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. HenceFor $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 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{k}{l}\right)$. Choosing $L$ first and then the $k-l$ additional elements of $K$ from its complement gives $\left(\genfrac{}{}{0ex}{}{n}{l}\right)\left(\genfrac{}{}{0ex}{}{n-l}{k-l}\right)$. These count the same pairs, proving the nested-subset binomial identity: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 $\left(\genfrac{}{}{0ex}{}{m}{i}\right)\left(\genfrac{}{}{0ex}{}{n}{k-i}\right)$ choices. The classes for different $i$ are disjoint and exhaust all $k$-element subsets, so double counting givesThe 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.