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?

• That the sum alternates suggests that some kind of inclusion-exclusion interpretation, but I don't know how to provide such a construction. – Semiclassical May 21 '16 at 19:10

1 Answer

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.

• I may be mistaken about this, but do you want $\left|\bigcap_{k\in I}\mathscr{A}_k\right|=\binom{m+n-l}{n-l}$ where $\varnothing\ne I\subseteq[m+1]$ with $|I|=l$? – user84413 May 21 '16 at 21:38
• @user84413: Good catch; thanks! – Brian M. Scott May 21 '16 at 21:41
• Thank you, and thanks for the answer! – user84413 May 21 '16 at 23:35
• @user84413: You're welcome! – Brian M. Scott May 21 '16 at 23:41