4
$\begingroup$

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

$\endgroup$
4

5 Answers 5

5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
0
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you! I think you have a typo in the last line of the equalities: shouldn't there be $$ \sum_{m=1}^n \frac{1}{2^m}\left(2-\dfrac1{2^{n-m}}\right) = \sum_{m=1}^n \left(\frac{1}{2^{m-1}} - \frac{1}{2^{n}}\right) = \frac{1- (1/2)^n}{1/2} - \frac{n}{2^n} = 2- \frac{1}{2^{n-1}} - \frac{n}{2^n}$$ $\endgroup$
    – Don
    Nov 8, 2015 at 12:00
  • $\begingroup$ @Don Corrected. Thanks. $\endgroup$
    – Adhvaitha
    Nov 8, 2015 at 12:47
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.