# Having trouble with a combinatorics proof

Here's the question:

Prove that for all positive integers k ≤ n,

$\sum_{i=0}^{k} {n \choose i} (-1)^i = {n -1 \choose k}(-1)^k$

So far, I've noticed that you can change ${n \choose i}$ into ${n - 1 \choose i} + {n -1 \choose i - 1}$, which gets me closer to where I want to be, but beyond that I'm stuck.

-
Are you familiar with telescoping series? –  anonymous Oct 15 '12 at 14:14
To some extent, but I don't believe we've seen them in the context of this class. –  rapidash Oct 15 '12 at 14:17
If you take the relation you noted, plug it in and write it out, you get a telescoping series in $(-1)^i\binom{n-1}{i}$. –  anonymous Oct 15 '12 at 14:28

You made a good observation. You've noticed that you can reduce the problem to a simpler form (smaller $n$, $k$, etc). So consider exploiting that in an inductive proof.
Let us induct on $k$ for a fixed $n$. We have for $k=1$ $$\sum_{i=0}^1 \binom{n}{i}(-1)^i =1-n= -\binom{n-1}{1}$$ so the result holds true. Now suppose it holds for some $k\ge1$. Let us consider $k+1$. We have $$\sum_{i=0}^{k+1}\binom{n}{i}(-1)^i = (-1)^{k+1}\binom{n}{k+1}+\sum_{i=0}^k\binom{n}{i}(-1)^i$$ Now we apply out inductive hypothesis to get $$=(-1)^{k+1}\binom{n}{k+1}+(-1)^k\binom{n-1}{k}=(-1)^{k+1}\left[\binom{n}{k+1}-\binom{n-1}{k}\right]$$ Can you see how to finish it off?