Prove combinatorics identity 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.
 A: Show $C_k^m C_n^k=C_n^m C_{n-m}^{k-m}$. (forgive my different notation.)
A: Brute-force (not elegant):
$$
\begin{align}
\sum_{k=m}^{n}{{k}\choose{m}}{{n}\choose{k}}
&=\sum_{k=0}^{n-m}{{k+m}\choose{m}}{{n}\choose{k+m}}\\
&=\sum_{k=0}^{n-m}\frac{(k+m)!}{m!k!}\frac{n!}{(n-m-k)!(m+k)!}\\
&=\sum_{k=0}^{n-m}\frac{n!}{m!(n-m)!}\frac{(n-m)!}{k!(n-m-k)!}\\
&= \frac{n!}{m!(n-m)!}\sum_{k=0}^{n-m}\frac{(n-m)!}{k!(n-m-k)!}\\
&= {{n}\choose{m}}2^{n-m}
\end{align}
$$
A: I would not apply the binomial theorem to the power of $2$.
You have a set of $n$ white balls. You want to paint $m$ of them blue and possibly some of the remaining $n-m$ balls red. You can choose the $m$ blue balls in $\binom{n}m$ ways, and there are then $2^{n-m}$ subsets of the remaining $n-m$ balls that you could choose to color red, so there are $2^{n-m}\binom{n}m$ ways to carry out the task.
Alternatively, you could choose $k\ge m$ balls to be colored something other than white and then choose $m$ of these to be painted blue, leaving the other $m-k$ to be painted red; this can be done in $\binom{n}k\binom{k}m$ ways. The possible values of $k$ are the integers from $m$ through $n$, so the lefthand side of the equation counts all possibilities, and the two sides must be equal.
If $S$ is the entire set of balls, $B$ is the set of blue balls, and $R$ is the set of red balls, then the righthand side corresponds to picking $B$ and then picking $R$ from $S\setminus B$. The lefthand side corresponds to picking $R\cup B$ of some cardinality between $m$ and $n$ inclusive, and then choosing $B$ from $R\cup B$.
A: I'd write $2^n \binom{n}{m}$ as the number of ways of picking two subsets, $S_1,S_2 \subseteq \{1,\dots,n\}$ independently with the condition that $|S_2|=m$.
Let $T_1=S_1\cup S_2, T_2=S_2\cap S_1$. 
Then we can see that $\binom{n}{k}\binom{k}{m}2^m$ counts the number of ways of picking a $T_1\subset \{1,\dots,n\}$ of size $k$, then $S_2$ of size $m$ inside $T_1$, then a random subset $S_2$ of $T_1$ or size $m$, and then a random subset of $T_2$ of $S_2$. Then $S_1$ is uniquely determined as $(T_1\setminus S_2)\cup T_2$.
Basically, $k=|S_1\cup S_2|$.
