Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?..

Comments and thoughts

  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).
share|cite|improve this question
Oh, and if someone wants to try to google, LHS is called Franel numbers – Grigory M Nov 29 '13 at 21:53
Cf Dixon's identity – Grigory M Dec 1 '13 at 18:30
up vote 2 down vote accepted

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


share|cite|improve this answer
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 '15 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).

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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