Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer 1

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|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
add comment

Your Answer

 
discard

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.