How to Solve Summation by Hand I am having trouble solving the following summation by hand.
$$ \sum_{i=0}^{n-1} 2^i (n-i) $$
Can someone guide me in the right direction, especially for the $i \cdot 2^i$ part?
 A: Let
$s(n)
=\sum_{i=0}^{n-1} 2^i(n-i)
$.
I'm going to try
to go from $n$
to $n+1$
and see what happens.
$\begin{array}\\
s(n+1)-s(n)
&=\sum_{i=0}^{n} 2^i(n+1-i)-\sum_{i=0}^{n-1} 2^i(n-i)\\
&=\sum_{i=0}^{n} 2^i(n-i)+\sum_{i=0}^{n} 2^i-\sum_{i=0}^{n-1} 2^i(n-i)\\
&=\sum_{i=0}^{n-1} 2^i(n-i)+(2^{n+1}-1)-\sum_{i=0}^{n-1} 2^i(n-i)\\
&=2^{n+1}-1\\
\text{so that}\\
s(m)-s(0)
&=\sum_{n=0}^{m-1} (s(n+1)-s(n))\\
&=\sum_{n=0}^{m-1} (2^{n+1}-1)\\
&=\sum_{n=1}^{m} 2^{n}-m\\
&=2^{m+1}-2-m\\
\text{so that}\\
s(m)
&=s(0)+2^{m+1}-2-m\\
&=2^{m+1}-2-m
\qquad\text{since } s(0) = 0\\
\end{array}
$
It worked!
A: $$
(i+1)2^{i+1} - i 2^i = i 2^i + 2^{i+1}
$$
$$
\sum_{i=0}^{n-1} i 2^i = \sum_{i=0}^{n-1}[(i+1)2^{i+1} - i 2^i] - \sum_{i=0}^{n-1}2^{i+1} = n2^n-2^{n+1}+2
$$
A: Alternatively, one can use generating function method to find the sum: We know that
$$ \sum_{n=0}^{\infty} 2^n x^n = \frac{1}{1-2x}
\qquad \text{and} \qquad
\sum_{n=0}^{\infty} n x^n = \frac{x}{(1-x)^2}. $$
Thus it follows that
\begin{align*}
\sum_{n=0}^{\infty} \bigg( \sum_{i=0}^{n} 2^i (n-i) \bigg) x^n
&= \frac{1}{1-2x} \cdot \frac{x}{(1-x)^2} \\
&= \frac{2}{1-2x} - \frac{1}{1-x} - \frac{1}{(1-x)^2} \\
&= \sum_{n=0}^{\infty} ( 2^{n+1} - 1 - (n+1) ) x^n.
\end{align*}
Therefore 
$$ \sum_{i=0}^{n} 2^i (n-i) = 2^{n+1} - n - 2. $$
A: $\sum 2^i$ is a geometric series.
\begin{align}
\sum_{i=0}^{n-1} i2^i&=2\sum_{i=1}^{n-1}  i2^{i-1}\\&=2\sum_{i=1}^{n-1} \frac{d}{dx}\left(x^i\right)|_{x=2}\\&=2\frac{d}{dx}\sum_{i=1}^{n-1} \left(x^i\right)|_{x=2}\\
&=2\frac{d}{dx}\left(\frac{x(x^{n-1}-1)}{x-1}\right)|_{x=2}
\\&=2\frac{d}{dx}\left(\frac{x^{n}-x}{x-1}\right)|_{x=2}
\\&=2\frac{(x-1)(nx^{n-1}-1)-(x^n-x)}{(x-1)^2}|_{x=2} \\
&=2(n2^{n-1}-1-2^n+2)\\
&=2(n2^{n-1}-2^n+1)
\end{align}
A: Here's a hint: 
$$ \sum_{i=0}^k i 2^i = 2 + 2*2^2+ 3*2^3 + \dots + k* 2^k \\ 
 = ( 2 + 2^2 + 2^3 + \dots + 2^k ) \\
   + (2^2+2^3+\dots + 2^k) \\
   + \dots + (2^{k-1}+2^k) + (2^k) \\
 = 2(1+ \dots + 2^{k-1}) + \dots + 2^{k-1}(1+2) + 2^k \\
= 2(2^k-1)+2^2(2^{k-1}-1) + \dots + 2^{k-1}(2^2-1) \\
= (k-1) 2^{k+1} + 2^k - 2(1+2+\dots+2^{k-2}) \\
= (k-1) 2^{k+1} + 2.$$
Can you get it from here? 
A: Making the problem more general, consider $$A_n=\sum_{i=0}^{n-1} x^i (n-i)=n\sum_{i=0}^{n-1} x^i -\sum_{i=0}^{n-1} ix^i= n\sum_{i=0}^{n-1} x^i-x\sum_{i=0}^{n-1} ix^{i-1}$$ that is to say $$A_n=n\left(\sum_{i=0}^{n-1} x^i \right)-x\left(\sum_{i=0}^{n-1} x^i \right)'$$ $$\sum_{i=0}^{n-1} x^i= \frac{x^n-1}{x-1}$$ $$\left(\sum_{i=0}^{n-1} x^i \right)'=\frac{n x^{n-1}}{x-1}-\frac{x^n-1}{(x-1)^2}$$ which make $$A_n=\frac{x \left(x^n-1\right)-n x+n}{(x-1)^2}$$ which you could use for any value of $x$.
Making $x=2$ will give $A_n=2^{n+1}-n-2$.
