# Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$

I found the following formula in a book without any proof:

$$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$

This does not seem to follow immediately from the basic binomial identities. I would like to know how to prove this, and any relevant references.

Remark : This question has been asked previously on math.SE without receiving any complete answers.

• This is Dixon's identity. See, for example, en.wikipedia.org/wiki/Dixon%27s_identity. – Mark Wildon Sep 27 '13 at 16:38
• @Mark: I suggest you add your remark as an answer as it really answers the original question. – GH from MO Sep 27 '13 at 16:46
• See particularly Short Proofs of Saalschutz's and Dixon's Theorems by Ira Gessel and Dennis Stanton: sciencedirect.com/science/article/pii/0097316585900263 (which gives the identity more directly than the Wikipedia article). – Todd Trimble Sep 27 '13 at 17:01
• I disagree with the vote to close (not just because I was half-way through typing up a short proof). The techniques used to prove identities like this are definitely of interest to research mathematicians. – Mark Wildon Sep 27 '13 at 21:13
• Half-way through a proof is clearly a bad time to make annoucements. The Gessel-Stanton proof is shorter than any proof I can find. One useful source for binomial coefficients identities is Gould's tables: math.wvu.edu/~gould. See Volume 4 (1.13) for Dixon's identity. – Mark Wildon Sep 28 '13 at 23:35

## 2 Answers

Here is a short proof of the more general identity

$$\sum_{k=0}^{2m} (-1)^k \binom{2m}{k} \binom{x}{k}\binom{x}{2m-k} = (-1)^m \binom{2m}{m} \binom{x+m}{2m}.$$

Considered as polynomials in $x$, both sides have degree $2m$. If $x = m$ then $\binom{x}{k}\binom{x}{2m-k}$ is non-zero only when $k=m$, and so both sides equal $(-1)^m \binom{2m}{m}$. If $x \in \{0,1,\ldots,m-1\}$ then both sides are zero. If $x = -r$ where $r \in \{1,\ldots, m\}$ then, using that $\binom{-r}{k} = \binom{r+k-1}{r-1}$, the left-hand side becomes

$$\sum_{k=0}^{2m} (-1)^k \binom{2m}{k} f(k)$$

where $f(y) = \binom{r+y-1}{r-1} \binom{r+2m-y-1}{r-1}$. Since $f$ is a polynomial of degree $2(r-1) < 2m$ in $y$, its $2m$-th iterated difference is zero. So both sides are again zero. This shows that the two sides agree at $2m+1$ values of $x$, and so they must be equal as polynomials in $x$.

This identity is a specialization of (2) in the Gessel-Stanton paper linked to above. It is (6.56) in Volume 4 of Gould's tables. To get Dixon's identity, take $x=2m$ and use that $\binom{2m}{2m-k} = \binom{2m}{k}$.

• Gorgeous! Now all we need is a combinatorial (counting) argument... :-) – Steven Stadnicki Dec 19 '13 at 23:01

Mathematica evaluates it in a blink of an eye, which means that it is an application of W(ilf)-Z(eilberger) method, which means that you can read all about it in Petkovsek/Zeilberger's A=B.

• nice meta-proof – Pietro Majer Sep 27 '13 at 20:46
• The WZ method gives a simple proof of Dixon's identity (and many other hypergeometric series identities), but it doesn't really explain it. – Ira Gessel Sep 29 '13 at 16:22