Identity involving product of two binomial coefficients

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.


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.