Why $\sum_{k=m}^n\binom{n}{k}\binom{k}{m} = \binom{n}{m}2^{n-m},0< m< n$?

Question

I tried to use induction and I got $\displaystyle \sum_{k=m}^{n+1}\left(\begin{array}{c}n\\ k\end{array}\right)\left(\begin{array}{n}k\\ m\end{array}\right) = \left(\begin{array}{c}n+1\\ m\end{array}\right) 2^{n-1-m}$ So $\displaystyle \sum_{k=m}^{n+1}\left(\begin{array}{c}n\\ k\end{array}\right)\left(\begin{array}{n}k\\ m\end{array}\right) + \left(\begin{array}{c}n\\ n+1\end{array}\right) \left(\begin{array}{c}n+1\\ m\end{array}\right)$ And $\displaystyle \sum_{k=m}^{n+1}\left(\begin{array}{c}n\\ k\end{array}\right)2^{n-m} + \left(\begin{array}{c}n\\ n+1\end{array}\right) \left(\begin{array}{c}n+1\\ m\end{array}\right)$ I don't know what to do now. Can someone help me?

Answer 1

If you want to try completing your attempt using induction, try double induction on $m$ and $n$. Both sides of the identity equal $1$ when $n=m$. Now suppose the identity holds for a particular $m$ and for all $n\ge m$. Furthermore, suppose it holds for $m+1$ and a particular $n$. We now show that it also holds for $m+1$ and $n+1$.

Evaluate $$ \begin{aligned} \sum_{k=m+1}^{n+1}\binom{n+1}{k}\binom{k}{m+1}&=\sum_{k=m+1}^{n+1}\left(\binom{n}{k}+\binom{n}{k-1}\right)\binom{k}{m+1}\\ &=\sum_{k=m+1}^n\binom{n}{k}\binom{k}{m+1}+\sum_{k=m+1}^{n+1}\binom{n}{k-1}\left(\binom{k-1}{m+1}+\binom{k-1}{m}\right)\\ &=\sum_{k=m+1}^n\binom{n}{k}\binom{k}{m+1}+\sum_{k=m+1}^n\binom{n}{k}\binom{k}{m+1}+\sum_{k=m}^n\binom{n}{k}\binom{k}{m}\\ &=2\binom{n}{m+1}2^{n-m-1}+\binom{n}{m}2^{n-m}\\ &=\binom{n+1}{m+1}2^{n-m}\\ &=\binom{n+1}{m+1}2^{(n+1)-(m+1)}. \end{aligned} $$ In the first, second, and fifth steps the Pascal's triangle recurrence has been used. The induction hypothesis has been used in the fourth step. Induction on $n$ shows the identity holds for $m+1$ and all $n\ge m+1$. Consequently, by induction on $m$, it holds for all $0\le m\le n$.

Answer 2

Consider the following scenario:

You have $n$ numbered, white balls. You want to color $m$ of them blue, and some number of the remaining balls (anywhere form $0$ to $n-m$) red.

You could do this by first picking out $k$ balls that will get a color at all, and then from among those choose $m$ to make blue, and make the rest red. You could, alternately, do this by first picking the $m$ balls to color blue, then for each of the remaining $n-m$ balls decide whether you want to color it red or not.

If you want to know in how many ways this coloring can be done, these two approaches give two different-looking expressions for how many ways this can be done. But ultimately, those two expressions must yield the same final value, as they count the same thing.

Answer 3

Use $${n \choose k}{k \choose m}={n \choose m}{n-m \choose k-m}$$ Then $$S=\sum_{k=m}^{n}{n \choose k}{k \choose m}= {n \choose m} \sum_{k=m}^{n} {n-m \choose k-m}= {n \choose m} \sum_{p=0}^{n-m} {n-m \choose p}={n \choose m} 2^{n-m}$$