6
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – user84413 May 21 '16 at 21:38
  • $\begingroup$ @user84413: Good catch; thanks! $\endgroup$ – Brian M. Scott May 21 '16 at 21:41
  • $\begingroup$ Thank you, and thanks for the answer! $\endgroup$ – user84413 May 21 '16 at 23:35
  • $\begingroup$ @user84413: You're welcome! $\endgroup$ – Brian M. Scott May 21 '16 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.