Recognitions:
Gold Member

## Combinatorial Proofs of a binomial identity

1. The problem statement, all variables and given/known data
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)

3. 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 :)
 PhysOrg.com science news on PhysOrg.com >> 'Whodunnit' of Irish potato famine solved>> The mammoth's lament: Study shows how cosmic impact sparked devastating climate change>> Curiosity Mars rover drills second rock target
 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{.}$$

 Tags combinatorics, identities, proof