Prove that $\sum_{k=0}^m \binom{n}{k} \binom{n-k}{m-k}= 2^m \binom{n}{m}$ for $m < n $ Prove that $\sum_{k=0}^m \dbinom{n}{k} \dbinom{n-k}{m-k}= 2^m \dbinom{n}{m}$ for $m < n $

In short : I've tried to prove this by induction since I can't really see how to interpret this with a combinatorial argument,below I
  provide my thinking

Inducting on $m$ I have proved the base case $m=1$,since I have
\begin{array}
\space \dbinom{n}{0} \dbinom{n}{1} +\dbinom{n}{1} \dbinom{n-1}{0} & =2 \dbinom{n}{1} \\
n+n & =2n \\
\end{array}
Assuming it hold for $m=j$ I have  $\sum_{k=0}^j \dbinom{n}{k} \dbinom{n-k}{j-k}= 2^j \dbinom{n}{j}$ 
(I don't write the claim for sake of space and your time)
So to complete the induction I have to prove that 
$$ 2^{j+1} \dbinom{n}{j+1} =2^j \dbinom{n}{j} +\dbinom{n}{k} \dbinom{n-k}{(j+1)-k}$$
which is rather a beast to simplify...
Can someone help ?
(Any proof is welcome,though I would also appreciate if someone can help me with  the induction proof)
 A: You have
$$
 \binom{n}{k} \binom{n-k}{m-k}
 = \frac{n!}{k!(m-k)!(n-m)!}
 = \binom{n}{m} \binom{m}{k},
$$
so
$$
 \sum_{k=0}^m \binom{n}{k} \binom{n-k}{m-k}
 = \binom{n}{m} \sum_{k=0}^m \binom{m}{k}
 = 2^m \binom{n}{m}.
$$
PS: You can also interpret this formula combinatoricaly: The right side $2^m \binom{n}{m}$ tells us that we have $n$ colourless balls, out of which we choose $m$ many (giving us $\binom{n}{m}$), and paint each of them either black or white (giving us $2^m$). The term $\binom{n}{k} \binom{n-k}{m-k}$ on the left side tells us that we choose $k$ balls to paint black and then $m-k$ balls to paint white; summing this over $k = 0, 1, \dotsc, m$ gives us the same result as before.
A: Another solution is by double counting.
Suppose that we have n balls, and we want to choose m balls among them and color each of them by blue or red. In how many ways we can do that?
Right side: We can simply choose m of n balls ( $n \choose m$ ) and then choose a color for each of these m balls ($2^m$).
Left side: We can choose $k$ balls to be colored by blue ( $n \choose k$ ) and the m-k balls from the remaining balls to be colored by red ( $n-k \choose m-k$ ) and we must do so for all $1\leq k \leq m$.
A: Hint: The following technique can also be useful in more complicated situations.

We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^{n}$ in a polynomial or series $A(x)=\sum_{k=0}^{\infty}a_kx^k$. We can write e.g.
  \begin{align*}
  \binom{n}{k}=[x^k](1+x)^n
  \end{align*}
We obtain for $0\leq m\leq n$
\begin{align*}
  \sum_{k=0}^m&\binom{n}{k}\binom{n-k}{m-k}\\
  &=\sum_{k=0}^\infty[x^k](1+x)^n[y^{m-k}](1+y)^{n-k}\tag{1}\\
  &=[y^m](1+y)^n\sum_{k=0}^{\infty}y^k(1+y)^{-k}[x^k](1+x)^n\tag{2}\\
  &=[y^m](1+y)^n\left(1+\frac{y}{1+y}\right)^n\tag{3}\\
  &=[y^m](1+2y)^n\\
  &=\binom{n}{m}2^m
  \end{align*}

Comment:


*

*In (1) we use the coefficient of operator twice and set the upper limit of the sum to $\infty$ without changing anything, since we add only zero.

*In (2) we rearrange the sum by using the linearity of the coefficient of operator and $[x^{n+k}]A(x)=[x^n]x^{-k}A(x)$.

*In (3) we apply the substitution rule
\begin{align*}
  A(x)=\sum_{k=0}^{\infty}a_kx^k=\sum_{k=0}^{\infty}x^k[y^k]A(y)
  \end{align*}
with $a_k=[y^k]A(y)$.
