Combinatorics and alternating series

[QuantumP7]

Homework Statement

Prove that

1 - \dbinom{n}{1}\ + \dbinom{n}{2} \ - \dbinom{n}{3} \ + \cdots \ + (-1)^r \dbinom{n}{r} = (-1)^r \dbinom{n - 1}{r}

by induction.

Homework Equations

The Attempt at a Solution

Well, I know how to solve the normal binomial sums by using the identity \dbinom{n}{r} \ = \dbinom{n - 1}{r} \ + \dbinom{n - 1}{r - 1}. I'm just not sure what to do with the (-1) part. I can't find any example of an inductive proof using an alternating series anywhere, that does not involve the convergence test. Could anyone give me a hint as to where to go with this problem?

 

[fzero]

Prove that

1 - \dbinom{n}{1}\ + \dbinom{n}{2} \ - \dbinom{n}{3} \ + \cdots + (-1)^r \ \dbinom{n - 1}{r}

by induction.

This statement is incomplete as written.

 

[QuantumP7]

I'm SO sorry! I fixed it. Thank you for pointing this out!

 

[fzero]

It might make it easier to write the identity as
(-1)^r \dbinom{n - 1}{r} = \sum_{k=0}^r (-1)^{r-k} \begin{pmatrix} n \\ r-k \end{pmatrix}.I'm not sure yet if the recursive formula is any easier than the factorial formula. It might help to use both at some point.

 

[QuantumP7]

Well, for n + 1, would the equation be

1 - \dbinom{n}{1} + \dbinom{n}{2} \ - \dbinom{n}{3} + \cdots + (-1)^{r - 1 }<br /> \dbinom{n}{r} + (-1)^r \dbinom{n + 1}{r} ?

 

[fzero]

Well, for n + 1, would the equation be

1 - \dbinom{n}{1} + \dbinom{n}{2} \ - \dbinom{n}{3} + \cdots + (-1)^{r - 1 }<br /> \dbinom{n}{r} + (-1)^r \dbinom{n + 1}{r} ?

No, for n+1, just shift n\rightarrow n+1 everywhere in the equation in the OP. Induction on n is trivial because you can just multiply through the equation for n by a certain set of factors to show that the (n+1) equation is true. The trickier part is induction on r. It looks like using that series just makes things harder though, so forget that I wrote that and use the recursion formula in the equation for r. You should be able to rearrange things to get the equation for (r+1).

 

[QuantumP7]

Oh, I see. Thank you SO much! I wish I could give you some points or something for your help!