13
$\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.

Improve this question
$\endgroup$
7
  • 8
    $\begingroup$ This is Dixon's identity. See, for example, en.wikipedia.org/wiki/Dixon%27s_identity. $\endgroup$
    – Mark Wildon
    Commented Sep 27, 2013 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
    Commented Sep 27, 2013 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
    Commented Sep 27, 2013 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
    Commented Sep 27, 2013 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
    Commented Sep 28, 2013 at 23:35

2 Answers 2

Reset to default
30
$\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}$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Gorgeous! Now all we need is a combinatorial (counting) argument... :-) $\endgroup$
    – Steven Stadnicki
    Commented Dec 19, 2013 at 23:01
11
$\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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ nice meta-proof $\endgroup$
    – Pietro Majer
    Commented Sep 27, 2013 at 20:46
  • 10
    $\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
    Commented Sep 29, 2013 at 16:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .