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.

  • $\begingroup$ 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$. $\endgroup$ – Akiva Weinberger Aug 20 '15 at 2:19
  • $\begingroup$ (Or, alternatively, the same with $k$. Or both? If both I guess you'd want an $x^ry^k$ term at the end.) $\endgroup$ – 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...

  • $\begingroup$ 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. $\endgroup$ – Ben Aug 20 '15 at 2:26
  • $\begingroup$ You're welcome! Have added an solution for the bonus case. $\endgroup$ – 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}.$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.