Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to prove the following using inclusion exclusion

$$ \sum _{k=m} ^{n} (-1)^{k-m} {n \choose k} = {n-1 \choose m-1}$$

share|cite|improve this question
Hint: $\binom{n-1}{k-1}+\binom{n-1}{k}=\binom{n}{k}$ – Thomas Andrews Apr 9 '13 at 14:02
But, by the tag "inclusion-exclusion" perhaps you are looking for a counting proof? – Thomas Andrews Apr 9 '13 at 14:05
yes, I want a counting proof – RIchard Williams Apr 9 '13 at 16:05

Instead of choosing $m-1$ from $n-1$ (the right-hand side), you add an $n$-th element $a$ and choose $m$ from $n$. If your choice included $a$, removing it from your selection gives you the choice of $m-1$ from the other $n-1$ that you wanted. But you also counted some spurious selections, the ones that don't include $a$. You could correct for that by subtracting $\binom{n-1}m$, but instead you go on as before and perform the correction by subtracting $\binom n{m+1}$. Again that yields the desired correction if your choice includes $a$ but also a new error if it doesn't, so you keep "correcting", until, at the point where you're selecting $n$ elements, your selection necessarily includes $a$, so it no longer contains an error and you're done.

share|cite|improve this answer

Your Answer


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.