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

Answer

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