1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    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!

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?
    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]
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook