Results 1 to 6 of 6

Math Help - Proof by Induction

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    5

    Proof by Induction

    Hey guys,

    ive got a question to solve:
    It goes like this:
    Using mathematical Induction, prove that

    SUM(r=1->n) of (r+1)2^r-1 = n(2^n)

    Now the basic step is easy so im not gonna bother typing it here now but later on:

    I get that:

    (Let P(k) be true so
    Sum(r=1->k) of (r+1)2^r-1 = k(2^k)

    Now prove that P(k+1) is true:

    Sum(r=1->k+1) of (r+1)2^r-1 = (k+1)(2^(k+1))

    The Lefthandside of the equation above says:
    Sum(r=1->k+1) of (r+1)2^r-1
    We can expand this to be
    Sum(r=1->k) of (r+1)2^r-1 + ((k+1)+1)2^(k+1)-1
    Using our assumption of the beginnig we can say now that:

    k(2^k) + ((k+1)+1)2^(k+1)-1 must equal this if i havenīt done any mistakes: (k+1)(2^(k+1)), doesnīt it.

    But somehow i canīt get that,
    if some could just show me the last step then iīd be fine with that.

    Hope i`ve expressed my self correctly in that question. (Couldnīt really get used to the commands quick menu; sorry)

    Cheers guys
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1
    Quote Originally Posted by ananas1301 View Post
    k(2^k) + ((k+1)+1)2^(k+1)-1 must equal this if i havenīt done any mistakes: (k+1)(2^(k+1)), doesnīt it.
    So far so good.

    Now

    What can you do with this?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2011
    Posts
    5
    This is how far I just got a minute ago as well;

    but I am stuck there and canīt get it to be (k+1)(2^(k+1)).

    Would it be fine ich I just state an example, where I replace the k with a fixed value!?

    (2k+2)2^k has to be fromed to look like that: (k+1)(2^(k+1))
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Mar 2011
    Posts
    118
    Quote Originally Posted by ananas1301 View Post
    Would it be fine ich I just state an example, where I replace the k with a fixed value!?
    That reveals a fatal misunderstanding of proof by induction. You have to show, if the result is true for a general particular integer k, it is true for k +1.
    (2k+2)2^k =2.2^k(k+1)=(k+1)2^(k+1).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2011
    Posts
    5
    Quote Originally Posted by poirot View Post
    That reveals a fatal misunderstanding of proof by induction. You have to show, if the result is true for a general particular integer k, it is true for k +1.
    (2k+2)2^k =2.2^k(k+1)=(k+1)2^(k+1).
    Thatīs what I thought as well, it is just not the point of the induction.

    I donīt get that step you have done
    (2k+2)2^k =2.2^k(k+1)=(k+1)2^(k+1)

    I know i could just write that down, but i want to understand it as well.

    Can you explain it in more detail please?

    Would be really nice, thank you


    EDIT:

    No i got it now.

    The last step was fairly easy but i just didnīt really know what that dot between the two twos was meant to be.

    Anyway thank you!!!
    Last edited by ananas1301; April 26th 2011 at 07:41 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Mar 2011
    Posts
    118
    its the european sign for multiplication
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction that 4| 5^n - 1
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 17th 2010, 11:23 AM
  2. proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 17th 2010, 08:11 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. induction proof
    Posted in the Algebra Forum
    Replies: 7
    Last Post: November 1st 2008, 05:32 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum