Inductive proof of a binomial series

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
Homework Helper
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$$

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
Homework Helper
Gold Member
Well, the problem statement says to use Pascal's identity. What is that identity?

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
Homework Helper
Gold Member
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.

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