How to compute this finite sum $\sum_{k=1}^n \frac{k}{2^k} + \frac{n}{2^n}$? 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 :) 
 A: 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)
$$
A: 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}}$.
A: 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}$$
A: 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} $$
A: 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}$
