Results 1 to 3 of 3

Math Help - induction with a binomial

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    induction with a binomial

    Prove \forall n\geq 0

    \binom{n}{0}+\binom{n}{1}+\cdots +\binom{n}{n}=2^n

    p(0): \ \binom{n}{0}=1=2^0=1

    Assume p(k) is true

    p(k): \ \binom{k}{0}+\binom{k}{1}+\cdots +\binom{k}{k}=2^k

    Prove

    p(k+1): \ \binom{k}{0}+\binom{k}{1}+\cdots +\binom{k+1}{k+1}=2^{k+1}

    Simply adding the next binomial term to both sides doesn't help. Any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,111
    Thanks
    2

    Re: induction with a binomial

    You're a few "k+1"s short - actually, k of them.

    2^{k+1} - 2^{k} = 2^{k}\cdot(2-1) = 2^{k}

    Focus on the 3rd term (2 in the bottom of the choose) and see if it makes any sense.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Master Of Puppets
    pickslides's Avatar
    Joined
    Sep 2008
    From
    Melbourne
    Posts
    5,236
    Thanks
    28

    Re: induction with a binomial

    Hi dw, it might help if,


    p(k+1): \ \binom{k+1}{0}+\binom{k+1}{1}+\cdots +\binom{k+1}{k+1}=2^{k+1}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: July 15th 2010, 05:33 AM
  2. Sums of Binomial Coefficients - proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 22nd 2010, 07:44 AM
  3. Replies: 1
    Last Post: November 12th 2009, 12:38 AM
  4. Replies: 1
    Last Post: March 11th 2009, 11:09 PM
  5. Relation between Negative Binomial and Binomial Distros
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 5th 2007, 06:59 AM

/mathhelpforum @mathhelpforum