# proof of a combinatorial identity

How to prove the following using inclusion exclusion

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

-
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.