Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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, etc.)

Thank you.

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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