A nice proof of the identity $\sum_{i=0}^{l+1}(-1)^i\binom{n+i}{l}\binom{l+1}{i}=0$

Question

The identity $$\sum_{i=0}^{n}(-1)^i\binom{n}{i}=0$$ has a nice proof: notice that the LHS equals $(1-1)^n$.

Today, I came across the identity $$\sum_{i=0}^{l+1}(-1)^i\binom{n+i}{l}\binom{l+1}{i}=0$$

For instance, $$\binom{n}{2}-3\binom{n+1}{2}+3\binom{n+2}{2}-\binom{n+3}{2}=0$$.

Is there a proof of this identity in a similar vein?

Answer 1

Here is a technique using the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ 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 \begin{align*} \color{blue}{\sum_{i=0}^{l+1}}&\color{blue}{(-1)^i\binom{n+i}{l}\binom{l+1}{i}}\\ &=\sum_{i=0}^{l+1}\binom{l+1}{i}(-1)^i[z^l](1+z)^{n+i}\tag{2}\\ &=[z^l](1+z)^n\sum_{i=0}^{l+1}\binom{l+1}{i}(-1)^i(1+z)^i\tag{3}\\ &=[z^l](1+z)^n(1-(1+z))^{l+1}\\ &=[z^l](1+z)^n(-z)^{l+1}\tag{4}\\ &\,\,\color{blue}{=0} \end{align*} and the claim follows.

Comment:

• In (2) we apply the coefficient of operator as in (1).

• In (3) we use the linearity of the coefficient of operator.

• In (4) we see that each term with $z$ has an exponent greater than $l$.

Answer 2

Just fleshing out Jean-Claude Arbaut's answer for my own sake:

Let $\Delta$ be the operator that takes $u(x)\mapsto u(x+1)-u(x)$. Then, inductively:

$$\Delta^l (u)(x)=\Delta^{l-1}(u)(x+1)-\Delta^{l-1}(u)(x)$$ $$=\sum_{i=0}^l(-1)^i\binom{l}{i}u(x+1+i)-\sum_{i=0}^l(-1)^i\binom{l}{i}u(x+i)$$ $$=\sum_{i=1}^{l+1}(-1)^{i-1}\binom{l}{i-1}u(x+i)-\sum_{i=0}^l(-1)^i\binom{l}{i}u(x+i)$$ $$=\sum_{i=0}^{l+1}(-1)^{i-1}\binom{l+1}{i}u(x+i)$$

Now set $u(x)=\binom{x}{l}$. This has degree $l$ so $$0=\Delta^l(u)(x)=\sum_{i=0}^{l+1}(-1)^{i-1}\binom{l+1}{i}\binom{x+i}{l}$$

which is what I wanted, for $x=n$.

Answer 3

This is an alternative using combinatorial argument.

Set Up

$n$ students and $l+1$ teachers are going to an amusement park. The park's official is eccentric and decides to limit the number of teachers who can enter to $i$. However, $l$ of those who enter the park get free beverages. The number of possibilities for a given $i$ is given by (almost) the summand:

$$ \binom{l+1}{i}\binom{n+i}{l} $$

The LHS is then simply the difference in number of possibilities in which even or odd number of teachers enter the park:

$$ \sum_{i=0}^{l+1}\left(-1\right)^{i}\binom{l+1}{i}\binom{n+i}{l} $$

Alternative Counting

The park official can choose $l$ out of $n+l+1$ people who get free beverages. Teachers who get free beverages can enter the park. Some teachers who don't get free beverages can also enter the park.

Since only $l$ free beverages are available, there is at least a teacher who does not get free beverage, i.e. this is a non-empty set. It is well-known that a non-empty set has as many odd subset as even subset. Therefore, there are equal number of possibilities in which even number / odd number of teachers enter the park.

$$ \sum_{i=0}^{l+1}\left(-1\right)^{i}\binom{l+1}{i}\binom{n+i}{l}=0 $$

Generalization

Using the same argument, the following holds for any positive integer $m$:

$$ \sum_{i=0}^{l+m}\left(-1\right)^{i}\binom{l+m}{i}\binom{n+i}{l}=0 $$