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
<br /> \sum_{k = m}^n \binom{n}{k} \binom{k}{m}<br />
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
<br /> 2^{n - m} \binom{n}{m}<br />
such ordered pairs. Thus, since both methods count the same thing, you have
<br /> \sum_{k = m}^n \binom{n}{k} \binom{k}{m} = 2^{n - m} \binom{n}{m} \textrm{.}<br />