Combinatorial interpretation of an alternating binomial sum Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove this will be appreciated but a combinatorial solution is greatly preferred. Thanks for your help.
 A: Rewrite the identity with the index of summation changed from $i$ to $j$ where $j=i-k+1$:
$$\sum_{j=1}^{n+1-k}(-1)^{j-1}\binom{n+1}{k+j}\binom{k+j-1}k=1.$$
Define a "good word" to be a word of length $n+1$ over the alphabet $\{A,B,C\}$ satisfying the conditions: there are exactly $k$ $C$'s, there is at least one $B$, and the first $B$ precedes all the $C$'s.
If $j$ is the number of $B$'s in a good word, then we must have $1\le j\le n+1-k$; moreover, the number of good words with exactly $j$ $B$'s is given by the expression
$$\binom{n+1}{k+j}\binom{k+j-1}k.$$
The combinatorial meaning of the identity is that the number of good words with an odd number of $B$'s is one more than the number of good words with an even number of $B$'s. Here is a bijective proof of that fact.
Let $w$ be the word consisting of a single $B$ preceded by $n-k$ $A$'s and followed by $k$ $C$'s; this is a good word with an odd number of $B$'s. Let $W$ be the set of all good words different from $w$; we have to show that $W$ contains just as many words with an odd as with an even number of $B$'s. To see this, observe that the operation of switching the last non-$C$ letter in a word (from $A$ to $B$ or from $B$ to $A$) is an involution on $W$ which changes the parity of the number of $B$'s.
A: I haven't yet come up with a combinatorial proof, but a proof using induction and the binomial formula is straightforward enough.
We fix $k \geqslant 0$ and use induction on $n \geqslant k$. The base case $n = k$ is simply
$$\sum_{i=k}^k (-1)^{i-k}\binom{i}{k}\binom{k+1}{i+1} = (-1)^0 \binom{k}{k}\binom{k+1}{k+1} = 1.$$
For the induction step, we have
$$\begin{align}
\sum_{i=k}^{n+1} (-1)^{i-k}\binom{i}{k}\binom{n+2}{i+1} &= \sum_{i=k}^{n+1} (-1)^{i-k}\binom{i}{k}\left\lbrace \binom{n+1}{i+1} + \binom{n+1}{i}\right\rbrace\\
&=\sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i+1} + \sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i}\\
&=\underbrace{\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i+1}}_1 + \underbrace{\sum_{i=k}^{n+1}(-1)^{i-k}\binom{i}{k}\binom{n+1}{i}}_{m(k,n)}
\end{align}$$
where in the first sum on the right the term for $i = n+1$ vanishes since $\binom{n+1}{n+1+1} = 0$ and the remainder is the sum for $n$, which is $1$ by the induction hypothesis.
It remains to see that $m(k,n) = 0$. But that is the coefficient of $x^k$ in
$$\begin{align}
x^{n+1} &= \bigl(1 - (1-x)\bigr)^{n+1}\\
&= \sum_{i=0}^{n+1} (-1)^i\binom{n+1}{i}(1-x)^i\\
&= \sum_{i=0}^{n+1} \sum_{k=0}^i (-1)^{i+k}\binom{i}{k}\binom{n+1}{i}x^k\\
&= \sum_{k=0}^{n+1}\left(\sum_{i=k}^{n+1}(-1)^{i+k}\binom{i}{k}\binom{n+1}{i}\right)x^k,
\end{align}$$
since $(-1)^{i+k} = (-1)^{i-k}$. We have $k \leqslant n < n+1$, hence the coefficient is $0$.
A: Here is another algebraic proof. Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the product of the two generating functions is the generating function of
$$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
The sum we are trying to evaluate is
$$\sum_{k=j}^n (-1)^{k-j} {k\choose j} {n+1\choose k+1} =
(n+1)  \sum_{k=j}^n \frac{(-1)^{k-j}}{k+1} {k\choose j} {n\choose k}.$$
Now let $$A_1(z)
= \sum_{k\ge 0} (-1)^{k-j} {k\choose j} \frac{z^k}{k!} =
\frac{1}{j!} \sum_{k\ge j} (-1)^{k-j}  \frac{z^k}{(k-j)!}
\\= \frac{1}{j!} z^j \sum_{k\ge j} (-1)^{k-j}  \frac{z^{k-j}}{(k-j)!}
= \frac{1}{j!} z^j \exp(-z).$$
It then follows that
$$ A(z) = \sum_{k\ge 0} \frac{(-1)^k}{k+1} {k\choose j} \frac{z^k}{k!}
= \frac{1}{z} \left(C + \int A_1(z) dz\right)$$
with $C$ a constant to be determined.
Now it is not difficult to show (consult the end of this post) that 
$$\int A_1(z) dz = -\exp(-z)  \sum_{q=0}^j \frac{z^q}{q!}$$
and we must have 
$$C = -[z^0] \left(-\exp(-z)  \sum_{q=0}^j \frac{z^q}{q!} \right)= 1$$
so that
$$A(z) =  \frac{1}{z} \left(1 -\exp(-z)  \sum_{q=0}^j \frac{z^q}{q!}\right).$$
We have now determined $A(z)$ for the convolution of the two generating functions.
We take $$B(z) = \sum_{k\ge 0} \frac{z^k}{k!} = \exp(z).$$
It follows that
$$A(z) B(z) =
\frac{1}{z} \left(\exp(z) -  \sum_{q=0}^j \frac{z^q}{q!}\right).$$
Now applying the coefficient extraction operator we get for $n\ge j$ that
$$(n+1)  n! [z^n] A(z) B(z) =
(n+1)!  [z^{n+1}] \left(\exp(z) -  \sum_{q=0}^j \frac{z^q}{q!}\right).$$
None of the terms from the sum contribute because $n+1>j$ so that we are left with
$$(n+1)! [z^{n+1}] \exp(z) = (n+1)!  \frac{1}{(n+1)!} = 1.$$
Verification.
$$\left(-\exp(-z)  \sum_{q=0}^j \frac{z^q}{q!}\right)' =
\exp(-z)   \sum_{q=0}^j \frac{z^q}{q!} - \exp(-z)  \sum_{q=0}^{j-1} \frac{z^q}{q!}
= \exp(-z) \frac{z^j}{j!}.$$
A: Wolfram Alpha yields this result:

It's here !!!
It's too bad for Wolfram Alpha that ${\bf they\ don't\ say}$ that the right hand side is identical to $\color{#0000ff}{\large\mbox{ONE}\ = 1}$.
A: Suppose we  seek to verify that
$$\sum_{q=k}^n (-1)^{q-k} {q\choose k} {n+1\choose q+1} = 1$$
where $n\ge k.$
We first treat the case when $k\gt 0$ and introduce
$${q\choose k} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k+1}} (1+z)^q \; dz.$$
Observe that this is zero when $0\le q\lt k$ so that we may extend the
limit in the sum to zero, getting
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k+1}} 
\sum_{q=0}^n (-1)^{q-k} {n+1\choose q+1} (1+z)^q
\; dz
\\ = (-1)^{k+1} \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k+1}} \frac{1}{1+z}
\sum_{q=0}^n (-1)^{q+1} {n+1\choose q+1} (1+z)^{q+1}
\; dz
\\ = (-1)^{k+1} \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k+1}} \frac{1}{1+z}
\sum_{q=1}^{n+1} (-1)^{q} {n+1\choose q} (1+z)^{q}
\; dz
\\ = (-1)^{k+1} \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k+1}} \frac{1}{1+z}
(-1+(1-(1+z))^{n+1})
\; dz
\\ = (-1)^{k+1} \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k+1}} \frac{1}{1+z}
(-1 + (-1)^{n+1} z^{n+1})
\; dz.$$
Now since $n\ge k$ this simplifies to
$$(-1)^{k} \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k+1}} \frac{1}{1+z} \; dz
= (-1)^k (-1)^k = 1.$$
The second case when $k=0$ yields
$$\sum_{q=0}^n (-1)^{q} {n+1\choose q+1} 
= - \sum_{q=1}^{n+1} (-1)^{q} {n+1\choose q}
= - ((1-1)^{n+1}-1) = 1.$$
