Inductive proof of a binomial series

  • Thread starter lynchu
  • Start date
  • #1
7
0

Homework Statement



Use mathematical induction and Pascal's Identity to prove:

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

The Attempt at a Solution



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

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!
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
964
Am I missing something? When k= 0 that says
[tex]\begin{pmatrix}n \\ 0\end{pmatrix}= (-1)^0\begin{pmatrix}n-1 \\ 0\end{pmatrix}[/tex]
which is not true, the left side is n and the right n-1.

For k= 1,
[tex]\begin{pmatrix}n \\ 0\end{pmatrix}- \begin{pmatrix}n \\ 1\end{pmatrix}= n- (n- 1)= 1[/tex]
but
[tex](-1)^1\begin{pmatrix}n-1 \\ 1\end{pmatrix}= -(n-2)= 2- n[/tex]
 
  • #3
7
0
But [tex]\binom{n}{0} = \binom{n-1}{0} = 1[/tex]

It's the number of 0-element subsets of an n-elements set. Which is 1, because there's only the empty set.
 
  • #4
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,473
255
Well, the problem statement says to use Pascal's identity. What is that identity?
 
  • #5
7
0
Sorry, forgot to include that. Pascal's Identity is:

[tex]\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}[/tex] for non-negative n's.
 
  • #6
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,473
255
OK, so apply Pascal's identity to the binomial coefficient for each [itex]i[/itex] in the sum:

[tex]{n \choose i} = {n - 1 \choose i - 1} + {n - 1 \choose i}[/tex]

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

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

[tex]{n - 1 \choose i}[/tex]

and you can do the same with the other sum

[tex]{n - 1 \choose i - 1}[/tex]

after a change of variables.
 
Last edited:
  • #7
7
0
Thanks a bunch.
That's just about what I needed. :)
 

Related Threads on Inductive proof of a binomial series

  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
2K
Replies
5
Views
3K
Replies
3
Views
1K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
715
  • Last Post
Replies
1
Views
1K
Replies
1
Views
937
Top