1
$\begingroup$

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.

  • 0
    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}$.2012-10-15

1 Answers 1

2

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?

  • 0
    Yes, exactly. Anytime you have a proof involving closed forms of sums, induction is likely a good thing try.2012-10-15