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

Question

I'm supopsed to show that if $m$ and $n$ are non-negative integers then

$$\sum_{k=0}^{n}(-1)^k {{m+1}\choose{k}}{{m+n-k}\choose{m}} = \left\{ \begin{array}{l l} 1 & \quad \text{if $n=0$}\\ 0 & \quad \text{if $n>0$} \end{array} \right.$$

I used mathematical induction about $n$, but I couldn't reach at the answer. Also, I tend to make the process to show this type of equality quite non-elegant, so I want a concise solution for this. Since the case of $n=0$ was already proved, you don't need to show it.

Answer 1

We may use convolution of generating functions:

Let \begin{align*} a_k &= (-1)^k\, \binom{m+1}{k} \\ b_k &= \binom{m+k}{m} \end{align*}

The corresponding g.fs are: \begin{align*} A(x) &= (1-x)^{m+1} \\ B(x) &= \frac{1}{(1-x)^{m+1}} \end{align*} Multiplying $A(x)$ and $B(x)$ \begin{align*} A(x)\cdot B(x) &= \sum_{n\ge 0} \left(\sum_{k=0}^{n} a_k\, b_{n-k}\right) x^n \\ &= \frac{(1-x)^{m+1}}{(1-x)^{m+1}} \\ &= 1 \end{align*}

which verifies that the sum is $1$ only when $n=0$