Combinatorial Proofs of a binomial identity

by silvermane
Tags: combinatorics, identities, proof
 P: 111 Think about it like this: Imagine you have a big set $$S$$, with $$n$$ elements. You want to find the number of ordered pairs $$(A, B)$$, where $$A$$ and $$B$$ are subsets of $$S$$, $$A$$ has size $$m$$, and $$A \subseteq B$$. There are two ways to count the number of such ordered pairs. You could choose the elements of $$B$$ first, by letting $$|B| = k$$ (where $$m \leq k \leq n$$); there are then $$\binom{n}{k}$$ ways to choose $$B$$, and $$\binom{k}{m}$$ ways to pick the set $$A$$ from the elements of $$B$$. Thus, for a given $$k$$, there are $$\binom{n}{k} \binom{k}{m}$$ ways to choose the pair $$(A, B)$$, so there are $$\sum_{k = m}^n \binom{n}{k} \binom{k}{m}$$ such pairs in total. Alternatively, you could choose the elements of $$A$$ first. This time, there are $$\binom{n}{m}$$ ways to pick $$A$$. Choosing $$B$$ then amounts to picking any subset $$C$$ of $$S \setminus A$$ which you then "add on" to $$A$$: $$B = A \cup C$$. There are $$2^{|S \setminus A|} = 2^{n - m}$$ subsets of $$S \setminus A$$. Thus, there are $$2^{n - m} \binom{n}{m}$$ such ordered pairs. Thus, since both methods count the same thing, you have $$\sum_{k = m}^n \binom{n}{k} \binom{k}{m} = 2^{n - m} \binom{n}{m} \textrm{.}$$