# Strehl identity for the sum of cubes of binomial coefficients

In 1993 Strehl showed that $$\sum_k\binom nk^3=\sum_k\binom nk^2\binom{2k}n.$$ I’m interested in a combinatorial proof.

Upd (Jan '14). Maybe the original question was too restrictive — I'm now asking for any proof.

I've written a combinatorial proof (see answers), but it's somewhat convoluted. Maybe there is a nice proof using generating functions / residues (something like one for the Dixon's identity), for example?..

1. There is of course an algebraic proof (any such identity can be proved using WZ-magic of hypergeometric functions AFAIK). Feel free to post any proof, but I’m mainly interested in a combinatorial proof.
2. It’s well known that $\sum_k\binom nk=2^n$ and $\sum_k\binom nk^2=\binom{2n}n$. Perhaps, one should think about Stehl identity as the next member of this family. (Is there any analogue for degree 4, I wonder, btw?)
3. Quadratic case suggests that it’s, perhaps, better to write LHS as $\binom nk^2\binom n{n-k}$. And maybe instead of one $n$ one should introduce two or three parameters (s.t. Strehl identity corresponds to n=m[=l]). A naive approach is $\sum\binom nk\binom mk\binom m{m-k}$ but looks like $\sum\binom nk\binom mk\binom n{m-k}$ might be a better choice — actually, it's equal to $\sum\binom nk\binom mk\binom{2k}m$.
4. arXiv:0712.3946 might be of some relevance. There LHS is interpreted as the number of ways to deal a deck of 3n cards (n denominations, 3 colors) to 3 players so that no player receives a card of her own color.
5. Let's write the identity in the form $$\sum_{i+j=n}\binom Bi\binom Wj\binom ni=\sum_k\binom Bk\binom Wk\binom{2k}n,$$ where $B$ and $W$ are two $n$-element sets. What I want to say is that both sides count ways to choose an $n$-element subset of $B\sqcup W$ with some kind of... extension (cf. two formulas for a trinomial coefficient, perhaps).
-
Oh, and if someone wants to try to google, LHS is called Franel numbers – Grigory M Nov 29 '13 at 21:53
– Grigory M Dec 1 '13 at 18:30

Suppose we seek to show that $$\sum_{k=0}^n {n\choose k}^3 = \sum_{k=\lceil n/2 \rceil}^n {n\choose k}^2 {2k\choose n}.$$

The RHS is $$\sum_{k=\lceil n/2 \rceil}^n {n\choose k} {2k\choose k} {k\choose n-k}.$$

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

and (this integral is zero when $0\le k\lt \lceil n/2\rceil$) $${k\choose n-k} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{k}}{w^{n-k+1}} \; dw$$

to get for the RHS

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} \sum_{k=0}^n {n\choose k} \frac{w^k(1+w)^k (1+z)^{2k}}{z^k} \; dw\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} \left(1+\frac{w(1+w)(1+z)^2}{z}\right)^n \; dw\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} (z+w(1+w)(1+z)^2)^n \; dw\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} (z+w(z+1))^n (1+w(z+1))^n \; dw\; dz.$$

Extracting first the residue in $w$ next the residue in $z$ we get

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{q=0}^n {n\choose q} z^{n-q} (1+z)^q {n\choose n-q} (1+z)^{n-q} \; dz \\ = \sum_{q=0}^n {n\choose q}^2 \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{q+1}} \; dz \\ = \sum_{q=0}^n {n\choose q}^3$$

QED.

-
Nice. Since you don't really use change of variables etc one can get rid of all integrals and get a slightly shorter version in the language of gen. functions. – Grigory M Jun 24 at 11:20

Suppose we have $n$ black cards and $n$ white cards and we want to divide cards into «good» and «bad» — in such way that there is the same number of bad cards of each color — and burn $n$ of bad cards.

(RHS) Obviously there are exactly $\sum\binom nk^2\binom{2k}n$ ways to do it: we choose $k$ bad black cards, $k$ bad white cards and burn $n$ bad cards.

(LHS) If we just want to choose what $n$ cards we burn — it can be done in $\sum_k\binom nk\binom n{n-k}$ ways: we choose $k$ black cards to burn and $n-k$ white cards to burn.

Let’s call bad white cards and good black cards «perverse». After we’ve burned that $n$ cards we need to choose exactly $k$ perverse cards (from the cards left): if we have $l$ good black cards, we've had $n-l$ bad white cards of which $(n-l)-(n-k)=k-l$ left.

So $$\sum\binom nk^2\binom{2k}n=\sum\binom nk\binom n{n-k}\binom nk.$$

// This is of course just a rewrite of an algebraic proof (based on Vandermonde convolution and aforementioned two presentations of the same trinomial coefficient) — namely, of the proof on p. 16 of V. Strehl’s «Binomial Identities...» (I’ve tried to look into the paper before — but missed it).

-
If you are still following this question you might want to look at my proof. – Marko Riedel Jun 24 at 1:38
Thank you, I'll take a look – Grigory M Jun 24 at 10:48