Inductive proof of a binomial series

[lynchu]

Homework Statement

Use mathematical induction and Pascal's Identity to prove:

\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - ... + (-1)^{k}\binom{n}{k} = (-1)^{k}\binom{n-1}{k}

The Attempt at a Solution

First, I guess this means something like:
\sum_{i=0}^{k}(-1)^{i}\binom{n}{i} = (-1)^{k}\binom{n-1}{k}

But after that I'm stumped (as with any inductive proof with sums of binomials)... I can't see how my usual strategy would work. i.e. Figure out what n+1 would contribute to the left hand side, add it to the right side and work my way through algebraically.

Help with this would be very appreciated!

 

[HallsofIvy]

Am I missing something? When k= 0 that says
\begin{pmatrix}n \\ 0\end{pmatrix}= (-1)^0\begin{pmatrix}n-1 \\ 0\end{pmatrix}
which is not true, the left side is n and the right n-1.

For k= 1,
\begin{pmatrix}n \\ 0\end{pmatrix}- \begin{pmatrix}n \\ 1\end{pmatrix}= n- (n- 1)= 1
but
(-1)^1\begin{pmatrix}n-1 \\ 1\end{pmatrix}= -(n-2)= 2- n

 

[lynchu]

But \binom{n}{0} = \binom{n-1}{0} = 1

It's the number of 0-element subsets of an n-elements set. Which is 1, because there's only the empty set.

 

[jbunniii]

Well, the problem statement says to use Pascal's identity. What is that identity?

 

[lynchu]

Sorry, forgot to include that. Pascal's Identity is:

\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k} for non-negative n's.

 

[jbunniii]

OK, so apply Pascal's identity to the binomial coefficient for each i in the sum:

{n \choose i} = {n - 1 \choose i - 1} + {n - 1 \choose i}

(However, be careful: this doesn't make any sense for i = 0. So you will need to handle that term separately. Similarly, watch out if n = i.)

Then split the sum into two sums. You can apply the inductive hypothesis directly to the sum involving

{n - 1 \choose i}

and you can do the same with the other sum

{n - 1 \choose i - 1}

after a change of variables.

 

[lynchu]

Thanks a bunch.
That's just about what I needed. :)