Prove that $\sum\limits_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum\limits_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$ Prove that 
$$\sum_{k=0}^{m}\binom{m}{k}\binom{n+k}{m}=\sum_{k=0}^{m}\binom{n}{k}\binom{m}{k}2^k$$
What should I do for this equation? Should I focus on proving $\binom{m}{k}\binom{n+k}{m}=\binom{n}{k}\binom{m}{k}2^k$?
 A: Let's prove the identity
$$\sum_k\binom m{m-k}\binom{n+k}m=\sum_j\binom nj\binom m{m-j}2^j$$
combinatorially.
Claim. Let $A$ be an $n$-element set and let $B$ be an $m$-element set. Both sides count the number of partitions $A$ into two sets, $A_1$ and $A_2$, and $B$ into two sets, $B_1$, $B_2$ and $B_3$, s.t. $|A_1|+|B_1|=m$.
Proof. In LHS we first choose $B_3$ (first binomial coefficient) and then choose $A_1\cup B_1$ inside $A\cup(B\setminus B_3)$ (second binomial coefficient). In RHS we choose $A_1\subset A$, then $B_1\subset B$ and finally $B_2\subset(B\setminus B_1)$.

Or, if you prefer more algebraic version, this is just
$$
[t^m]\bigl\{(1+t)^n\bigl(1+(1+t)\bigr)^m\bigr\}=
[t^m]\bigl\{(1+t)^n(2+t)^m\bigr\}.
$$
Of course, other coefficients are also equal, so we immediately get a slight generalization,
$$
\sum_k\binom mk\binom{n+k}l=\sum_j\binom nj\binom m{l-j}2^j
$$
(which, after a moment's reflection, is also clear from the purely combinatorial proof above).
A: I'll be using a variety of identities for sums of binomial coefficients.  Note that the indices may vary over all integers (don't worry about boundaries) since the summands are zero outside of the designated interval anyway.


*

*Binomial Theorem: $2^k=\sum_{j} {k\choose j}$.

*Substitute into RHS: $\sum_k \sum_j {n\choose k}{m\choose k}{k\choose j}$. 

*Trinomial Revision: $\sum_k \sum_j {n\choose k}{m\choose j}{m-j\choose k-j}$.

*Symmetry: $\sum_k \sum_j {n\choose k}{m\choose j}{m-j\choose m-k}$.

*Reverse order of summation:  $\sum_j \sum_k {n\choose k}{m\choose j}{m-j\choose m-k}$.

*Factor out ${m\choose j}$: $\sum_j{m\choose j} \sum_k {n\choose k}{m-j\choose m-k}$.

*Vandermonde identity: $\sum_j{m\choose j}{n+m-j\choose m}$.

*Symmetry: $\sum_j{m\choose m-j}{n+m-j\choose m}$.

*Substitute $k=m-j$: $\sum_k{m\choose k}{n+k\choose m}$. 

*And this is the LHS, as desired.

A: This can also be done using a basic complex variables technique.
Suppose we seek to verify that
$$\sum_{k=0}^m {m\choose k} {n+k\choose m}
= \sum_{k=0}^m {m\choose k} {n\choose k} 2^k.$$
Introduce the two integral representations
$${n+k\choose m}
= \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{n+k} \; dz$$
and 
$${n\choose k}
= \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^n \; dz$$
This gives the following integral for the sum on the LHS
$$\frac{1}{2\pi i} 
\int_{|z|=\epsilon} 
\sum_{k=0}^m {m\choose k}
\frac{1}{z^{m+1}} (1+z)^{n+k} \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{(1+z)^n}{z^{m+1}}
\sum_{k=0}^m {m\choose k} 
(1+z)^k \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{(1+z)^n}{z^{m+1}} (2+z)^m \; dz.$$
We get the following integral for the sum on the RHS
$$\frac{1}{2\pi i} 
\int_{|z|=\epsilon} 
\sum_{k=0}^m {m\choose k} 2^k
\frac{1}{z^{k+1}} (1+z)^n \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{(1+z)^n}{z}
\sum_{k=0}^m {m\choose k} 2^k
\frac{1}{z^k} \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{(1+z)^n}{z}
\left(1 + \frac{2}{z}\right)^m \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{(1+z)^n}{z}
\frac{(z+2)^m}{z^m} \; dz.$$
We can stop here without  further evaluation because the integrals for
LHS and RHS are seen to be the same.

A trace as to when this method appeared on MSE and by whom starts at this
MSE link.
A: I view that the purpose on the lefthand side of the eqn as: 
Let $A = {x_{1},x_{2},...,x_{n}}$ and $B={y_{1},y_{2},...,y_{m}}$.  where $n \ge m$
$ \left( \begin{array}{cc}
m  \\
0 \\
 \end{array} \right) $ 
$ \left( \begin{array}{cc}
n  \\
m \\
 \end{array} \right) $ accounts the number of ways to choose $m$ elements from $A$.
$ \left( \begin{array}{cc}
m  \\
1 \\
 \end{array} \right) $ 
$ \left( \begin{array}{cc}
n + 1  \\
m \\
 \end{array} \right) $ accounts the number of ways to choose $m$ elements from $A$ plus one element from $B$. ( from the set {${x_{1},x_{2},...,x_{n},y_{i}}$} )
Keep on going until the last term,
$ \left( \begin{array}{cc}
m  \\
m \\
 \end{array} \right) $ 
$ \left( \begin{array}{cc}
n + m  \\
m \\
 \end{array} \right) $ accounts the number of ways to choose $m$ elements from $A$ and $B$. ( from the set {${x_{1},x_{2},...,x_{n},y_{1},y_{2},...,y_{m}}$} ) 
$$ $$
Now for the right hand side of the eqn, count the same thing as before as :
Set the number of $x_{i}$'s that has been chosen is $j$, then the remaining $m-j$ are elements from $B$. That is
$ \left( \begin{array}{cc}
n  \\
j \\
 \end{array} \right) $ 
$ \left( \begin{array}{cc}
m  \\
m-j \\
 \end{array} \right) $ =  $ \left( \begin{array}{cc}
n  \\
j \\
 \end{array} \right) $ 
$ \left( \begin{array}{cc}
m  \\
j \\
 \end{array} \right) $ 
About the $2^k$ i am still confused, but i hope this will help a little..
