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
    Are you familiar with telescoping series?2012-10-15
  • 0
    To some extent, but I don't believe we've seen them in the context of this class.2012-10-15
  • 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
    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.2012-10-15
  • 0
    Yes, exactly. Anytime you have a proof involving closed forms of sums, induction is likely a good thing try.2012-10-15