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. 

Let $m$ be a nonnegative integer.  Then $$\sum_{i=0}^m \frac{1}{2^i}$$ is simply a finite geometric series with common ratio $r = 1/2$.  In general, $$\sum_{i=0}^m r^i = \begin{cases} \frac{r^{m+1} - 1}{r - 1}, & r \ne 1, \\ m+1, & r = 1, \end{cases} \tag{1}$$ from which your desired result follows immediately.
The proof of $(1)$ is straightforward and is typically discussed in high school algebra.  One sees that the summation is telescoping for $r \ne 1$:
$$(r - 1) \sum_{i=0}^m r^i = \sum_{i=0}^m r^{i+1} - r^i = \sum_{i=0}^m r^{i+1} - \sum_{i=0}^m r^i = \sum_{i=1}^{m+1} r^i - \sum_{i=0}^m r^i = r^{m+1} - r^0 = r^{m+1} - 1.$$  And when $r = 1$, the summation is trivial.
