$ \sum_{k=0}^n (-1)^{k} {{m+1}\choose k }{{m+n-k}\choose m }= 0$ if $n>0$

Question

I need to show that $ \sum_{k=0}^n (-1)^{k} {{m+1}\choose k }{{m+n-k}\choose m }= 0 $ if $n>0$. Here $m$ is a non negative integer.

I am thinking induction, but do I apply it on $m$ or $n$? I have tried both. Please help.

Answer 1

Starting from

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

we find

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

Now we may extend $k$ beyond $n$ because of the factor $z^k$ and the coefficient extractor $[z^n]$ in front:

$$[z^n] (1+z)^{m+n} \sum_{k\ge 0} (-1)^k {m+1\choose k} z^k (1+z)^{-k} \\ = [z^n] (1+z)^{m+n} \left(1-\frac{z}{1+z}\right)^{m+1} = [z^n] (1+z)^{n-1} = 0.$$

Answer 2

Also, we can write it as $$ \eqalign{ & \sum\limits_{0\, \le \,k\, \le \,n} {\left( { - 1} \right)^{\,k} \left( \matrix{ m + 1 \cr k \cr} \right)\left( \matrix{ m + n - k \cr m \cr} \right)} \quad \left| {\,0 \le m} \right.\quad = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{ m + 1 \cr k \cr} \right)\left( \matrix{ m + n - k \cr n - k \cr} \right)} = \quad \quad (1)\cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( \matrix{ k - m - 2 \cr k \cr} \right)\left( \matrix{ m + n - k \cr n - k \cr} \right)} = \quad \quad (2) \cr & = \left( \matrix{ n - 1 \cr n \cr} \right)\quad \quad \quad \quad (3) \cr} $$ where:
-(1) we can apply "symmetry" since $m$ and $n-k$ are non negative;
-(2) upper negation, and we can omit the bounds because implicit in the binomials;
-(3) "double convolution".