Trick to solving this Summation? I am currently following some slides I found to try and learn how to find the average case complexity for some algorithms. I got stuck when having to handle this summation though: 
$$\sum_{i=1}^k i*2^i $$
According to the slides: it can be shown that the the summation is equal to:  
$$(k - 1)·({2^k+1}) + 2  $$
Can somebody explain how to get to this answer? 
 A: Let's look at 
$$\sum_{i=0}^k r^i=\frac{1-r^{k+1}}{1-r}$$
which is the finite geometric series. If we now take the derivative of both sides with respect to $r$, we find
$$\frac{d}{dr}\sum_{i=0}^k r^i=\sum_{i=0}^k i*r^{i-1}=$$
$$\frac{d}{dr}\frac{1-r^{k+1}}{1-r}=-(k+1)\frac{r^k}{1-r}+\frac{1-r^{k+1}}{(1-r)^2}$$
Now multiply both sides by $r$ and let $r=2$:
$$\sum_{i=0}^k i*2^{i}=-2(k+1)2^k/(-1)+2(1-2^{k+1})/(-1)^2=(k+1)2^{k+1}+2-2*2^{k+1}$$
$$=(k-1)2^{k+1}+2$$
which is the true formula (I think you may have missed a bracket in yours).
A: Proof without derivatives:
Let us denote the sum as follows
$$
S(k):=\sum_{i=1}^k i\cdot 2^i
$$
Then we have
$$
S(k+1)=\sum_{i=1}^{k+1} i\cdot 2^i=S(k)+(k+1)\cdot2^{k+1}
$$
On the other hand we can deduce that
$$
S(k+1)=\sum_{i=1}^{k+1} i\cdot 2^i=\sum_{i=0}^k (i+1)\cdot 2^{i+1}=2\left(\sum_{i=0}^k i\cdot 2^i+\sum_{i=0}^k 2^i\right)=2(S(k)+2^{k+1}-1)
$$
Both identities are equal, so
$$
\begin{align*}
S(k)+(k+1)\cdot2^{k+1}&=2(S(k)+2^{k+1}-1)\\
S(k)&=(k+1)\cdot2^{k+1}-2(2^{k+1}-1)=(k-1)\cdot 2^{k+1}+2
\end{align*}
$$
A: $\sum_\limits{i=1}^k i*2^i = 1\cdot2 + 2\cdot2^2 + 3\cdot 2^3 +\cdots +k2^k$
Multiply by $-(1-2)$.
Since $-(1-2) = 1$ it doesn't change the value of the sum, but look what happens as you apply the distributive property.
$-(1-2)(1\cdot2 + 2\cdot2^2 + 3\cdot 2^3 +\cdots +k2^k) = -(1\cdot 2 - 1\cdot 2^2 + 2\cdot 2^2 - 2\cdot 2^3 + 3\cdot2^3 - 3\cdot2^4+\cdots - (k-1)2^k + k2^k - k2^{k+1})$
Simplify
$-(2 +2^2 + 2^3+2^4+\cdots 2^k - k2^{k+1})$
We can use the same gabit again, or you might just say that that is a more recognizable geometric series.
$-(2^{k+1} - 2 - k2^{k+1})\\
(k-1)2^{k+1} + 2$
