7
$\begingroup$

Given the following identity: $$\sum_{i=0}^k (-1)^i \binom ni = (-1)^k \binom {n-1}{k}.$$

This is provable by induction. However, I wonder if there is a way to prove this in a combinatorial fashion (something like subsets, groups, choosing $n$ balls from a box with $k$ balls, et cetera.)

Thank you.

$\endgroup$
7
$\begingroup$

The left side of your equation is a weighted count of the subsets of $\{1,\dots,n\}$ of all sizes $i$ from $0$ to $k$, the weights being $1$ or $-1$ according as $i$ is even or odd. We can pair up most of these subsets as follows: If a set $X$ contains $n$, pair it with $X-\{n\}$; if it doesn't contain $n$, pair it with $X\cup\{n\}$. Note that this is truly a pairing; if we paired $X$ with $Y$, then we also paired $Y$ with $X$. Any two paired sets contribute with opposite signs to your sum, so their contributions cancel out, and the sum reduces to the unpaired sets. But these are just the sets that have $k$ elements and don't contain $n$. Any smaller set can be paired, as described, by adjoining or removing $n$; and a set of size $k$ that contains $n$ can be paired as described, by removing $n$. Only when a set doesn't contain $n$ (so we want to adjoin $n$) and has size $k$ (so that adjoining an element would make its size impermissibly large) is there a failure of pairing. The unpaired sets, the sets of size $k$ that don't contain $n$, all contribute with sign $(-1)^k$, and there are $\binom {n-1}k$ of them. Hence the right side of your equation.

| cite | improve this answer | |
$\endgroup$

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.