Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Solve $n + n/2 + n/4 + n/8 + \dots$ up to $\log n$ terms

This looks like Harmonic series. But I couldn't find a formula to calculate the sum of the series up to $\log n$ terms. Can anyone solve it please.

share|cite|improve this question
up vote 8 down vote accepted

It's $n$ times the geometric series $1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots \frac{1}{2^{\log n - 1}}$. Do you know how to find the value of a geometric sum?

share|cite|improve this answer
Are you sure? Because I tried with some practical values, but there was a large deviation. GP yielded very complex calculations. Isn't there any easy formula for this. – Vishnu Vivek Nov 26 '12 at 9:15
@VISHNUVIVEK The geometric sum formula is pretty easy. Can you include the calculations in your question so that others can check that it corresponds to the sum you wrote (or vice-versa)? – anon Nov 26 '12 at 19:10

I'll start by making some simplifications. Since you didn't specify the base for your log function, I'll assume that it is some integer $b>1$. Also, since it wasn't completely clear what you meant by "up to $\log n$ terms", I'll assume that we want $\log n$ to be an integer. Neither of these assumptions are necessary; they just make calculations easier.

Since $\log_bn$, the number of terms, is assumed to be an integer, we must have $n=b^k$ for some integer $k>0$. Then your expression will be $$ b^k(\underbrace{1+\frac{1}{2}+\frac{1}{4}+\cdots + \frac{1}{2^{k-1}}}_{k\text{ terms}})=b^k\left(\frac{1-(1/2^k)}{1-(1/2)}\right)=2b^k\left(1-\frac{1}{2^k}\right) $$ by the formula for the sum of a geometric series. Now since we assumed $n=b^k$ we'll see that your sum will be $$ 2b^k\left(1-\frac{1}{2^k}\right)=2n\left(1-\frac{1}{2^{\log_bn}}\right)=2n\left(1-\frac{1}{n^{\log_b2}}\right) $$ using the useful and frequently-forgotten identity $a^{\log_bc}=c^{\log_ba}$. As a reality check, if $b=2$ and $k=4$ (so $n=2^4=16$) we'll have the sum $$ 16\left(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}\right)=30=32\left(1-\frac{1}{16}\right)=2\cdot16\left(1-\frac{1}{16^{\log_22}}\right) $$

share|cite|improve this answer

Let us assume that $n=2^k$ and let your sum be $S=\sum_{i=0}^k n 2^{-k}$. Then $S$ denotes the number of nodes in a complete balanced binary tree of height $k$ with $n$ leaves. Such a tree has $2^{k+1}-1$ nodes, which can be easily shown by induction. Thus in your case we have $S=2n-1$.

share|cite|improve this answer
For this kind of thing I usually write the numbers in binary. e.g. $32 = {10000}_2$. 32 / 2 = 32 >> 1 = {1000}_2 (shift right one place), likewise $n 2^{-k} = n >> k$, so $32 (1 + 1/2 + 1/4 + ... ) = 10000 + 1000 + 100 + 10 + 1$, if you take that number and add another one, it will be carry all over until it settles putting one more one to the left. In this case: 11111 + 1 = 100000 (which is effectively multiplying 32 by 2). So 100000 - 1 = 11111, and the same can be done for any integer power of two. – Gastón Bengolea Oct 15 '14 at 3:33

protected by user26857 Dec 13 '15 at 16:52

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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