5
$\begingroup$

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

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
  • $\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
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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