Problem: Show that $ \sum_{k=0}^m\binom{n}{k}\binom{n-k}{m-k}=2^m\binom{n}{m} . $ Solution: Let $S$ be such that $|S| = n$. Let $A = \{(X,Y): X \subseteq S, |X| = m, Y \subseteq X \}$. Clearly, the number of $m$-element subsets, $X$, of $S$ is ${n \choose m}$ and the number of subsets $Y$ of $X$ is $2^m$ so $A = 2^m{n \choose m}$. Define an equivalence relation on $A$ by $B,C \in A$ satisfy $B \sim C \iff |B_{Y}| = |C_{Y}|$ (this is trivially an equivalence relation as inherited by $=$). There are exactly $m+1$ equivalence classes for when $K \in A$ satisfies $K_{Y}$ has cardinality $|K_{Y}| = 0,1,2,\dots, m$. For each fixed $k$ with $0 \leq k \leq m$, we see that the size of the equivalence class is ${n \choose k}{n - k \choose m-k}$ since we may select $k$ elements to exist within $K_{Y}$ and then add on any $m-k$ elements from the remaining $n-k$ to form $K_{X}$. Summing over all $k$, we find that $\sum_{k=0}^m\binom{n}{k}\binom{n-k}{m-k}=2^m\binom{n}{m} .$