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$ [duplicate]

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$?

Solution 1:

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.

1. Binomial Theorem: $2^k=\sum_{j} {k\choose j}$.
2. Substitute into RHS: $\sum_k \sum_j {n\choose k}{m\choose k}{k\choose j}$.
3. Trinomial Revision: $\sum_k \sum_j {n\choose k}{m\choose j}{m-j\choose k-j}$.
4. Symmetry: $\sum_k \sum_j {n\choose k}{m\choose j}{m-j\choose m-k}$.
5. Reverse order of summation: $\sum_j \sum_k {n\choose k}{m\choose j}{m-j\choose m-k}$.
6. Factor out ${m\choose j}$: $\sum_j{m\choose j} \sum_k {n\choose k}{m-j\choose m-k}$.
7. Vandermonde identity: $\sum_j{m\choose j}{n+m-j\choose m}$.
8. Symmetry: $\sum_j{m\choose m-j}{n+m-j\choose m}$.
9. Substitute $k=m-j$: $\sum_k{m\choose k}{n+k\choose m}$.
10. And this is the LHS, as desired.

Solution 2:

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).

Solution 3:

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.