Induction proof (combinatorics) I had a question. I don't know how to end my solution:
$$\sum_{k=0}^{n}{n\choose k}{k\choose m} = {n\choose m}2^{n-m}$$ for $n = 0$ $${0\choose 0}{0\choose m} = {0\choose m}2^{0-m}$$ if $m=0$: both equal $1$, if $m>0$: both equal $0$. Suppose it holds for :$$\sum_{k=0}^{n-1}{n-1\choose k}{k\choose m} = {n-1\choose m}2^{n-m-1}$$ now:
$$\sum_{k=0}^{n}{n-1\choose k}{k\choose m} + {n\choose n}{n\choose m}= {n\choose m}2^{n-m}$$ $${n-1\choose m}2^{n-m-1} + {n\choose m} = {n\choose m}2^{n-m} $$
now I don't know how to continue it, maybe I did a mistake that it is misleading me. Can you help me?
 A: Inductive Proof
I would start the induction from $n=m$, where both sum and formula are $1$, and then use the inductive step
$$
\begin{align}
\sum_{k=m}^n\color{#C00}{\binom{n}{k}}\binom{k}{m}
&=\sum_{k=m}^n\left[\color{#C00}{\binom{n-1}{k}}\binom{k}{m}+\color{#C00}{\binom{n-1}{k-1}}\color{#090}{\binom{k}{m}}\right]\\
&=\sum_{k=m}^n\left[\binom{n-1}{k}\binom{k}{m}+\binom{n-1}{k-1}\color{#090}{\binom{k-1}{m}}+\binom{n-1}{k-1}\color{#090}{\binom{k-1}{m-1}}\right]\\
&=\binom{n-1}{m}\color{#00F}{2^{n-1-m}}+\binom{n-1}{m}\color{#00F}{2^{n-1-m}}+\binom{n-1}{m-1}2^{n-m}\\
&=\color{#E80}{\binom{n-1}{m}}\color{#00F}{2^{n-m}}+\color{#E80}{\binom{n-1}{m-1}}2^{n-m}\\
&=\color{#E80}{\binom{n}{m}}2^{n-m}
\end{align}
$$

Combinatoric Proof
Suppose we want to distribute $m$ pairs of shoes among $n$ people. Everyone who gets a pair of shoes gets a pair of socks, and the rest of the people can get a pair of socks or not.
We can break things down by how many pairs of socks we want to give out.
We have $n$ people and choose $k$ to wear socks. From those $k$, we want to choose $m$ to wear shoes. The number of ways to distribute shoes and socks is
$$
\sum_{k=m}^n\binom{n}{k}\binom{k}{m}
$$
Another way to look at this is to distribute the $m$ shoes, and the required socks, among the $n$ people, then distribute socks or no socks to the $n-m$ people who don't have shoes. The number of ways to distribute shoes and socks is
$$
\binom{n}{m}2^{n-m}
$$
Since these two formulas count the same thing in different ways, we have
$$
\sum_{k=m}^n\binom{n}{k}\binom{k}{m}=\binom{n}{m}2^{n-m}
$$

Another Approach
Note that
$$
\begin{align}
\binom{n}{k}\binom{k}{m}
&=\frac{n!}{k!(n-k)!}\frac{k!}{m!(k-m)!}\\
&=\frac{n!}{(n-m)!m!}\frac{(n-m)!}{(n-k)!(k-m)!}\\
&=\binom{n}{m}\binom{n-m}{k-m}
\end{align}
$$
Then recalling that $\sum\limits_{k=m}^n\binom{n-m}{k-m}=2^{n-m}$, we get
$$
\begin{align}
\sum_{k=m}^n\binom{n}{k}\binom{k}{m}
&=\sum_{k=m}^n\binom{n}{m}\binom{n-m}{k-m}\\
&=\binom{n}{m}2^{n-m}
\end{align}
$$
