Finding closed-form expression for this sum

• Jul 12th 2014, 05:33 PM
ReneG
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
• Jul 12th 2014, 09:51 PM
Prove It
Re: Finding closed-form expression for this sum
Why do you think there is a simple closed form expression for this sum?
• Jul 12th 2014, 11:14 PM
ReneG
Re: Finding closed-form expression for this sum
The initial problem asks for a closed form expression, so I just assumed one existed.
• Jul 12th 2014, 11:53 PM
Prove It
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...
• Jul 13th 2014, 08:51 AM
topsquark
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
• Jul 13th 2014, 10:09 AM
ReneG
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)$
• Jul 13th 2014, 02:18 PM
Soroban
Re: Finding closed-form expression for this sum
(Rofl)Hello, ReneG!

Quote:

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}$