<s>[INST] 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.
 [/INST] 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.$$
</s>