1
$\begingroup$

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.

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

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

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

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.

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.