11
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ This is Dixon's identity. See, for example, en.wikipedia.org/wiki/Dixon%27s_identity. $\endgroup$ – Mark Wildon Sep 27 '13 at 16:38
  • 5
    $\begingroup$ @Mark: I suggest you add your remark as an answer as it really answers the original question. $\endgroup$ – GH from MO Sep 27 '13 at 16:46
  • 5
    $\begingroup$ 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). $\endgroup$ – Todd Trimble Sep 27 '13 at 17:01
  • 8
    $\begingroup$ 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. $\endgroup$ – Mark Wildon Sep 27 '13 at 21:13
  • 3
    $\begingroup$ 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. $\endgroup$ – Mark Wildon Sep 28 '13 at 23:35
28
$\begingroup$

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

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

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.

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

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.