The double sum $\sum_{j=0}^{n} \sum_{i=0}^{m} (-1)^{i+j} {m \choose i} {n \choose j} {i+j \choose i} =0~ \mbox{or}~1$

Question

For non-negative integers $m$ and $n$, the double sum $$\sum_{j=0}^{n} \sum_{i=0}^{m} (-1)^{i+j} {m \choose i} {n \choose j} {i+j \choose i}$$ can be checked to be 0 or 1. How can one show this by hand, along with the conditions on $m$ and $n$?

Answer 1

The Laguerre Polynomials are defined as $$L_n(x)=\sum_{j=0}^{n} (-1)^{j} \frac{{n \choose j}}{j!} x^J,~~~(1)$$ these are well known to follow the orthogonality condition as $$\int_{0}^{\infty} e^{-x} L_m(x)~ L_n(x)~ dx=\delta_{m,n}~,~~~~(2)$$ where $\delta_{m,n}$ is the Kroneckor delta function, If we insert (1) in (2), we get $$\int_{0}^{\infty}\sum_{i=0}^{m} \sum_{0}^{n} (-1)^{i+j} \frac{{m \choose i}}{i!} \frac{{n \choose j}}{j!} x^{i+j} e^{-x}~ dx= \delta_{m,n}.$$ Finally, $\int_{0}^{\infty} x^k e^{-x}~dx= k!$, leads to $$\sum_{i=0}^{m} \sum_{j=0}^{n} (-1)^{i+j} {m \choose i} {n \choose j} {i+j \choose i} = \delta_{m,n}.$$ Hence the result.

Answer 2

This is a slight variation of @MarkoRiedels nice answer. We use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ of a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n }{k}\tag{1} \end{align*}

We obtain for integral $m,n\geq 0$: \begin{align*} \color{blue}{\sum_{p=0}^n}&\color{blue}{\sum_{q=0}^m(-1)^{p+q}\binom{n}{p}\binom{m}{q}\binom{p+q}{q}}\\ &=\sum_{p=0}^n\binom{n}{p}(-1)^p\sum_{q=0}^m\binom{m}{q}(-1)^q[z^q](1+z)^{p+q}\tag{2}\\ &=[z^0]\sum_{p=0}^n\binom{n}{p}(-1)^p(1+z)^p\sum_{q=0}^m\binom{m}{q}\left(-\frac{1+z}{z}\right)^q\tag{3}\\ &=[z^0]\sum_{p=0}^n\binom{n}{p}(-1)^p(1+z)^p\left(1-\frac{1+z}{z}\right)^m\tag{4}\\ &=(-1)^m[z^m]\sum_{p=0}^n\binom{n}{p}(-1)^p(1+z)^p\tag{5}\\ &=(-1)^m[z^m]\left(1-(1+z)\right)^n\\ &=(-1)^{m+n}[z^m]z^n\\ &\,\,\color{blue}{=[[m=n]]}\tag{6} \end{align*}

and the claim follows.

Comment:

• In (2) we use the coefficient of operator according to (1).

• In (3) we do some rearrangements and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (4) we apply the binomial theorem.

• In (5) we do some simplifications and apply the rule from (3) again.

• In (6) we use Iverson Brackets.

Answer 3

Starting from

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

we write

$$\sum_{p=0}^n (-1)^{p} {n\choose p} \sum_{q=0}^m (-1)^{m-q} {m\choose q} {p+m-q\choose m-q} \\ = \sum_{p=0}^n (-1)^{p} {n\choose p} (-1)^m [z^m] (1+z)^{p+m} \sum_{q=0}^m (-1)^{q} {m\choose q} z^q (1+z)^{-q} \\ = \sum_{p=0}^n (-1)^{p} {n\choose p} (-1)^m [z^m] (1+z)^{p+m} \left(1-\frac{z}{1+z}\right)^m \\ = (-1)^m [z^m] \sum_{p=0}^n (-1)^{p} {n\choose p} (1+z)^{p} \\ = (-1)^m [z^m] (1-(1+z))^n = (-1)^{m+n} [z^m] z^n = (-1)^{m+n} \delta_{n,m} = \delta_{n,m}.$$