# 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.

• Is lg the natural logarithm? – Ryan Shesler Apr 18 at 2:33
• So you are interested in the sum $\sum_{i=0}^k\frac{2^k}{2^i}$? – Lord Shark the Unknown Apr 18 at 2:33
• Sorry, lg is $log_2$ – dover Apr 18 at 2:39

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

• Cool! I was thinking there must be some formula but I couldn't remember or my brain was fried... Thanks! – dover Apr 18 at 2:40
• Formulas are easy to forget! I believe that this is called a geometric series/sum if you want to look it up – munchhausen Apr 18 at 2:50

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.

• awesome, yes I can see it now. Thank you! – dover Apr 18 at 2:43
• @dover if you found this answer useful, please upvote and accept it as answered. – heropup Apr 19 at 4:15

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

• Thank you for your response, another helpful way to look at it! – dover Apr 18 at 3:24