Combinatorial proof of a certain alternating sum of binomial coefficients The following identity appeared as a question earlier today
$$\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}$$
and was given an algebraic solution. Is there a combinatorial proof?
 A: Suppose that you want to choose $n$ integers from the set $[m+n]$ in such a way that you do not include any integer less than or equal to $m+1$. If $n=0$ this is possible in exactly one way: you choose the empty set. If $n>0$, it’s not possible, since only the $n-1$ integers in $[m+n]\setminus[m+1]$ are available to be chosen.
For each $k\in[m+1]$ let $\mathscr{A}_k$ be the set of $n$-element subsets of $[m+n]$ that contain $k$; we want the number of $n$-element subsets of $[m+n]$ that are not in $\bigcup_{k\in[m+1]}\mathscr{A}_k$. Clearly
$$\left|\bigcap_{k\in I}\mathscr{A}_k\right|=\binom{m+n-|I|}{n-|I|}$$
whenever $\varnothing\ne I\subseteq[m+1]$, so by the inclusion-exclusion principle we have
$$\begin{align*}
\left|\bigcup_{k\in[m+1]}\mathscr{A}_k\right|&=\sum_{\varnothing\ne I\subseteq[m+1]}(-1)^{|I|-1}\left|\bigcap_{k\in I}\mathscr{A}_k\right|\\
&=\sum_{\varnothing\ne I\subseteq[m+1]}(-1)^{|I|-1}\binom{m+n-|I|}{n-|I|}\\
&=\sum_{k=1}^{m+1}(-1)^{k-1}\binom{m+1}k\binom{m+n-k}{n-k}\;,
\end{align*}$$
and hence the number of $n$-element subsets of $[m+n]$ that are not in $\bigcup_{k\in[m+1]}\mathscr{A}_k$ is
$$\begin{align*}
\binom{m+n}n&-\sum_{k=1}^{m+1}(-1)^{k-1}\binom{m+1}k\binom{m+n-k}{n-k}\\
&=\binom{m+n}n+\sum_{k=1}^{m+1}(-1)^k\binom{m+1}k\binom{m+n-k}{n-k}\\
&=\sum_{k=0}^{m+1}(-1)^k\binom{m+1}k\binom{m+n-k}{n-k}\;.
\end{align*}$$
Thus,
$$\sum_{k=0}^{m+1}(-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}$$
The fact that I have $m+1$ instead of $n$ as the upper limit of summation is unimportant: in both versions we’re simply summing over all values of $k$ for which the terms are non-zero.
