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

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.

-
Have you tried a combinatoric proof using the inclusion/exclusion principle ? – Lucian May 31 '14 at 9:34

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$

-
Thanks! I especially wanted to know a proof using generating function like this one. – Math.StackExchange Jun 1 '14 at 22:02
You are welcome! – gar Jun 2 '14 at 3:20