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

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