Finding closed form for $\sum_{k=1}^n k2^{k-1}$ I am trying to use the perturbation method to find a closed form for:
$$
S_n = \sum_{k=1}^n k2^{k-1}
$$
This is what I’ve tried so far:
$$
S_n + (n+1)2^n = 1 + \sum_{k=2}^{n+1} k2^{k-1}
$$
$$
S_n + (n+1)2^n = 1 + \sum_{k=1}^{n} (k+1)2^{k}
$$
$$
S_n + (n+1)2^n = 1 + \sum_{k=0}^{n-1} k2^{k-1}
$$
$$
S_n + (n+1)2^n = 1 + 0 + n2^{n-1} + \sum_{k=1}^{n} k2^{k-1}
$$
But I don’t think it is right since it would result in a $S_n - S_n = ...$ 
Could you please help me?
Thank you very much.
 A: HINT:
$$
\sum_{k=1}^n k2^{k-1}=\left(\sum_{k=1}^n 2^{k-1}\right)+\left(\sum_{k=2}^n 2^{k-1}\right)+\ldots
$$
and every sum in parentheses is easy to compute. (And the sum of them also).
A: You have
$$S_n=\sum_{k=1}^n k 2^{k-1}=1\cdot 2^0 +2\cdot 2^1+3\cdot 2^2+\cdots+n2^{n-1}=$$
$$=\big(2^0+2^1+2^2+\cdots+2^{n-1}\big)+\big(1\cdot 2^1+2\cdot 2^2+\cdots+(n-1)2^{n-1}\big)=\quad (*)$$
$$=\sum_{k=0}^{n-1}2^k+2\big(1\cdot 2^0+2\cdot 2^1+\cdots+(n-1)2^{n-2}\big)=\quad (**)$$
$$=(2^n-1)+2 S_{n-1}.$$
So,
$$S_n=(2^n-1)+2(S_n-n2^{n-1}).$$
And you can get $S_n$ from there.

(*) I'm using the fact that if I have
$$1\cdot 2^0+2\cdot 2^1+3\cdot 2^2+4\cdot 2^3+\cdots,$$
that means that I have $2^0$ once, $2^1$ added twice, $2^2$ added three times, $2^3$ four times, and so on. So next I took just one of each to form the sum
$$2^0+2^1+2^2+2^3+\cdots$$
and the original sum ends up whith one less $2^0$ (that is, with none), one less $2^1$ (so just only one), one less $2^2$ (just two), one less $2^3$ (just three, instead of the original four), etc.
Let's put it backwards: if you sum
$$2^0+2^1+2^2+2^3+\cdots$$
and
$$[0\cdot 2^0]+[1]\cdot 2^1 +2\cdot 2^2 +3\cdot 2^3+\cdots$$
(I put between squared brackets what you wouldn't usually type explicitly),
you would get the original
$$1\cdot 2^0+2\cdot 2^1+3\cdot 2^2+4\cdot 2^3+\cdots.$$
(**) Now, going back to the decomposition in two sums we've got: I finally took out a common factor $2$ from the second sum to get back all terms in which the exponent of the $2$ is one less than the coefficient by which it is multiplied, which caracterizes the terms of $S_n$.

Notes:
The answer is, naturally,
$$S_n=1-2^n+n2^n=1+(n-1)2^n.$$
This is a perturbation process, since I wrote $S_n$ in terms of $S_{n-1}$, from which I made $S_n$ reappear. I could have started from $S_{n+1}$, too, and reduce it to an expression on $S_n$, like in
$$S_{n+1}=2^{n+1}-1+2S_n.$$
Then I could have gone on like
$$S_n+(n+1)2^n=2^{n+1}-1+2S_n,$$
and the same result would arise from this equation.
A: Fix $n$, and define a function
$$f(x)=\sum_{k=1}^nx^k$$
Note that for $x\neq 1$:
$$f(x)(1-x)=x-x^{n+1}$$
hence, for $x\neq 1$:
$$f(x)=\frac{x-x^{n+1}}{1-x}$$
Now differentiate $f$:
$$f'(x)=\sum_{k=1}^nkx^{k-1}$$
but also:
$$f'(x)=\frac{nx^{n+1}-(n+1)x^n+1}{(x-1)^2}$$
so we deduce that for every $x\neq 1$:
$$\sum_{k=1}^nkx^{k-1}=\frac{nx^{n+1}-(n+1)x^n+1}{(x-1)^2}$$
In particular, for $x=2$:
$$\sum_{k=1}^nk2^{k-1}=2^nn-2^n+1$$
A: Note the mistake: $\sum_{k=1}^{n} (k+1)2^{k}\ne \sum_{k=0}^{n-1} k2^{k-1}$.
Here is the right way:
$$\begin{align}S_n + (n+1)2^n &= 1 + \sum_{k=1}^{n} (k+1)2^{k}=\\
&=1+\sum_{k=0}^{n-1} (k+2)2^{k+1}=\\
&=1+\color{blue}{\sum_{k=0}^{n-1} k\cdot 2^{k+1}}+\color{red}{\sum_{k=0}^{n-1}2^{k+2}}=\\
&=1+\color{blue}{\sum_{k=0}^n k\cdot 2^{k+1}-n\cdot 2^{n+1}}+\color{red}{4(2^n-1)}=\\
&=1+4\sum_{k=0}^nk\cdot 2^{k-1}-n\cdot 2^{n+1}+4(2^n-1)=\\
&=1+4S_n-n\cdot 2^{n+1}+4(2^n-1) \Rightarrow \\
3S_n&=(n+1)2^n-1+n\cdot 2^{n+1}-4(2^n-1)=\\
&=3n\cdot 2^n-3\cdot 2^n+3 \Rightarrow \\
S_n&=n\cdot 2^n-2^n+1.\end{align}$$
