6
$\begingroup$

I believe the following identity holds for any non-negative integers $m,k$:

$$\binom{m+k}{k}^2 = \sum_{n=0}^m \binom{k}{m-n}^2\binom{2k+n}{n}.$$

It seems like there should be a slick double counting way of proving it, but I am not able to see it. I got this identity because I believe the following power series equality holds for $|x| < 1$,

$$(1-x)^{2k-1} \sum_{m=0}^\infty \binom{m+k-1}{k-1}^2 x^m = \sum_{j=0}^{k-1} \binom{k-1}{j}^2 x^j. $$

The binomial identity above comes from dividing by $(1-x)^{2k-1}$, applying the binomial theorem replacing $k$ with $k+1$ and comparing the coefficients of both sides.

But this power series equality doesn't seem any easier to prove than the binomial coefficient identity, since I don't really have a handle on the sums on either side.

Does anyone know a reference for an identity of this nature or have an idea for a double counting argument?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Permit me to contribute an algebraic proof. We seek

$${m+k\choose k}^2 = \sum_{q=0}^m {k\choose m-q}^2 {2k+q\choose q}$$

Starting with the RHS we find

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

Now we may extend $q$ to infinity because the coefficient extractor $[w^m]$ enforces the upper limit. We get

$$[z^k] (1+z)^k [w^m] (1+w)^{2k+m} \sum_{q\ge 0} {k\choose q} z^q w^q (1+w)^{-q} \\ = [z^k] (1+z)^k [w^m] (1+w)^{2k+m} (1 + zw/(1+w))^k \\ = [z^k] (1+z)^k [w^m] (1+w)^{k+m} (1 + w + zw)^k$$

Re-expanding we find

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

We may set the upper limit of the sum to $m.$ (If $k\lt m$ the values $k\lt q\le m$ produce zero from the binomial coefficient and we may raise $q$ to $m.$ If $k\gt m$ the values $m\lt q\le k$ produce zero by the coefficient extractor $[w^m]$ and we may lower $q$ to $m.$) We get

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

Now observe that

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

This yields for our sum

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

Using Vandermonde we obtain at last

$$\bbox[5px,border:2px solid #00A000]{ {m+k\choose k}^2.}$$

$\endgroup$
3
  • $\begingroup$ Nice and instructive derivation. (+1) $\endgroup$ Feb 19, 2021 at 22:07
  • $\begingroup$ Thanks! This one worked using formal power series only so we were able to keep it simple. $\endgroup$ Feb 19, 2021 at 22:10
  • $\begingroup$ Yes, I see. Nevertheless it's always both astonishing and a pleasure for me to see the nice binomial identities we derive in intermediate steps together with their generating functions. $\endgroup$ Feb 19, 2021 at 22:14

You must log in to answer this question.

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