How would one begin to find a simple formula for

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

I have no idea where to begin

Printable View

- Jul 12th 2014, 05:33 PMReneGFinding closed-form expression for this sum
How would one begin to find a simple formula for

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

I have no idea where to begin - Jul 12th 2014, 09:51 PMProve ItRe: 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 PMReneGRe: 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 PMProve ItRe: 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 AMtopsquarkRe: 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 AMReneGRe: Finding closed-form expression for this sum
If I recall correctly, the following is a property of sums

$\displaystyle \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 $\displaystyle \frac{m(m+1)}{2}$

I found the 2nd sum by letting

$\displaystyle \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 $\displaystyle S_n$ from $\displaystyle 2S_n$ yields

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

Plugging back in...

$\displaystyle \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 $\displaystyle 2(2^{m} m - 2^m + 1)$ - Jul 13th 2014, 02:18 PMSorobanRe: Finding closed-form expression for this sum
(Rofl)Hello, ReneG!

Quote:

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

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

$\displaystyle \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 $\displaystyle a = 2$, common ratio $\displaystyle r = 2$ and $\displaystyle n$ terms.

. . Its sum is: .$\displaystyle 2\cdot\frac{2^n-1}{2-1}\:=\:2(2^n-1)$

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

. . $\displaystyle -S_n \;=\;-2 - (n-1)2^{n+2} \quad\Rightarrow\quad \boxed{S_n \;=\;(n-1)2^{n+1} + 2}$