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

## marked as duplicate by Grigory M, Lord_Farin, Jonas Meyer, Hans Engler, Najib IdrissiDec 29 '14 at 8:17

• That approach won't work, since it is false. Take $m=2$, $k=1$, $n=1$. The left hand side is $2$ while the right hand side is $4$. Look for a counting argument: the two sums count the same object. – Gyu Eun Lee Oct 19 '13 at 4:57
• related: wiki: Delannoy numbers – Grigory M Jul 9 '14 at 12:10
• – Grigory M Dec 26 '14 at 14:19

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.

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

• Beautiful, I love it! – vadim123 Dec 18 '13 at 14:32
• (Cf. [shifted] Legendre polynomials, btw!) – Grigory M Jan 2 '14 at 0:39

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.

• This is a pretty neat approach. +1 – Cameron Williams Aug 25 '14 at 3:23

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