Results 1 to 4 of 4

Math Help - using mathematical induction to prove something

  1. #1
    Junior Member
    Joined
    Mar 2008
    Posts
    55

    Red face using mathematical induction to prove something

    Hey guys having some trouble with this question I just don't really know where to go with it..


    Use mathematical induction to prove that, for all integers n ≥ 1

    n
    2^(j-1) = (2^n)-1.
    j=1

    thanks for any help you can give
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    P(n) : \sum_{j = 1}^{n} 2^{j-1} = 2^{n} - 1

    Prove that P(1) is true:
    \sum_{j = 1}^{1} 2^{0} = 1
    2^{1} - 1 = 1

    Now assume P(k) is true. We must show that this implies
    P(k+1): \sum_{j = 1}^{k+1} 2^{j-1} = 2^{k+1} - 1

    So, we have that:
    P(k+1): \sum_{j = 1}^{{\color{red}k+1}}2^{j-1} = \underbrace{\sum_{j=1}^{k}2^{j-1}}_{P(k)} + {\color{red} \: 2^{(k+1)-1}} = \underbrace{\left(2^{k} - 1\right)}_{P(k)} + 2^{k}

    Can you go on from that?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2008
    Posts
    55
    Quote Originally Posted by o_O View Post
    P(n) : \sum_{j = 1}^{n} 2^{j-1} = 2^{n} - 1

    Prove that P(1) is true:
    \sum_{j = 1}^{1} 2^{0} = 1
    2^{1} - 1 = 1

    Now assume P(k) is true. We must show that this implies
    P(k+1): \sum_{j = 1}^{k+1} 2^{j-1} = 2^{k+1} - 1

    So, we have that:
    P(k+1): \sum_{j = 1}^{{\color{red}k+1}}2^{j-1} = \underbrace{\sum_{j=1}^{k}2^{j-1}}_{P(k)} + {\color{red} \: 2^{(k+1)-1}} = \underbrace{\left(2^{k} - 1\right)}_{P(k)} + 2^{k}

    Can you go on from that?
    Hey thanks heaps for the reply!! Just wondering where the (-1) in {\color{red} \: 2^{(k+1)-1}} comes from?

    Thanks again.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Math Engineering Student
    Krizalid's Avatar
    Joined
    Mar 2007
    From
    Santiago, Chile
    Posts
    3,654
    Thanks
    13
    Because of \sum\limits_{j\,=\,1}^{k+1}{2^{j-1}}=\sum\limits_{j\,=\,1}^{k}{2^{j-1}}+\sum\limits_{j\,=\,k+1}^{k+1}{2^{j-1}}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove by mathematical induction
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: April 28th 2011, 01:06 PM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Prove By Mathematical Induction
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: May 30th 2010, 10:22 AM
  4. using mathematical induction to prove..
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 12th 2009, 08:28 AM
  5. Prove by Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 17th 2007, 10:29 AM

Search Tags


/mathhelpforum @mathhelpforum