# Identity involving product of two binomial coefficients

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

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.

• 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? Mar 15, 2019 at 5:20
• Yes it would seem so. 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.