1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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


    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]
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook