Results 1 to 4 of 4

Math Help - Even vs. Odd in a combinatoric proof

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    12

    Even vs. Odd in a combinatoric proof

    I was given a problem to simplify the following:
    \sum_{k \geq 0} \binom{n}{2k}
    where:
     \binom{n}{j} = 0 whenever j > n.
    It's easy to see that the problem is equivalent to:
    \sum_{k = 0}^n \binom{n}{2k}

    Now I can see that for odd values of n, this expands to:
    \binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1}
    and since:
    \binom{n}{n-1} = \binom{n}{1}, \binom{n}{n-3} = \binom{n}{3}, ...
    we can use the last n/2 terms to "fill in the gaps", simplifying it to be:
    \frac{\sum_{k=0}^n \binom{n}{k}}{2} = \frac{2^n}{2} = 2^n-1

    That's easy. But I don't know why the proof still works for even numbers of n. You no longer have the same correspondence (n choose 0 no longer has the equivalent n choose n-1 as a term):
    \binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-2} + \binom{n}{n}
    So it can't "fill in the gaps" in the same way.

    Can anyone figure this out? I've been at this for hours and the explanations I'm being given by the texts are just crap.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by RespeckKnuckles View Post
    I was given a problem to simplify the following:
    \sum_{k \geq 0} \binom{n}{2k}
    where:
     \binom{n}{j} = 0 whenever j > n.
    It's easy to see that the problem is equivalent to:
    \sum_{k = 0}^n \binom{n}{2k}

    Now I can see that for odd values of n, this expands to:
    \binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1}
    and since:
    \binom{n}{n-1} = \binom{n}{1}, \binom{n}{n-3} = \binom{n}{3}, ...
    we can use the last n/2 terms to "fill in the gaps", simplifying it to be:
    \frac{\sum_{k=0}^n \binom{n}{k}}{2} = \frac{2^n}{2} = 2^n-1

    That's easy. But I don't know why the proof still works for even numbers of n. You no longer have the same correspondence (n choose 0 no longer has the equivalent n choose n-1 as a term):
    \binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-2} + \binom{n}{n}
    So it can't "fill in the gaps" in the same way.

    Can anyone figure this out? I've been at this for hours and the explanations I'm being given by the texts are just crap.
    Here is a combinatorial proof. Clearly \displaystyle \sum_{k=0}^{n}{n\choose {2k}} counts the number of subsets of [n] with
    an even number

    of elements. Call the set of subsets with an odd number elements of [n] O_n and the set of subsets with an

    even number elements E_n. We claim that \#\left(E_n\right)=\#\left(O_n\right) for every n\in\mathbb{N}. The result is clearly true

    for n=1. Suppose it's true for [n] and note that [n+1] can be partitioned into the subsets of [n+1]

    which contain n+1 and those that don't, call this partition \{B_1,B_2\} (with B_1 being the collection

    of subsets not containing n+1) it's evident that O_{n+1} is equal to the number of subsets with an odd number

    of elements of B_1 plus the number of subsets of B_2 with an odd number of elements and similarly for E_{n+1}.

    But, it's clear that the number of subsets of B_1 with an odd number of elements is O_{n} and the number of

    subsets of B_1 with an even number of elements is E_n. But, a little thought shows that the number of

    subsets with an even number of elements in B_2 is O_n and the number of subsets with an odd number of

    elements is E_n. Thus, O_{n+1}=O_n+E_n and E_{n+1}=O_n+E_n from where the conclusion follows by

    induction. Thus,


    \displaystyle \begin{aligned}\sum_{k=0}^{n}{n\choose 2k} &=\frac{1}{2}\left(\#(E_n)+\#(E_n)\right)\\ &= \frac{1}{2}\left(\#(E_n)+\#(O_n)\right)\\ &= \frac{1}{2}2^n\\ &= 2^{n-1}\end{aligned}




    Remark: Incidentally we've proven that \#2([n])=\#([n+1]) and since \#(2^{\varnothing})=1 we may conclude that

    \#([n])=2^n
    Last edited by Drexel28; January 2nd 2011 at 12:42 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member BAdhi's Avatar
    Joined
    Oct 2010
    From
    Gampaha, Sri Lanka
    Posts
    252
    Thanks
    6
    you've taken \sum_{k\geq0} \rightarrow \sum_{k=0}^n but doesn't it has to be \sum_{k\geq0} \rightarrow \sum_{k=0}^{n/2} that is because when  2k>n,  \binom{n}{2k}=0 so the largest value that k can have is \frac{n}{2}. if this is correct, since k is an integer, n has to even.
    Last edited by BAdhi; January 2nd 2011 at 12:56 AM. Reason: latex errors
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member BAdhi's Avatar
    Joined
    Oct 2010
    From
    Gampaha, Sri Lanka
    Posts
    252
    Thanks
    6

    correction to the previous post

    forget what i've mentioned in my previous post it's all wrong and really sorry abount it.(because n is a given value it can either be odd or even)

    but check out this method. Hope it's not wrong too.

    (a+b)^n=\sum_{r=0}^n\binom{n}{r}a^rb^{n-r}

    if n is odd

    if a=1,b=-1

    0=\sum_{r=0}^n\binom{n}{2r}-\sum_{r=0}^n\binom{n}{2r+1} ___ (1)

    if a=b=1;

    2^n=\sum_{r=0}^n\binom{n}{2r}-\sum_{r=0}^n\binom{n}{2r+1}___(2)

    by (1)+(2) i think we'll get the result for odd n

    when n is even, same 2 equations could be achieved.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Two combinatoric problems
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 21st 2010, 05:16 PM
  2. Need help with Combinatoric Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 27th 2010, 09:21 PM
  3. combinatoric thing
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 11th 2008, 12:48 AM
  4. Combinatoric sequence, please help me
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 5th 2007, 08:05 AM
  5. combinatoric identity
    Posted in the Statistics Forum
    Replies: 1
    Last Post: February 17th 2007, 05:24 PM

Search Tags


/mathhelpforum @mathhelpforum