Finding closed form for $\sum_{k=1}^n k2^{k-1}$

Question

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.

Answer 1

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).

Answer 2

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.

Answer 3

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$$

Answer 4

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