• Support PF! Buy your school textbooks, materials and every day products Here!

Binomial coefficients

  • Thread starter jbear12
  • Start date
13
0
Suppose n is even, prove:
[tex]\sum[/tex]k=0->n/2, C(n,2k)=2^(n-1)=[tex]\sum[/tex]k=1->n/2, C(n,2k-1)
Give a combinatorial argument to prove that: (I've figured out this one...)
[tex]\sum[/tex]k=1->n, C(n,k)^2=C(2n,n)

For the first problem, I tried to break C(n, 2k) into C(n+1,2k)-C(n, 2k-1), but they didnt seem to work very well. (I also noticed that [tex]\sum[/tex]0, n C(n,2k)=2^n, but I can't really use this to solve the problem.)
For the second problem, I don't have a clue.
Any thoughts?
Thanks!
 
Last edited:

HallsofIvy

Science Advisor
Homework Helper
41,731
883
You want to prove that, for n even, [itex]\sum_{k= 0}^{n/2}C(n, 2k)= 2^{n-1}[/itex] and that [itex]\sum_{k=0}^{n/2} C(n, 2k-1)= 2^{n-1}[/itex]

You think mean you have tried to use C(n, 2k)= C(n-1,2k)-C(n-1, 2k-1) . That works nicely! If you take i= 2k, That just says C(n, i)= C(n-1, i)+ C(n-1, i) and your sum is [itex]\sum_{k= 0}^{n/2}C(n, 2k)= \sum_{i= 0}^n C(n-1, i)= 2^{n-1}[/itex]!

For the second one, let i= 2k-1.
 
13
0
You want to prove that, for n even, [itex]\sum_{k= 0}^{n/2}C(n, 2k)= 2^{n-1}[/itex] and that [itex]\sum_{k=0}^{n/2} C(n, 2k-1)= 2^{n-1}[/itex]

You think mean you have tried to use C(n, 2k)= C(n-1,2k)-C(n-1, 2k-1) . That works nicely! If you take i= 2k, That just says C(n, i)= C(n-1, i)+ C(n-1, i) and your sum is [itex]\sum_{k= 0}^{n/2}C(n, 2k)= \sum_{i= 0}^n C(n-1, i)= 2^{n-1}[/itex]!

For the second one, let i= 2k-1.
Thanks HallsofIvy.
But I don't get it how you get from C(n, 2k)= C(n-1,2k)-C(n-1, 2k-1) to C(n, i)= C(n-1, i)+ C(n-1, i). Taking i=2k, why is C(n-1,i-1) equal to -C(n-1,i).
Also, why is [itex]\sum_{i= 0}^n C(n-1, i)= 2* \sum_{i= 0}^{n/2} C(n-1, i)[/itex]
 

Related Threads for: Binomial coefficients

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
627
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
2
Replies
29
Views
6K
Top