Combinatorial Proofs of a binomial identity

[silvermane]

Homework Statement

Show that for all integers n,m where 0 ≤ m ≤ n
The sum from k=m to n of {(nCk)*(kCm)} = (nCm)*2^(n-m)

The Attempt at a Solution

So for the proof, I have to use a real example, such as choosing committees, binary sequences, giving fruit to kids, etc. I have been thinking hard on it, but I don't fully understand it to do so. Any hints would be wonderful. I don't exactly want the answer, just an understanding! Thank you for your time :)

 

[VKint]

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{.}$$