Results 1 to 3 of 3

Math Help - Proof by induction (proving formula for sum of a series) ?

  1. #1
    Newbie
    Joined
    Nov 2013
    From
    Ireland
    Posts
    5

    Proof by induction (proving formula for sum of a series) ?

    The question is:
    Prove by induction for all positive integers n:
    1 + 2(2) + 3(2^2) + 4(2^) + ... n(2^(n-1)) = (n-1)(2^n) + 1

    I'm stuck on this and it's bothering me! Here are my workings so far:

    1. Show proposition is true for n=1
    LHS: P(1) = 1(2^(1-1)) = 1
    RHS: P(1) = (1-1)(2^1) + 1 = 1
    1=1
    => P(1) is true

    2. Assume that P(k) is true
    1 + 2(2) + 3(2^2) + ... k(2^(k-1) = (k-1)(2^k) + 1

    3. Prove P(k+1) is true, given P(k) is true
    To prove: 1 + 2(2) + 3(2^2) + ... k(2^(k-1)) + (k+1)(2^((k+1)-1) = (k)(2^(k+1)) + 1

    Proof:

    1 + 2(2) + 3(2^2) + ... k(2^(k-1) = (k-1)(2^k) + 1 (Assumption)
    Add new term:
    1 + 2(2) + ... k(2^(k-1)) + (k+1)(2^k) = (k-1)(2^k)+1 + (k+1)(2^k)

    (This is where it got a bit messy ...)
    = (4^k)(k) +1 ???????

    Could anyone please tell me where I have gone wrong?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,569
    Thanks
    1427

    Re: Proof by induction (proving formula for sum of a series) ?

    Quote Originally Posted by HABMD View Post
    The question is:
    Prove by induction for all positive integers n:
    1 + 2(2) + 3(2^2) + 4(2^) + ... n(2^(n-1)) = (n-1)(2^n) + 1

    I'm stuck on this and it's bothering me! Here are my workings so far:

    1. Show proposition is true for n=1
    LHS: P(1) = 1(2^(1-1)) = 1
    RHS: P(1) = (1-1)(2^1) + 1 = 1
    1=1
    => P(1) is true

    2. Assume that P(k) is true
    1 + 2(2) + 3(2^2) + ... k(2^(k-1) = (k-1)(2^k) + 1

    3. Prove P(k+1) is true, given P(k) is true
    To prove: 1 + 2(2) + 3(2^2) + ... k(2^(k-1)) + (k+1)(2^((k+1)-1) = (k)(2^(k+1)) + 1

    Proof:

    1 + 2(2) + 3(2^2) + ... k(2^(k-1) = (k-1)(2^k) + 1 (Assumption)
    Add new term:
    1 + 2(2) + ... k(2^(k-1)) + (k+1)(2^k) = (k-1)(2^k)+1 + (k+1)(2^k)

    (This is where it got a bit messy ...)
    = (4^k)(k) +1 ???????

    Could anyone please tell me where I have gone wrong?
    You're very close,

    $\displaystyle \begin{align*} \sum_{ r = 0 }^{k} { \left[ \left( r + 1 \right) 2^r \right] } &= \sum_{r =0}^{k - 1}{ \left[ \left( r + 1 \right) 2^r \right] } + \left( k + 1 \right) 2^k \\ &= \left( k - 1 \right) 2^k + 1 + \left( k + 1 \right) 2^k \\ &= \left( k - 1 \right) 2^k + \left( k + 1 \right) 2^k + 1 \\ &= 2^k \left( k - 1 + k + 1 \right) + 1 \\ &= 2^k \cdot 2k + 1 \\ &= k \cdot 2^{k + 1} + 1 \end{align*}$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2013
    From
    Ireland
    Posts
    5

    Re: Proof by induction (proving formula for sum of a series) ?

    Thanks a million, I think I understand now!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 4th 2013, 08:49 AM
  2. Replies: 1
    Last Post: November 14th 2012, 04:54 PM
  3. induction proof of de moivres formula
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 9th 2012, 05:06 AM
  4. Proof Tree induction - proving conjunction
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: October 16th 2011, 11:58 AM
  5. [SOLVED] Proof a recursive formula with induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 27th 2011, 02:50 PM

Search Tags


/mathhelpforum @mathhelpforum