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

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