Results 1 to 7 of 7
Like Tree4Thanks
  • 1 Post By topsquark
  • 3 Post By Soroban

Math Help - Finding closed-form expression for this sum

  1. #1
    Junior Member ReneG's Avatar
    Joined
    Mar 2013
    From
    United States
    Posts
    70
    Thanks
    9

    Finding closed-form expression for this sum

    How would one begin to find a simple formula for

    S_m = \sum_{n=1}^{m} n(2^n)

    I have no idea where to begin
    Follow Math Help Forum on Facebook and Google+

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

    Re: Finding closed-form expression for this sum

    Why do you think there is a simple closed form expression for this sum?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member ReneG's Avatar
    Joined
    Mar 2013
    From
    United States
    Posts
    70
    Thanks
    9

    Re: Finding closed-form expression for this sum

    The initial problem asks for a closed form expression, so I just assumed one existed.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,831
    Thanks
    1602

    Re: Finding closed-form expression for this sum

    Well to start it might be worth writing out a cumulative sum and see if you can see a pattern...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1

    Re: Finding closed-form expression for this sum

    It does have a closed form. See here. You can always do an induction proof from here, but I have no clue how to derive it from scratch.

    -Dan
    Thanks from ReneG
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member ReneG's Avatar
    Joined
    Mar 2013
    From
    United States
    Posts
    70
    Thanks
    9

    Re: Finding closed-form expression for this sum

    If I recall correctly, the following is a property of sums
    \begin{align*} \sum_{n=1}^{m}n(2^n) &= \sum_{n=1}^{m}n\sum_{n=1}^{m}2^n \end{align*}

    On the RHS, the first sum obviously becomes \frac{m(m+1)}{2}

    I found the 2nd sum by letting

    \begin{align*}\ S_n &= 2 + 2^2 + 2^3 + ... + 2^n \\ 2S_n &= 2^2 + 2^3 + 2^4 + ... + 2^n + 2^{n+1}\end{align*}

    Subtracting S_n from 2S_n yields

    S_n = 2^{n+1} - 2 = 2(2^n) - 2 = 2(2^n -1)

    Plugging back in...

    \begin{align*} \sum_{n=1}^{m}n\sum_{n=1}^{m}2^n &= \frac{2m(m+1)(2^m - 1)}{2} \\ &= (m^2+m)(2^m - 1)\end{align*}

    Is any of my reasoning is even correct? I have no idea how Wolfram Alpha got 2(2^{m} m - 2^m + 1)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,914
    Thanks
    779

    Re: Finding closed-form expression for this sum

    (Rofl)Hello, ReneG!

    Find a closed-form expression for: . S_n \:=\: \sum_{i=1}^{n} n(2^n)

    \begin{array}{ccccccc}\text{We are given:} & S_n &=& 1\cdot2 + 2\cdot 2^2 + 3\cdot 2^3 + 4\cdot2^4 + \cdots + n\cdot2^n \qquad\qquad\qquad & [1] \\ \text{Mult. by 2:} & 2S_n &=& \qquad\quad 1\cdot2^2 + 2\cdot 2^3 + 3\cdot 2^4 + \cdots + (n-1)2^n + n\cdot2^{n+1} & [2]  \\ \text{Subtract [1] - [2]:} & -S_n &=& 2 + 2^2 + 2^3 + 2^4 + \cdots + 2n - n\cdot 2^{n+1}\qquad\qquad\qquad\qquad  \end{array}

    \text{We have: }\: -S_n \;=\; \underbrace{2 + 2^2 + 2^3 + 2^4 + \cdots + 2n}_{\text{geometric series}} - n\cdot 2^{n+1}\;\;[3]

    The geometric series has: first term a = 2, common ratio r = 2 and n terms.
    . . Its sum is: . 2\cdot\frac{2^n-1}{2-1}\:=\:2(2^n-1)

    Hence, [3] becomes: . -S_n \;=\;2(2^n-1) - n\cdot2^{n+1} \quad\Rightarrow\quad -S_n \;=\;2^{n+1} - 2 - n\cdot2^{n+1}

    . . -S_n \;=\;-2 - (n-1)2^{n+2} \quad\Rightarrow\quad \boxed{S_n \;=\;(n-1)2^{n+1} + 2}
    Thanks from ReneG, topsquark and Prove It
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. closed-form expression and induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 14th 2013, 01:04 PM
  2. Replies: 1
    Last Post: November 29th 2012, 04:59 PM
  3. Finding Closed form
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 5th 2009, 10:42 AM
  4. Finding Closed Form
    Posted in the Algebra Forum
    Replies: 0
    Last Post: October 4th 2009, 07:51 AM
  5. Prooving that normal CDF has no closed-form expression
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: October 6th 2008, 10:51 AM

Search Tags


/mathhelpforum @mathhelpforum