How to compute this finite sum $\sum_{k=1}^n \frac{k}{2^k} + \frac{n}{2^n}$?

Question

I do not know how to find the value of this sum:

$$\sum_{k=1}^n \frac{k}{2^k} + \frac{n}{2^n}$$

(Yes, the last term is added twice).

Of course I've already plugged it to wolfram online, and the answer is $$2-\frac{1}{2^{n-1}}$$

But I do not know how to arrive at this answer.

I am not interested in proving the formula inductively :)

Answer 1

Take the following: $$ f_k(x)=\sum_{n=0}^k (c x)^n=\frac{1-(cx)^{k+1}}{1-c x} $$ Taking the derivative of both sides: $$ f'_n(x)=c \sum_{n=0}^{k-1} n (cx)^n=\frac{c (k+1) (c x)^k}{c x-1}-\frac{c \left((c x)^{k+1}-1\right)}{(c x-1)^2} $$ For your problem, just plug in $c=2^{-1}$ and $x=1$, and then add the final term.

Or you could just use the following identity: $$ \sum_{i=1}^n if(i)=\sum_{j=1}^n\left(\sum_{i=j}^n f(i)\right) $$

Answer 2

Let $$S=\sum_{k=1}^{n}\frac{k}{2^k}$$ or, $$S=\frac{1}{2^1}+\frac{2}{2^2}+\frac{3}{2^3}+\frac{4}{2^4}+\frac{5}{2^5}+....+\frac{n}{2^n}$$ and $$\frac{S}{2}= \frac{1}{2^2}+\frac{2}{2^3}+\frac{3}{2^4}+\frac{4}{2^5}+....+\frac{n-1}{2^n}+\frac{n}{2^{n+1}}$$ Subtracting we get, $$\frac{S}{2}= \frac{1}{2^1}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+\frac{1}{2^5}+....+\frac{1}{2^n}-\frac{n}{2^{n+1}}$$ or, $$S= 1+\frac{1}{2^1}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+....+\frac{1}{2^{n-1}}-\frac{n}{2^n}=2\left(1-\frac{1}{2^n}\right)-\frac{n}{2^n}$$

Answer 3

Here is a simple step by step approach. We decompose the sum into a geometric series and a telescoping series.

$$\eqalign{ & \sum\limits_{k = 1}^n {{k \over {{2^k}}}} = \sum\limits_{k = 1}^n {{{2k - k} \over {{2^k}}}} = \sum\limits_{k = 1}^n {{{2k} \over {{2^k}}} - {k \over {{2^k}}}} = \sum\limits_{k = 1}^n {{k \over {{2^{k - 1}}}} - {k \over {{2^k}}}} = \sum\limits_{k = 1}^n {{{k - 1 + 1} \over {{2^{k - 1}}}} - {k \over {{2^k}}}} \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\, = \sum\limits_{k = 1}^n {\left[ {\left( {{{k - 1} \over {{2^{k - 1}}}} - {k \over {{2^k}}}} \right) + {1 \over {{2^{k - 1}}}}} \right]} = \sum\limits_{k = 1}^n {{{k - 1} \over {{2^{k - 1}}}} - {k \over {{2^k}}} + \sum\limits_{k = 1}^n {{1 \over {{2^{k - 1}}}}} } \cr & \,\,\,\,\,\,\,\,\,\,\,\,\, = \left( {0 - {n \over {{2^n}}}} \right) + \left( {{{1 - {{\left( {{1 \over 2}} \right)}^n}} \over {1 - {1 \over 2}}}} \right) = - {n \over {{2^n}}} + \left( {2 - {1 \over {{2^{n - 1}}}}} \right) \cr & \cr & \sum\limits_{k = 1}^n {{k \over {{2^k}}}} + {n \over {{2^n}}} = 2 - {1 \over {{2^{n - 1}}}} \cr} $$

Answer 4

We have \begin{align} \sum_{k=1}^n \dfrac{k}{2^k} & = \sum_{k=1}^n \dfrac1{2^k} \sum_{m=1}^k 1 = \sum_{k=1}^n \sum_{m=1}^k \dfrac1{2^k} 1 = \sum_{m=1}^n \sum_{k=m}^n \dfrac1{2^k} = \sum_{m=1}^n \dfrac1{2^m} \sum_{k=0}^{n-m} \dfrac1{2^k} = \sum_{m=1}^n \dfrac1{2^m}\left(2-\dfrac1{2^{n-m}}\right)\\ & = 2-\dfrac1{2^{n-1}}-\dfrac{n}{2^n} \end{align} Hence, your sum is $2-\dfrac1{2^{n-1}}$.

Answer 5

A trick with generating functions:

$\begin{align} \sum_{k \ge 0} 2^{-k} z^k &= \frac{1}{1 - 2^{-1} z} \\ z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{2 (1 - 2^{-1} z)} &= \frac{z}{2 (1 - 2^{-1} z)^2} \\ &= \sum_{k \ge 0} k 2^{-k} z^k \\ \frac{1}{1 - z} \cdot \frac{z}{(1 - 2^{-1} z)^2} &= \sum_{n \ge 0} \sum_{0 \le k \le n} k 2^{-k} z^n \end{align}$

Thus you are interested in the coefficient of $z^n$ in the above:

$\begin{align} [z^n] \frac{z}{(1 - z) (1 - 2^{-1} z)^2} &= [z^n] \left( \frac{4}{1 - z} - \frac{2}{1 - 2^{-1} z} - \frac{2}{(1 - 2^{-1} z)^2} \right) \\ &= 4 - 2 \cdot 2^{-n} - 2 (n + 1) \cdot 2^{-n} \\ &= 4 - \frac{n + 2}{2^{n - 1}} \end{align}$