Emprically it looks like the following identity holds, but I haven't been able to prove it. Can anyone find a proof? $$ \binom{m+k}{k}\binom{n+k}{k}=\sum_{i\geq0}\binom{m}{i}\binom{n}{i}\binom{m+n+k-i}{k-i} $$ For some context, a corollary would be that the generating function for the LHS keeping $m$ and $n$ fixed is $$ \sum_{k\geq0}\binom{m+k}{k}\binom{n+k}{k}x^k=\frac{\sum_{i\geq0}\binom{m}{i}\binom{n}{i}x^i}{(1-x)^{m+n+1}} $$


2 Answers 2


We seek to prove that

$${m+k\choose k} {n+k\choose k} = \sum_{q\ge 0} {m\choose q} {n\choose q} {m+n+k-q\choose k-q}.$$

We start on the RHS with

$$\sum_{q\ge 0} {m\choose q} {n\choose n-q} {m+n+k-q\choose k-q} \\ = [z^n] (1+z)^n [w^k] (1+w)^{m+n+k} \sum_{q\ge 0} {m\choose q} z^q w^q (1+w)^{-q} \\ = [z^n] (1+z)^n [w^k] (1+w)^{m+n+k} \left(1+\frac{zw}{1+w}\right)^m \\ = [z^n] (1+z)^n [w^k] (1+w)^{n+k} (1+w+zw)^m \\ = [w^k] (1+w)^{n+k} [z^n] (1+z)^n (1+w(1+z))^m \\ = [w^k] (1+w)^{n+k} [z^n] (1+z)^n \sum_{q=0}^m {m\choose q} w^q (1+z)^q \\ = [w^k] (1+w)^{n+k} \sum_{q=0}^m {m\choose q} {n+q\choose q} w^q \\ = \sum_{q=0}^k {m\choose q} {n+q\choose q} {n+k\choose k-q}.$$

Observe that

$${n+q\choose q} {n+k\choose k-q} = \frac{(n+k)!}{q!\times n!\times (k-q)!} = {n+k\choose k} {k\choose q}.$$

We get

$${n+k\choose k} \sum_{q=0}^k {m\choose q} {k\choose q} = {n+k\choose k} \sum_{q=0}^k {m\choose q} {k\choose k-q} \\ = {n+k\choose k} [z^k] (1+z)^k \sum_{q=0}^k {m\choose q} z^q.$$

We may extend $q$ to infinity owing to the coeffcient extractor in $z$:

$${n+k\choose k} [z^k] (1+z)^k \sum_{q\ge 0} {m\choose q} z^q \\ = {n+k\choose k} [z^k] (1+z)^{m+k} = {n+k\choose k} {m+k\choose k}.$$

This is the claim.

  • $\begingroup$ Nice proof Marko. I'd not encountered coefficient extraction techniques before - very neat. Btw, once we reach $\binom{n+k}{k}\sum_{q=0}^k\binom{m}{q}\binom{k}{k-q}$ the final step follows immediately from Vandermonde's identity, right? $\endgroup$ Mar 15, 2019 at 5:20
  • $\begingroup$ Yes it would seem so. $\endgroup$ Mar 15, 2019 at 14:13

That is known as Suranyi's formula, and you can find a demonstration in this paper.
Also interesting is the context in which it is analyzed in this other paper.


You must log in to answer this question.

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