# Sum over two binomials identity

So while trying to count the number of configurations in a statistical mechanics research problem I come across this lovely sum:

$$\sum_{i=0}^k \binom{i+r}{r} \binom{k-i+r}{r}$$

I scoured the internet for binomial identities the closest being an identity close to the Chu-Vandermonde, so after a few hours I give up and chuck it into Mathematica who immediately gives me: $$\sum_{i=0}^k \binom{i+r}{r} \binom{k-i+r}{r}=\binom{k+2r+1}{k}$$ Was just wondering if anybody had any idea how to show that or if it is a standard identity I just don't know.

BONUSES: Mathematica wasn't able to do it, but if anybody has any idea or insight on how to do a double sum over three binomials: $$\sum_{i=0}^N \sum_{j=0}^{N-i} \binom{i+r}{r}\binom{j+r}{r}\binom{N-i-j+r}{r}$$ It would help gain insight on trying to do it over K binomials: $$\sum_{x_1, \cdots, x_K = 0 }^{N} \ \prod_{i=1}^K \binom{x_i+r}{r} \delta^{N}_{\sum_{i=1}^K x_i}$$ where $\delta_i^j$ is the Kronecker delta.

• Have you tried this? Call your expression $A_r$. Examine $\sum_rA_rx^r$, switch the two summation signs, simplify, and examine the coefficient of $x^r$. – Akiva Weinberger Aug 20 '15 at 2:19
• (Or, alternatively, the same with $k$. Or both? If both I guess you'd want an $x^ry^k$ term at the end.) – Akiva Weinberger Aug 20 '15 at 2:31

Using a combination of upper negation and Vandermonde, we have: \begin{align}\sum_{i=0}^k \binom{i+r}{r} \binom{k-i+r}{r} &=\sum_{i=0}^k\binom {i+r}i\binom {k-i+r}{k-i}\\ &=\sum_{i=0}^k (-1)^i\binom{-r-1}i (-1)^{k-i}\binom {-r-1}{k-i}\\ &=(-1)^k\sum_{i=0}^k\binom {-r-1}i\binom{-r-1}{k-i}\\ &=(-1)^k\binom{-2r-2}k\\ &=(-1)^{2k}\binom{k+2r+1}k\\ &=\binom{k+2r+1}{k}\qquad\blacksquare \end{align}

We can use the result above to help with the bonus case.

\begin{align} \sum_{i=0}^N \sum_{j=0}^{N-i} \binom{i+r}{r}\binom{j+r}{r}\binom{N-i-j+r}{r} &=\sum_{i=0}^N \binom{i+r}{r}\color{blue}{\sum_{j=0}^{N-i}\binom{j+r}{r}\binom{\overline{N-i}-j+r}{r}}\\ &=\sum_{i=0}^N \binom{i+r}{r}\color{blue}{\binom{\overline{N-i}+2r+1}{\overline{N-i}}}\\ &=\sum_{i=0}^N (-1)^i\binom{-r-1}{i}(-1)^{N-i}\binom{-2r-2}{N-i}\\ &=(-1)^N\sum_{i=0}^N \binom{-r-1}i\binom{-2r-2}{N-i}\\ &=(-1)^N\binom{-2r-3}N\\ &=\binom{N+2r+2}N\qquad\blacksquare \end{align}

An interesting pattern emerges...

• Thanks! Upper negation and Vandermonde. Just found out those two neat tools while browsing stack exchange. You can also do the general case I posted using upper negation and the generalized Vandermonde. – Ben Aug 20 '15 at 2:26
• You're welcome! Have added an solution for the bonus case. – hypergeometric Aug 20 '15 at 3:12

Suppose we seek to evaluate $$S(k,r) = \sum_{q=0}^k {q+r\choose r} {k-q+r\choose r} = \sum_{q=0}^k {q+r\choose r} {k-q+r\choose k-q}.$$

Introduce $${k-q+r\choose k-q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k-q+1}} (1+z)^{k-q+r} \; dz.$$

Observe that when $q\gt k$ the integral vanishes so we may use it to control the range, extending the sum in $q$ to infinity to get $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^{k+r} \sum_{q\ge 0} {q+r\choose r} \frac{z^q}{(1+z)^q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^{k+r} \frac{1}{(1-z/(1+z))^{r+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^{k+2r+1} \frac{1}{(1+z-z)^{r+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^{k+2r+1} \; dz \\ = {k+2r+1\choose k}.$$

The general pattern here for $K$ binomials is $$[z^N] \frac{1}{(1-z)^{(r+1)\times K}} = {(r+1)K - 1+ N\choose N}.$$

• Using contour integrals to represent binomial coefficients. Clever! – Ben Aug 21 '15 at 3:30