<s>[INST] 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.
 [/INST] 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.
</s>