Summation formula for this?

Question

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.

Answer 1

This is an application of the formula $\sum_{i=0}^n x^i ={1-x^{n+1}\over 1-x}$. Here you have $x=1/2$.

Answer 2

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.

Answer 3

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