# Combinatorial Proofs of a binomial identity

by silvermane
Tags: combinatorics, identities, proof
 PF Patron P: 117 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 :)
 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{.}$$

 Related Discussions Calculus & Beyond Homework 9 Precalculus Mathematics Homework 2 General Math 0 Introductory Physics Homework 2 Introductory Physics Homework 1