Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Binomial coefficients

  1. Feb 2, 2010 #1
    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: Feb 2, 2010
  2. jcsd
  3. Feb 2, 2010 #2

    HallsofIvy

    User Avatar
    Science Advisor

    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.
     
  4. Feb 2, 2010 #3
    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]
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook