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. :)