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

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.

share|cite|improve this question
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?

share|cite|improve this answer
Yeah. Since n choose k + n choose k + 1 = n + 1 choose k + 1, the portion within brackets becomes n - 1 choose k + 1. Then we're done. – rapidash Oct 15 '12 at 14:41
Yes, exactly. Anytime you have a proof involving closed forms of sums, induction is likely a good thing try. – EuYu Oct 15 '12 at 14:44

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.