Results 1 to 9 of 9
Like Tree2Thanks
  • 1 Post By MarkFL
  • 1 Post By Plato

Math Help - Prove by induction

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    Earth
    Posts
    9

    Prove by induction

    I'm stuck on this exercise, I know I'm getting close, but I just can't see it

    Prove by induction that \sum_{i=0}^n i2^{i - 1} = (n -1)2^n + 1.

    Basically this boils down to showing that ((k + 1) - 1)2^{k + 1} + 1 = (k - 1)2^k + 1 + (k + 1)2^{(k + 1) - 1, simplified: 2k^{k + 1} + 1 = (k - 1)2^k + 1 + (k + 1)2^k

    My right hand side simplifies to (k - 1)2^k + 1 + (k + 1)2^k = 2k^k - 2^k + 1 + 2k^k + 2^k = 4k^k + 1 \ne 2k^{k + 1} + 1
    So obviously I'm missing something and I'm afraid it's as trivial as possible, but I just don't see it at the moment
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,711
    Thanks
    1640
    Awards
    1

    Re: Prove by induction

    Quote Originally Posted by Diligo View Post
    Prove by induction that \sum_{i=0}^n i2^{i - 1} = (n -1)2^n + 1.
    Have you shown the base case n=0 is true.

    Then note that \sum_{i=0}^{N+1} i2^{i - 1} =\sum_{i=0}^n i2^{i - 1} + (n )2^{n+1}
    Last edited by Plato; November 21st 2012 at 09:14 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2012
    From
    Earth
    Posts
    9

    Re: Prove by induction

    Sorry, I'm not getting the hint.

    But, yes, I've checked for the base case, just omitted it for brevity.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,711
    Thanks
    1640
    Awards
    1

    Re: Prove by induction

    Quote Originally Posted by Diligo View Post
    Sorry, I'm not getting the hint.
    If you assume that \sum_{i=0}^{N} i2^{i - 1} = (N-1 )2^{N} + 1

    Then \sum_{i=0}^{N+1} i2^{i - 1} = (N)2^{N} + 1+(N )2^{N}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2012
    From
    Earth
    Posts
    9

    Re: Prove by induction

    Hmm, ok, I thought it had to be: \sum_{i=0}^{N+1}i2^{i-1}=(N - 1)2^{N}+1+(N + 1)2^{N}

    Take for example \sum_{i = 0}^n 2^i = 2^{n + 1} - 1

    Now we need to show that 2^{k + 2} - 1 = 2^{k+ 1} - 1 + 2^{k + 1}, which of course is true.
    I thought \sum_{i=0}^{N+1}i2^{i-1}=(N - 1)2^{N}+1+(N + 1)2^{N} was analog to that? I fill in k + 1 in the LHS and add that to the RHS.

    Is it possible you explain your answer a bit further? Would help me tremendously, apparently I don't understand it quite as good as I'm supposed to
    Last edited by Diligo; November 21st 2012 at 09:44 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Prove by induction

    If I were to prove this by induction, after having demonstrated the base case is true, I would state the induction hypothesis P_k:

    \sum_{i=0}^ki2^{i-1}=(k-1)2^k+1

    Next, add (k+1)2^k to both sides:

    \sum_{i=0}^ki2^{i-1}+(k+1)2^k=(k-1)2^k+1+(k+1)2^k

    \sum_{i=0}^{k+1}i2^{i-1}=((k-1)+(k+1))2^k+1

    Now, we are left to try to show:

    ((k-1)+(k+1))2^k=((k+1)-1)2^{k+1}
    Thanks from Diligo
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2012
    From
    Earth
    Posts
    9

    Re: Prove by induction

    Thats exactly what I was trying. I've identified what's going wrong by working trough another example. And it's actually very basic...

    I fail to understand why, for example 3^k + 2(3^k) = 3^{k + 1} and in this case, why (2k)2^k = 2k^{k +1}
    Ah, I understand the latter one, could you please provide a pointer to 3^k + 2(3^k) = 3^{k + 1}?
    Last edited by Diligo; November 21st 2012 at 10:13 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,711
    Thanks
    1640
    Awards
    1

    Re: Prove by induction

    Quote Originally Posted by Diligo View Post
    Thats exactly what I was trying. I've identified what's going wrong by working trough another example. And it's actually very basic...
    I fail to understand why, for example 3^k + 2(3^k) = 3^{k + 1}


    It is simple factoring.
    3^k + 2(3^k) = 3^{k }(1+2)=3^{k }(3)=3^{k+1 }
    Thanks from Diligo
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2012
    From
    Earth
    Posts
    9

    Re: Prove by induction

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

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. prove by induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2009, 09:16 PM
  3. Prove by induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 26th 2008, 06:06 AM
  4. Induction to prove
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 25th 2008, 07:24 AM
  5. Prove by Induction
    Posted in the Calculus Forum
    Replies: 3
    Last Post: October 12th 2007, 10:31 AM

Search Tags


/mathhelpforum @mathhelpforum