Results 1 to 7 of 7

Math Help - Proof with Combinations

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    Proof with Combinations

    I've been having trouble with the following proof:

    Let n be an odd positive integer. Prove that

    \binom{n}{0} + \binom{n}{2} + \binom{n}{4} + ... + \binom{n}{n-1} = 2^{n-1}

    My first attempt at a proof was to use induction but at the inductive step, I couldn't simplify it to work out. After consulting my professor, he said that while it possible to prove it by induction, he could think of numerous other ways without induction. I'm not too sure of what to do now.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by icecube View Post
    I've been having trouble with the following proof:

    Let n be an odd positive integer. Prove that

    \binom{n}{0} + \binom{n}{2} + \binom{n}{4} + ... + \binom{n}{n-1} = 2^{n-1}

    My first attempt at a proof was to use induction but at the inductive step, I couldn't simplify it to work out. After consulting my professor, he said that while it possible to prove it by induction, he could think of numerous other ways without induction. I'm not too sure of what to do now.

    Remember Newton's Binomial Theorem: (a+b)^n=\sum_{k=0}^n\left(\begin{array}{c}n\\k\end  {array}\right)a^{n-k}b^k

    Also, note that 1^n=1 for any power n
    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    12
    Well I tried using Binomial Theorem, and using (1+1)^(d-1) and other variations, however, I could not prove that the terms from the Binomial Theorem were the same as in the proposition.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by icecube View Post
    Well I tried using Binomial Theorem, and using (1+1)^(d-1) and other variations, however, I could not prove that the terms from the Binomial Theorem were the same as in the proposition.
    Can you see why for odd n,

    \binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1} = \binom{n}{1} + \binom{n}{3} + ... + \binom{n}{n} ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    12
    Yes I can see why for odd n that would hold true. (I expanded each combination and saw that the terms were equal in reverse order).

    Now I just have to see how I can use this to relate my proof to the Binomial Theorem (?).

    EDIT: Oh wait. Hm...

    <br />
\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1} =  \binom{n}{1} + \binom{n}{3} + ... + \binom{n}{n} = 2^{n-1}  =  \frac{2^{n}}{2}

    \binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1} +  \binom{n}{1} + \binom{n}{3} + ... + \binom{n}{n} = 2^{n} = (1+1)^{n} = \sum_{k=0}^n \binom{n}{k} 1^{n-k}1^{k}<br />

    The proof is basically complete since the terms of each series are exactly equal. Is this correct?
    Last edited by icecube; October 20th 2009 at 07:00 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by icecube View Post
    Yes I can see why for odd n that would hold true. (I expanded each combination and saw that the terms were equal in reverse order).

    Now I just have to see how I can use this to relate my proof to the Binomial Theorem (?).

    EDIT: Oh wait. Hm...
    <br />
\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1} =  \binom{n}{1} + \binom{n}{3} + ... + \binom{n}{n} = 2^{n-1}  =  \frac{2^{n}}{2}

    \binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1} +  \binom{n}{1} + \binom{n}{3} + ... + \binom{n}{n} = 2^{n} = (1+1)^{n} = \sum_{k=0}^n \binom{n}{k} 1^{n-k}1^{k}<br />

    Is this correct?
    That is pretty much correct. A more clear way of showing it would be:

    2^n = (1+1)^n = \sum_{k=1}^n\binom{n}{k}1^n1^{n-k} = \binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n-1} + \binom{n}{n} =  2(\binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1}) = 2^n \Rightarrow \frac{2^n}{2} = \boxed{2^{n-1} = \binom{n}{0} + \binom{n}{2} + ... + \binom{n}{n-1}}
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2009
    Posts
    12
    Ah, yes my work tends to be a bit disorganized XD. Thank you so much! Now to write it up x_x.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof regarding combinations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 18th 2010, 01:44 PM
  2. combinations proof by induction?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 17th 2009, 11:03 PM
  3. combinations proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 4th 2009, 05:34 AM
  4. [SOLVED] Discrete Math Proof: Combinations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 24th 2009, 05:46 PM
  5. Combinations Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 14th 2008, 01:09 AM

Search Tags


/mathhelpforum @mathhelpforum