Prove that for $n,m\geq0$, that
$\sum\limits_{k=m}^{n}{{k}\choose{m}}{{n}\choose{k}}=2^{n-m}{{n}\choose{m}}$.
I wrote $2^{n-m}$ as $\sum\limits_{k=0}^{n-m}{{n-m}\choose{k}}$ using the binomial theorem. Then I drew a Venn-diagram with a set $A$ which has $k$ elements, and a set $B$ which is a subset of $A$ with $m$ elements. from which I think you can interpret the left side of the equality in the question as the number of ways in which you can first choose $k$ elements from the sample space (with n elements) and then choose $m$ elements from $A$. However, I am not entirely sure how to interpret the right side of the inequality then. Could anyone please comment on my approach and tell me what I should do next if it's correct and otherwise tell me how else it should be done?
Furthermore, could anyone please tell me how I should interpret the summation in terms of combinatorics? Because I do not really see what the summation does in terms of sets/how I should visualize this in a diagram or how I should just see this in general. Thank you in advance.
Best Answer
Show $C_k^m C_n^k=C_n^m C_{n-m}^{k-m}$. (forgive my different notation.)