# Prove an identity for finite sum of product of three binomial coefficients

I have the identity $$\sum_{n=0}^p \sum_{m=0}^p (-1)^{n+m} \left(\begin{array}{c} l + p \\ l+n \end{array}\right) \left(\begin{array}{c} l + n+m \\ n \end{array}\right) \left(\begin{array}{c} p \\ m \end{array}\right) = 1$$ where $$l,p,n,m \in \mathbb{Z}_0^+$$ are all non-negative integers and $$l\leq p$$, which I know holds from a physics based argument. Numerically it seems to hold for all cases I've tested too. I'm struggling to prove this from a mathematical perspective though, e.g. using properties of binomial coefficients.

Using the definition of the hypergeometric function and falling factorials I can do one, or other, of the summations giving for the left hand side (verified with Mathematica) $$\sum_{m=0}^p (-1)^m \left(\begin{array}{c} l + p \\ p \end{array}\right) \left(\begin{array}{c} p \\ m \end{array}\right) {}_2F_1(l+m+1,-p,l+1,1)$$ when summing over $$n$$, or alternatively $$\sum_{n=0}^p (-1)^n \left(\begin{array}{c} l + n \\ n \end{array}\right) \left(\begin{array}{c} l+p \\ l+n \end{array}\right) {}_2F_1(l+n+1,-p,l+1,1)$$ when summing over $$m$$, but I don't know how to do the final summation. Any help would be appreciated.

We want to show \begin{align*} \color{blue}{\sum_{n=0}^p}\,&\color{blue}{\sum_{m=0}^p(-1)^{n+m} \binom{l+p}{l+n}\binom{l+n+m}{n}\binom{p}{m}=1}\tag{1} \end{align*}

Here we use a technique that can be found in the classic Integral Representation and the Computation of Combinatorial Sums by G. P. Egorychev. In order to do so we write the binomial coefficient $$\binom{p}{m}$$ as residue of a meromorphic function, namely \begin{align*} \color{blue}{\binom{p}{m}}&=\frac{p!}{m!(p-m)!}=(-1)^{p-m}p!\left(\prod_{q=0}^{m-1}\frac{1}{m-q}\right) \left(\prod_{q=m+1}^n\frac{1}{m-q}\right)\\ &\,\,\color{blue}{=(-1)^{p-m}p!\operatorname{res}_{z=m}\prod_{q=0}^p\frac{1}{z-q}}\tag{2}\\ \end{align*}

We start with the inner sum of (1) and show \begin{align*} \color{blue}{\sum_{m=0}^p(-1)^m\binom{l+n+m}{n}\binom{p}{m}=(-1)^p[[p=n]]}\tag{3} \end{align*} where we use Iverson brackets indicating the sum is $$(-1)^p$$ iff $$p=n$$ and zero otherwise.

Note: A shorter path to show (3) is provided by the answer from @MarkoRiedel. We obtain \begin{align*} \color{blue}{\sum_{m=0}^p}&\color{blue}{(-1)^m\binom{l+n+m}{n}\binom{p}{m}}\\ &=\sum_{m=0}^p(-1)^p\binom{p}{m}\frac{1}{n!}\prod_{j=0}^{n-1}(l+n+m-j)\tag{4.1}\\ &=\sum_{m=0}^p(-1)^p\frac{p!}{n!}\underbrace{\operatorname{res}_{z=m} \left(\prod_{j=0}^{n-1}(l+n+z-j)\prod_{q=0}^p\frac{1}{z-q}\right)}_{=f(z)}\tag{\to\ (2)}\\ &=\sum_{m=0}^p(-1)^p\frac{p!}{n!}\left(-\operatorname{res}_{z=\infty}f(z)\right)\tag{4.2}\\ &=\sum_{m=0}^p(-1)^p\frac{p!}{n!}\operatorname{res}_{z=0} \left(\frac{1}{z^2}f\left(\frac{1}{z}\right)\right)\tag{4.3}\\ &=\sum_{m=0}^p(-1)^p\frac{p!}{n!}\lim_{z\to 0}\left(\frac{1}{z}\prod_{j=0}^{n-1}(l+n+\frac{1}{z}-j)\prod_{q=0}^p\frac{1}{\frac{1}{z}-q}\right)\\ &=\sum_{m=0}^p(-1)^p\frac{p!}{n!}\lim_{z\to 0}\left(z^{p-n}\prod_{j=0}^{n-1}\left(1+(l+n-j)z\right) \left(\prod_{q=0}^p\frac{1}{1-qz}\right)\right)\\ &=\sum_{m=0}^p(-1)^p\frac{p!}{n!}\lim_{z\to 0}z^{p-n}\tag{4.4}\\ &\,\,\color{blue}{=(-1)^p[[p=n]]} \end{align*} and the claim (3) follows.

Comment:

• In (4.1) we use $$\binom{p}{m}=\frac{1}{m!}p(p-1)\cdots(p-m+1)$$.

• In (4.2) we use the sum of the residues of a meromorphic function at the poles $$z=q, 0\leq q\leq p$$ plus the residue at $$\infty$$ sum up to zero. This way we get rid of the sum and what is left is just the residue at $$z=\infty$$.

• In (4.3) we use the identity \begin{align*} \operatorname{res}_{z=\infty}f(z)=\operatorname{res}_{z=0}\left(-\frac{1}{z^2}f\left(\frac{1}{z}\right)\right) \end{align*} which transforms a residue at infinity to a residue at zero.

• In (4.4) we do some simplifications

Using (3) we obtain \begin{align*} \color{blue}{\sum_{n=0}^p}\,&\color{blue}{\sum_{m=0}^p(-1)^{n+m} \binom{l+p}{l+n}\binom{l+n+m}{n}\binom{p}{m}}\\ &=\sum_{n=0}^{p}(-1)^n\binom{l+p}{l+n}\sum_{m=0}^p(-1)^m\binom{p}{m}\binom{l+n+m}{n}\\ &=\sum_{n=0}^{p}(-1)^n\binom{l+p}{l+n}(-1)^p[[p=n]]\tag{\to (3)}\\ &=(-1)^p\binom{l+p}{l+p}(-1)^p\\ &\,\,\color{blue}{=1} \end{align*} and the claim (1) follows.

• Interesting proof. Some aspects that I am less familiar with in there, but it certainly seems to check out. Since I was after an alternative proof to my own, I will go ahead and accept your answer. Thanks! Aug 15, 2022 at 14:42
• @George: You're welcome. Good to see tbe answer is useful. :-) Aug 15, 2022 at 14:48
• Indeed it was. Presumably this implies that the hypergeometric function with binomial prefactor appearing in the second summation in my original post simplifies drastically i.e. $\binom{l+n}{n} {}_2F_1(l+n+1,−p,l+1,1) = (-1)^p [[p=n]]$, a point I did not notice. Aug 15, 2022 at 14:56
• @epi163sqrt Sometimes we may want to keep it simple. ;-) Aug 16, 2022 at 21:12

What follows is a remark concerning the answer by @epi163sqrt. In seeking to show that

$$\sum_{n=0}^p \sum_{m=0}^p (-1)^{n+m} {l+p\choose l+n} {l+n+m\choose n} {p\choose m} = 1$$

we write

$$\sum_{n=0}^p {l+p\choose l+n} (-1)^n \sum_{m=0}^p (-1)^{m} {l+n+m\choose n} {p\choose m} = 1.$$

We get for the inner sum

$$\;\underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} (1+z)^{l+n} \sum_{m=0}^p (-1)^m (1+z)^m {p\choose m} \\ = \;\underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} (1+z)^{l+n} (1-(1+z))^p \\ = (-1)^{p} \;\underset{z}{\mathrm{res}}\; \frac{1}{z^{n-p+1}} (1+z)^{l+n}.$$

Note that the residue is zero when $$p\gt n$$ (as is the case in all but one term in the outer sum) and one when $$p=n$$. Hence using an Iverson bracket we find $$(-1)^p [[p=n]]$$ as long as $$0\le n\le p.$$ From this point on we may continue as before.

• I agree. Your approach is definitely simpler. :-) Many thanks for providing it. (+1) Aug 16, 2022 at 21:25

One way to prove this, which essentially comes from my original physics argument, is using the orthogonality of the Laguerre polynomials (LP). Specifically we can write an LP in series form as $$L_p^l(x) = \sum_{n=0}^p (-1)^n \binom{p+l}{p+n} \frac{x^n}{n!}.$$

The orthogonality of the LPs reads: $$\int_0^\infty x^l e^{-x} L_p^l(x) L_q^l = \frac{\Gamma(p+l+1)}{p!} \delta_{pq}.$$ Taking $$p=q$$ and substituting in the series representation gives $$\sum_{n=0}^p\sum_{m=0}^p \frac{(-1)^{n+m}}{n!m!} \binom{p+l}{p+n}\binom{p+l}{p+m} \int_0^\infty x^{l+n+m} e^{-x} dx = \frac{(p+l)!}{p!}$$ since I have assumed $$p,l$$ are non-negative integers, so I can replace the gamma function with its factorial representation. The integral term gives $$\Gamma(l+n+m+1)$$ whereby rearranging gives $$\sum_{n=0}^p\sum_{m=0}^p (-1)^{n+m}\frac{p!(l+n+m)!}{(p+l)!n!m!} \binom{p+l}{p+n}\binom{p+l}{p+m} = 1.$$

Using the definition of the binomial coefficient it then follows that $$\sum_{n=0}^p\sum_{m=0}^p (-1)^{n+m}\binom{l+p}{l+n}\binom{l+m+n}{n}\binom{p}{m} = 1.$$

Alternative proofs welcome.