Summation formula for this? I have found the following summation formula based on a recurrence. It supposes $n = 2^k$ where k is an integer. I've intuitively discovered that the following closed form may be true (following the constraint on n), but I'm not sure why. 
$\sum_{\textstyle i=0}^{\textstyle \lg n}  {\frac n{2^i}}\\
= n\sum_{\textstyle i=0}^{\textstyle \lg n} \frac 1{2^i}\\
= n(1+ \frac 12 + \frac 14 +...+ \frac 1n)\\
= 2n-1\\$
I've reasoned that the last line should be true because if I plug in n=32 the solution is 63, and if we think about the numbers being added as $1$s in a long bit string, we will end up with lg$n+1$ ones in a row. I'm wondering if there is a summation formula or inductive proof that can show that this is true? I'm just waving my hands thinking this must be true, but I can't be sure. 

Assuming the sum is $f(k) = 2^k \sum_{i=0}^k (\frac{1}{2})^i$:

$\sum_{i=0}^k (\frac{1}{2})^i = \frac{1-\frac{1}{2}^k}{\frac{1}{2}}$

It follows that this sum is
$$2^{k+1}(1-2^{-k}) = 2^{k+1}-2$$
