How can I prove that $\sum \limits_{i=0}^k {n \choose i}(-1)^i = {n-1 \choose k}(-1)^k$? I would like to prove this using a combinatorics argument. I have a feeling it involves the theorem $\sum \limits_{i=k}^n {i \choose k} = {n+1 \choose k+1}$. I'm not sure how to manipulate it to get the desired answer though. I also think I could explain it using Pascal's triangle, but I don't think that's a rigorous proof.
Thanks for any hints!
 A: Hint: Use the fact that
$$ { n-1 \choose k} + {n-1 \choose k+1} = { n \choose k}.$$
A: Both identities you mention are just Pascal's recurrence in disguise; however apart from that they are not directly close to each other, so you have better chances trying to use Pascal's recurrence directly. If you take $\sum\limits_{i=0}^n {i \choose k} = {n+1 \choose k+1}$ and subtract the same equation with $n$ lowered by one, you get $\binom nk=\binom{n+1}{k+1}-\binom n{k+1}$. In the same manner if you take the identity $\sum \limits_{i=0}^k (-1)^i{n \choose i} = (-1)^k{n-1 \choose k}$ you want to prove subtract the same equation with $k$ lowered by one, you get $(-1)^k\binom nk=(-1)^k\binom{n-1}k-(-1)^{k-1}\binom{n-1}{k-1}$, or after processing the signs $\binom nk=\binom{n-1}k+\binom{n-1}{k-1}$. So a proof by induction on $k$ should be a piece of cake.
If by a combinatorics argument you mean one that uses a combinatorial interpretation of the binomial coefficients, you can do the following. Take your left hand side to count all subsets of at most $k$ elements chosen from $n$ available element, bit with each subset$~S$ counted with a weight $(-1)^{|S|}$. Now you can pair up a lot of those subsets with one of an opposite sign by considering one particular available element, say number$~n$, and either removing it from $S$ if it is present, or otherwise adding it. The only contributions for which this is not possible is those that already have $k$ elements, bit not the element$~n$, so they are subsets of the remaining $n-1$ elements. The count of those is given by you right hand side.
