Find the sum of $k/2^k, k=1$ to $n$

Question

Let $S=1/2+2/2^2+3/2^3+...+n/2^n$

I try searching on the internet and see only the version of $k=1$ to infinity. I put this equation on Wolfram Alpha and get $(2^{n+1}-n-2)/2^n$ but I dunno how to do that. Please help

Answer 1

This is an example of what is called an arithmetico-goemetric series. We can write it more compactly as $$S_n = \displaystyle\sum\limits_{k=1}^n \frac{k}{2^k}$$

The common ratio for the denominators is $2$, so we will multiply the entire series by $2$:

\begin{align} S_n &= \,\qquad\frac{1}{2} +\frac{2}{4} +\frac{3}{8} +\frac{4}{16} + \cdots + \frac{n-1}{2^{n-1}} + \frac{n}{2^n}\tag{1}\\\\ 2S_n&=\,\,1 +\frac{2}{2} + \frac{3}{4} + \frac{4}{8} +\frac{5}{16} +\cdots +\frac{n}{2^{n-1}} \qquad\tag{2}\\ \end{align}

Subtract $(1)$ from $(2)$:

$$2S_n - S_n = \left(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots + \frac{1}{2^{n-1}} \right) - \frac{n}{2^n}$$

Everything on the right hand side, except the last term, is a finite geometric series with common ratio $1/2$.

\begin{align} S_n &= \left(2-\frac{1}{2^{n-1}}\right) - \frac{n}{2^n}\\\\ S_n &= \left(\frac{2^{n+1}}{2^{n}}-\frac{2}{2^{n}}\right) - \frac{n}{2^{n}}\\\\ \displaystyle\sum\limits_{k=1}^n \frac{k}{2^k} &= \boxed{\frac{2^{n+1}-n-2}{2^{n}}}\\\\ \end{align}

---

The exact same method works even more cleanly for the corresponding infinite series. We can also take the limit of the partial sums:

$$S = \displaystyle\sum\limits_{k=1}^\infty \frac{k}{2^k} = \lim_{n\to\infty} S_n = \lim_{n\to\infty}\left(\frac{2^{n+1}-n-2}{2^{n}}\right) = 2$$

Answer 2

Hint: The most direct way is to replace $\frac12$ with general $a\ne1$ and consider the product: $$ (1-a)^2\sum_{k=1}^n ka^k. $$

You will find that the series telescopes with a simple result. In fact it is the same method which works with geometric series.