Prove $\sum_{k=0}^{m} \binom{m}{k}\binom{n+k}{m} = \sum_{k=0}^{m}\binom{n}{k} \binom{m}{k} 2^{k}$. This is a question about proof of permutation and combination
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} $$
This Question is from http://staff.ustc.edu.cn/~jiema/Comb2020/week1.pdf
 A: This problem is a typical application of counting twice, an important idea in combinatorics and group theory (e.g., Burnside's lemma).
Here, we break $2^k$ into $\sum\limits_{i=0}^k \binom k i$.
Therefore, $\binom m k 2^k = \sum\limits_{i=0}^k \binom m k \binom k i$ (1).
By elementary mathematics, $\binom m k \binom k i = \binom m i \binom {m-i} {m-k}$ (2).
We consider the right hand side (RHS) of your equation first. By Eq. (1, 2),
$RHS = \sum\limits_{k=0}^m \binom n k \sum\limits_{i=0}^k \binom m i \binom {m-i}{m-k}$. (3)
Let us consider counting Eq. (3) as an algorithm. The algorithm first fixes $k$ and counts $\sum\limits_{i=0}^k \binom m i \binom {m-i}{m-k}$. Let us change our mind, what about fixes $i$ and traverses $k$? We have:
$RHS = \sum\limits_{i=0}^{m}\binom m i\sum\limits_{k=i}^m \binom n k \binom {m - i}{m - k}$. (4)
In Eq. (4), $\sum\limits_{k=i}^m \binom n k \binom {m - i}{m - k}$ is a Vandermonde's convolution, by the Vandermonde's identity:
$RHS = \sum\limits_{i=0}^m \binom m i \binom {n+m - i}{m}$. (5)
Now we aim to simplify Eq. (5). Let $S$ be the set $\{0, 1, ..., m\}$. We then define a bijection $f$ from $S \rightarrow S$: $f(i) = m - i$. When $i$ traverses $S$, $m - i$ also traverses $S$ and $\binom m i = \binom m {m-i}$.
Finally, $RHS = \sum\limits_{i=0}^m \binom m i \binom {n+i}{m} = \sum\limits_{k=0}^m \binom m k \binom {n+k}{m} = LHS$. (6)
A: In seeking to prove that
$$\sum_{k=0}^m {n\choose k} {m\choose k} 2^k
= \sum_{k=0}^m {m\choose k} {n+k\choose m}$$
we write for the LHS
$$\sum_{k=0}^m {n\choose k} {m\choose m-k} 2^k
= [z^m] (1+z)^m
\sum_{k=0}^m {n\choose k} 2^k z^k.$$
Here the coefficient extractor enforces the upper limit and we find
$$[z^m] (1+z)^m
\sum_{k\ge 0} {n\choose k} 2^k z^k
= [z^m] (1+z)^m (1+2z)^n.$$
This is
$$\mathrm{Res}_{z=0} \frac{1}{z^{m+1}} (1+z)^m (1+2z)^n.$$
Now we put $z/(1+z) = w$ so that $z=w/(1-w)$ and $dz = 1/(1-w)^2 \; dw$
to obtain
$$\mathrm{Res}_{w=0} \frac{1}{w^m} \frac{1-w}{w}
\frac{(1+w)^n}{(1-w)^n} \frac{1}{(1-w)^2}
= \mathrm{Res}_{w=0} \frac{1}{w^{m+1}}
\frac{(1+w)^n}{(1-w)^{n+1}}.$$
This evaluates by inspection to
$$\sum_{k=0}^m {n\choose k} {m-k+n\choose n}.$$
Now we have
$${n\choose k} {m-k+n\choose n}
= \frac{(m-k+n)!}{k! \times (n-k)! \times (m-k)!}
= {m\choose k} {m-k+n\choose n-k}$$
so that we get
$$\sum_{k=0}^m {m\choose k} {m-k+n\choose n-k}
= \sum_{k=0}^m {m\choose m-k} {n+k\choose n-m+k}
\\ = \sum_{k=0}^m {m\choose k} {n+k\choose m}$$
which is the RHS as claimed.
A: First note that the coefficient of $x^n$ in $(1+2x)^m(1+x)^n$ is $$\sum_{k=0}^{m}{m\choose k}\cdot2^k\cdot {n\choose n-k} = \sum_{k=0}^{m}{m \choose k}{n \choose k}2^k \tag{1}$$
Next note that $(1+2x)^m(1+x)^n$ can be written as
\begin{align}
(x +(1+x))^m(1+x)^n &= \left(\sum_{k=0}^m {m \choose m-k}x^{m-k}(1+x)^k \right)(1+x)^n\\
&=\sum_{k=0}^m{m \choose m-k}x^{m-k}(1+x)^{n+k} 
\end{align}
And the coefficient of $x^n$ in the above expression is given by
$$\sum_{k=0}^m{m \choose m-k}{n+k \choose n +k-m} = \sum_{k=0}^m{m \choose k}{n+k \choose m} \tag{2}$$
The required identity follows from $(1)$ and $(2)$
