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