Find the properties of the sum $\sum_{k=0}^n (-1)^k\binom{m+1}{k}\binom{m+n-k}{n-k}$

Question

I have to show that $$\displaystyle\sum\limits_{k=0}^n (-1)^k\binom{m+1}{k}\binom{m+n-k}{n-k} = \begin{cases} 1\ \text{if}\ n=0 \\ 0\ \text{if}\ n>0 \end{cases}$$

My try: I have tried to use snake oil method $$\sum_{k=0}^n \binom{m+1}{k}\binom{m+n-k}{n-k}$$ $$=\sum_m{\sum_{k=0}^n \binom{m+1}{k}\binom{m+n-k}{n-k}}x^m$$ $$={\sum_{k=0}^n(-1)^k \binom{m+1}{k}\sum_m\binom{m+n-k}{n-k}}x^m$$ We know that the second sum $\frac{1}{(1-x)^{1+n-k}}=\sum_m\binom{m+n-k}{n-k}x^m$ $$=\sum_{k=0}^n(-1)^k\binom{m+1}{k}\frac{1}{(1-x)^{1+n-k}}$$$$=\frac{1}{(1-x)^{1+n}}\sum_{k=0}^n(-1)^k\binom{m+1}{k}(1+x)^k$$ How should I proceed after that?

Edit: My method might be absolutely wrong so if anyone might show me some other method I would really appreciate it

Answer 1

No need for snake oil here. Just negate the upper index using this identity:

$$\binom{r}{j} = (-1)^j \binom{j-r-1}{j},\quad \text{integer }j.$$

We get

$$\sum\limits_{k=0}^n (-1)^k\binom{m+1}{k}\binom{m+n-k}{n-k} = (-1)^n\sum_k \binom{m+1}{k}\binom{-m-1}{n-k}.$$

Now this is just a Vandermonde convolution: the result is

$$(-1)^n\binom{(m+1)+(-m-1)}{n} = (-1)^n\binom{0}{n}.$$

Done. This is $0$ for $n > 0$ and $1$ for $n=0$.

Answer 2

Note: Here we show that the snake oil method which was applied by OP does also work.

Let $S_m(n)$ denote the series \begin{align*} S_m(n)=\sum_{k=0}^n(-1)^k\binom{m+1}{k}\binom{m+n-k}{n-k}\qquad\qquad m,n\geq 0 \end{align*}

The following is valid for $m\geq 0$ \begin{align*} S_m(n)= \begin{cases} 1\qquad&\qquad n=0\\ 0\qquad &\qquad n>0 \end{cases} \end{align*}

We obtain \begin{align*} \sum_{n=0}^\infty S_m(n)x^n&=\sum_{n=0}^\infty \sum_{k=0}^n(-1)^k\binom{m+1}{k}\binom{m+n-k}{n-k}x^n\\ &=\sum_{k=0}^\infty(-1)^k\binom{m+1}{k}\sum_{n=k}^\infty\binom{m+n-k}{n-k}x^n\tag{1}\\ &=\left(\sum_{k=0}^\infty(-1)^k\binom{m+1}{k}x^k\right)\left(\sum_{n=0}^\infty\binom{m+n}{n}x^n\right)\tag{2}\\ &=(1-x)^{m+1}\sum_{n=0}^\infty\binom{-(m+1)}{n}(-1)^nx^n\tag{3}\\ &=\frac{(1-x)^{m+1}}{(1-x)^{m+1}}\tag{4}\\ &=1 \end{align*} and the claim follows.

Comment:

• In (1) we exchange the sums and factor out which does not depend on the inner sum.

• In (2) we shift the index $n$ of the inner sum so that it starts from $0$. We factor out $x^k$ (from $x^{n+k}$) and observe the sums are now separated.

• In (3) we apply the binomial theorem to the left-hand sum and use the identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{q}(-1)^q \end{align*}

• In (4) we apply the binomial series expansion and the result is $1+0x+0x^2+\cdots$