5
$\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
  • $\begingroup$ Searching with Approach Zero you can find several references to this identity, for example here. You just need to tweak a little the index and variables. This is [Li Shanlan identity](en.wikipedia.org/wiki/… $\endgroup$ – BillyJoe Feb 19 at 8:56
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$ – Markus Scheuer Feb 19 at 22:07
  • $\begingroup$ Thanks! This one worked using formal power series only so we were able to keep it simple. $\endgroup$ – Marko Riedel Feb 19 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$ – Markus Scheuer Feb 19 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.