I am struggling to prove the following combinatorial identities: $$(1)\quad\sum_{r=0}^m \binom{m}{r}\binom{n}{r}\binom{p+r}{m+n} = \binom{p}{m}\binom{p}{n},\quad \forall n\in\mathbb N,p\ge m,n$$ $$(2)\quad\sum_{r=0}^m \binom{m}{r}\binom{n}{r}\binom{p+m+n-r}{m+n} = \binom{p+m}{m}\binom{p+n}{n},\quad \forall p\in\mathbb N$$ The book I found them in says they were discovered and proved by Chinese mathematician Li Shanlan in the 19th century but I have failed to find any of his works translated into English in the Internet.

I am looking for an either combinatorial or algebraic solution.

  • $\begingroup$ What's the book title? $\endgroup$ – zhoraster Oct 2 '15 at 12:12
  • $\begingroup$ Principles and Techniques in Combinatorics by Chen Chuan-Chong. $\endgroup$ – Artyom Dmitriev Oct 2 '15 at 12:35
  • $\begingroup$ The first of these looks to be a duplicate and was discussed at this MSE link. $\endgroup$ – Marko Riedel Oct 2 '15 at 20:48

Solution for $(1)$:

$$\begin{align} \sum_{r=0}^m \binom{m}{r}\binom{n}{r}\color{blue}{\binom{p+r}{m+n}} &=\sum_{r=0}^m \binom{m}{r}\binom{n}{r}\color{blue}{\sum_{j}\binom{p}{m+j}\binom r{n-j}}\\ &= \sum_{r=0}^m\sum_{j} \binom{m}{r}\binom{p}{m+j}\color{orange}{\binom{n}{r}\binom r{n-j}}\\ &= \sum_{r=0}^m\sum_{j} \binom{m}{r}\binom{p}{m+j}\color{orange}{\binom{n}{n-j}\binom j{r-n+j}}\\ &= \sum_{r=0}^m\sum_{j} \binom{m}{r}\binom{p}{m+j}\color{orange}{\binom nj\binom j{n-r}}\\ &= \sum_{j} \binom{p}{m+j}\binom nj\color{purple}{\sum_{r=0}^m\binom{m}{r}\binom j{n-r}}\\ &= \sum_{j} \binom{p}{m+j}\binom nj\color{purple}{\binom{m+j}n}\\ &= \sum_{j} \color{green}{\binom{p}{m+j}\binom{m+j}n}\binom nj\\ &= \color{green}{\binom pn}\sum_{j} \color{green}{\binom{p-n}{p-m-j}}\binom nj\\ &= \binom pn\binom{p}{p-m}\\ &=\binom pn \binom pm=\binom pm \binom pn\qquad\blacksquare \end{align}$$

Solution for $(2)$:

Put $\; p=1-q\;$ in $(1)$ above: $$\begin{align} \sum_{r=0}^m\binom mr \binom nr\binom {1-q+r}{m+n} &=\binom {1-q}m\binom {1-q}n \\ \sum_{r=0}^m\binom mr \binom nr (-1)^{m+n}\binom {m+n+q-r}{m+n} &=(-1)^m\binom {m+q}m (-1)^n\binom {m+q}n \qquad\text{using upper negation} \\ \sum_{r=0}^m \binom mr\binom nr \binom {m+n+q-r}{m+n} &=\binom {m+q}m \binom{n+q}n \\ \sum_{r=0}^m \binom mr\binom nr \binom {m+n+p-r}{m+n} &=\binom {p+m}m\binom {p+n}n \quad \text{putting $p$ for $q$ WLOG}\qquad\blacksquare\end{align}$$

  • $\begingroup$ Can we ignore actual values for j? It seems that at first j should have values from -m to n, but at the end it iterates from 0 to p - m. $\endgroup$ – Artyom Dmitriev Oct 2 '15 at 16:59
  • 1
    $\begingroup$ @ArtyomDmitriev, in fact, in the first line it gives non-zero values for $j$ from $n-r$ to $(p-m)\wedge n$. The same in the end, after you changed the order of summation (note that the upper limit is even preserved). However, I recommend you not to care about this at all. The expression is zero outside this range, that's it. $\endgroup$ – zhoraster Oct 2 '15 at 17:21

Assume $n\geq m$. $\binom{p}{n}\binom{p}{m}$ is the coefficient of the monomial $x^n y^m$ in the expansion of $(1+x)^p(1+y)^p=(1+x+y+xy)^p$, i.e. the coefficient of $x^n y^m$ in:

$$ \sum_{k=0}^{p}\binom{p}{k}(x+y+xy)^k=\sum_{k=0}^{p}\binom{p}{k}\sum_{j=0}^{k}\binom{k}{j}x^j y^j (x+y)^{k-j}$$ and we may restrict the last sum over $m+n=k+j$, having: $$ \sum_{j=0}^{m}\sum_{\substack{k\geq j \\ k+j=m+n}}\binom{k}{j}\binom{p}{k}\binom{k-j}{n-j}=\sum_{j=0}^{m}\binom{m+n-j}{j}\binom{p}{m+n-j}\binom{m+n-2j}{n-j} $$ that can be rearranged in the wanted form $(1)$.

  • $\begingroup$ Sorry, I don't see how it can be rearranged... What I get upon rearranging it so it fits most closely is $$ \frac{{n\choose j}{m\choose j}{m+n\choose n}{p+j\choose m+n}}{{p+j\choose j}} $$ $\endgroup$ – zhoraster Oct 2 '15 at 16:11

Very striking identities. Hard to guess how Li Shanlan discovered them...

Concerning (1), multiply by $x^n y^m z^p$ and add up.

In the rhs we have $$ \sum_{p\ge 0}z^p\sum_{n=0}^p {p \choose n} x^n \sum_{m=0}^p {p \choose m} y^m = \sum_{p\ge 0}(1+x)^p(1+y)^p z^p = \frac{1}{1-z(1+x)(1+y)}. $$ The lhs is tougher. Denoting $t = \frac{z}{1-z}$, $$ \sum_{r\ge 0}\sum_{n\ge r}{n\choose r}x^n \sum_{m\ge r}{m\choose r}y^m \sum_{p\ge m+n-r} {p+r\choose m+n}z^p \\ = \sum_{r\ge 0}\sum_{n\ge r}{n\choose r}x^n \sum_{m\ge r}{m\choose r}y^m\frac{z^{m+n-r}}{(1-z)^{m+n+1}} = \sum_{r\ge 0}\frac1{z^r(1-z)}\sum_{n\ge r}{n\choose r}(tx)^n \sum_{m\ge r}{m\choose r}(ty)^m\\ = \sum_{r\ge 0}\frac1{z^r(1-z)}\frac{(tx)^r}{(1-tx)^{r+1}}\frac{(ty)^r}{(1-ty)^{r+1}} = \frac{1}{(1-z)(1-tx)(1-ty)}\frac{1}{1-\frac{1}{z}\frac{tx}{1-tx}\frac{ty}{1-ty}}\\ = \frac{1}{(1-tx)(1-ty)\left(1-z-\frac{txy}{(1-tx)(1-ty)}\right)} = \frac{1}{(1-z)(1-tx)(1-ty) - txy}\\ = \frac{1}{(1-z-xz)(1-ty) - txy} = \frac{1}{1-xz -yz - txy + txyz} \\ = \frac{1}{1-z-xz -yz - xyz} = \frac{1}{1-z(1+x)(1+y)}. $$

  • $\begingroup$ Now that is a dirty snake-oil trick. Nice! $\endgroup$ – vonbrand Oct 2 '15 at 18:00
  • 1
    $\begingroup$ @vonbrand, I'll take it as a compiment. But isn't such use of gf's standard for proving identities like this? BTW, a horrible lot of transformations in hypergeometrics's and my answers hints that there is no simple combinatorial argument. This again raises the question: how on Earth did Li Shanlan write this? $\endgroup$ – zhoraster Oct 2 '15 at 18:39
  • $\begingroup$ standard us to use one indeterminate, not three. $\endgroup$ – vonbrand Oct 3 '15 at 11:41

Suppose we seek to verify that $$\sum_{r=0}^{\min\{m,n,p\}} {m\choose r} {n\choose r} {p+m+n-r\choose m+n} = {p+m\choose m} {p+n\choose n}.$$

Introduce $${n\choose r} = {n\choose n-r} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-r+1}} (1+z)^n \; dz$$

and $${p+m+n-r\choose m+n} = {p+m+n-r\choose p-r} \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{p-r+1}} (1+w)^{p+m+n-r} \; dw.$$

Observe carefully that the first of these is zero when $r\gt n$ and the second one when $r\gt p$ so we may extend the range of $r$ to infinity.

This yields for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{p+m+n}}{w^{p+1}} \sum_{r\ge 0} {m\choose r} z^r \frac{w^r}{(1+w)^r} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{p+m+n}}{w^{p+1}} \left(1+\frac{zw}{1+w}\right)^m \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{p+n}}{w^{p+1}} (1+w+zw)^m \; dw \; dz.$$

The inner integral is $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{p+n}}{w^{p+1}} \sum_{q=0}^m {m\choose q} (1+z)^q w^q \; dw$$

with residue $$\sum_{q=0}^{\min(m,p)} {m\choose q} {p+n\choose p-q} (1+z)^q$$

which in combination with the outer integral yields $$\sum_{q=0}^{\min(m,p)} {m\choose q} {p+n\choose n+q} {n+q\choose n}.$$

Now note that $${p+n\choose n+q} {n+q\choose n} = \frac{(p+n)!}{(p-q)! (n+q)!} \frac{(n+q)!}{q! n!} \\ = \frac{(p+n)!}{(p-q)! p!} \frac{p!}{q! n!} = {p+n\choose n} {p\choose q}.$$

Therefore we just need to verify that $$\sum_{q=0}^{\min(m,p)} {m\choose q} {p\choose p-q} = {p+m\choose m}$$

which follows by inspection.

It can also be done with the integral $${p\choose p-q} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{p}}{w^{p-q+1}} \; dw$$

which is zero when $q\gt p$ so we can extend $q$ to infinity to get for the sum $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{p}}{w^{p+1}} \sum_{q\ge 0} {m\choose q} w^q \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{p+m}}{w^{p+1}} \; dw \\ = {p+m\choose m}.$$


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.