In my theoretical mathematics class notes, the following problem is left open as an exercise. The professor thinks the solution should be easily seen, but after many hours, I cannot gain the proper insight.
The following identity can be proven using the binomial theorem.
$$\sum_{m = k}^{n}{{m \choose k}{n \choose m}} = {n \choose k}2^{n - k}$$
On
I have absolutely no clue how to show that using the binomial theorem. But there's really only one good way to show things are equal in combinatorics, and that's to phrase the same question in two different ways.
For this one, I thought of picking a soccer team. Let's say they're allowed to bring as many people as they want out of $n$ applicants, but only $k$ can be starters.
One way to find the number of ways to do this would be by picking the whole team, and then choosing starters from that team. We can do this by counting the possible teams with $i$ players where $n \geq i \geq m$. To do that you would choose $i$ members from your $n$, and then $k$ starters from the $i$ team members. Then you add up all the possible $i$'s and you have the left side of that equation.
We could also choose the starters first and then add others later. The number of ways to choose the starters would then be $n \choose k$, and then we could add any subset of the remaining $n-k$ players. Since there are $2^{n-k}$ such subsets, we have the right side of your equation.
Maybe you're better at symbol manipulation than I, and you'll be able to pull off some clever substitution to show this using the binomial theorem, but I like this kind of proof better.
I would agree with genisage that the counting proof is better here! But if you're really in search of the binomial theorem proof, here is a method. Consider $(1 + 1 + x)^n$. What is the coefficient on the $x^k$?
Well, if we look at this as $(2 + x)^n$, the binomial theorem says the $k$th term is ${n \choose k} 2^{n - k} x^k$, and hence the coefficient on the $x^k$ is ${n \choose k} 2^{n - k}$.
On the other hand, we could look at this like $(1 + (1 + x))^n$. The $m$th term of this looks like ${n \choose m} 1^{n - m} (1 + x)^m = {n \choose m} (1 + x)^m$. Oh, but now we need to expand $(1 + x)^m$, and we see the $k$ term (of the $m$th term), including the ${n \choose m}$ is $$ {n \choose m}{m \choose k} 1^{m - k} x^k = {n \choose m}{m \choose k} x^k. $$ To get the coefficient on the $x^k$, we need to add up all possible $x^k$ terms from each choice of $m$. Hence the coefficient on the $x^k$ term is $\sum_{m = k}^n {n \choose m}{m \choose k}$.