Combinatorial Proofs of a binomial identity

silvermane

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 :)

VKint

Think about it like this: Imagine you have a big set [tex] S [/tex], with [tex] n [/tex] elements. You want to find the number of ordered pairs [tex] (A, B) [/tex], where [tex] A [/tex] and [tex] B [/tex] are subsets of [tex] S [/tex], [tex] A [/tex] has size [tex] m [/tex], and [tex] A \subseteq B [/tex]. There are two ways to count the number of such ordered pairs. You could choose the elements of [tex] B [/tex] first, by letting [tex] |B| = k [/tex] (where [tex] m \leq k \leq n [/tex]); there are then [tex] \binom{n}{k} [/tex] ways to choose [tex] B [/tex], and [tex] \binom{k}{m} [/tex] ways to pick the set [tex] A [/tex] from the elements of [tex] B [/tex]. Thus, for a given [tex] k [/tex], there are [tex] \binom{n}{k} \binom{k}{m} [/tex] ways to choose the pair [tex] (A, B) [/tex], so there are
[tex]
\sum_{k = m}^n \binom{n}{k} \binom{k}{m}
[/tex]
such pairs in total.

Alternatively, you could choose the elements of [tex] A [/tex] first. This time, there are [tex] \binom{n}{m} [/tex] ways to pick [tex] A [/tex]. Choosing [tex] B [/tex] then amounts to picking any subset [tex] C [/tex] of [tex] S \setminus A [/tex] which you then "add on" to [tex] A [/tex]: [tex] B = A \cup C [/tex]. There are [tex] 2^{|S \setminus A|} = 2^{n - m} [/tex] subsets of [tex] S \setminus A [/tex]. Thus, there are
[tex]
2^{n - m} \binom{n}{m}
[/tex]
such ordered pairs. Thus, since both methods count the same thing, you have
[tex]
\sum_{k = m}^n \binom{n}{k} \binom{k}{m} = 2^{n - m} \binom{n}{m} \textrm{.}
[/tex]