How is "n+n/2+n/4....1" equal to "2n-1" using the formula for geometric series? I never knew not having good knowledge of basic maths will be so crippling!! So please help me out this time. I'll be working on my maths from today on.
I was discussing about complexity of an algorithm on StackOverflow and I was told that the series $n+n/2+n/4 + \dots + 1$ evaluates to $2n-1$ and I was linked to the following formula on Wikipedia:

Even after trying hard, I regret to say I still don't get it how using this formula I can conclude that my series evaluates to $2n-1$. Please help me out as I am sure it will take only a few seconds for you.
https://stackoverflow.com/questions/16748454/complexity-for-nested-loops-diving-by-2?noredirect=1#comment24124682_16748454

Firstly, in the linked StackOverflow question, the program does integer division at each step, so "n/2" in that context actually means the greatest integer less than or equal to $\frac{n}{2}$: more correctly, it should be written as $\left\lfloor \frac{n}{2} \right\rfloor$ (where $\left\lfloor x \right\rfloor$ is the floor function, e.g. $\left\lfloor \frac{7}{2} \right\rfloor = \left\lfloor 3.5 \right\rfloor = 3$).
Secondly, you missed a clause mentioned at the linked StackOverflow question: the correct statement is that if $n$ is a power of $2$, then $\left\lfloor n \right\rfloor + \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n}{4} \right\rfloor + \dots$ (which in this case is the same as $n + \frac{n}2 + \frac{n}4 + \dots + 1$) is exactly $2n - 1$.
For this special case when $n$ is a power of $2$ (which is what it takes for all the numbers $\frac{n}2, \frac{n}4, \dots$ to be integers, all the way to $1$), this is easy to prove. When $n$ is a power of $2$, say $n = 2^k$, the sum is 
$$2^k + \frac{2^k}{2} + \frac{2^k}{4} + \dots + 1 
= 2^k + 2^{k-1} + 2^{k-2} + \dots + 1
= 2^{k+1} - 1
= 2n - 1
$$
For example, $16 + 8 + 4 + 2 + 1 = 31$.
This can be proved by induction, or it follows from the formula for the geometric series, which states that $$a + ar + ar^2 + \dots + ar^{m-1} = a\frac{1-r^m}{1-r}.$$
In this case, we have $a = n = 2^k$, $r = 1/2$, and $m$ (the number of terms) is $k+1$, so the left-hand side is the sum $n + \frac{n}{2} + \dots + 1$, and the right-hand side is $$n \frac{1 - (1/2)^{k+1}}{1 - (1/2)} = n\frac{2 - (1/2)^k}{1} = 2n - n/2^k = 2n - 1.$$

But more generally, when $n$ need not be a power of $2$, still we can upper-bound the sum by $n + \frac{n}{2} + \frac{n}{4} + \dots$ (all the way to infinitely many terms). The formula for the infinite geometric series (when $|r| < 1$) is 
$$a + ar + ar^2 + \dots = a\frac{1}{1-r}.$$
Here with $a = n$ and $r = 1/2$, we have $$n + \frac{n}{2} + \dots = n\frac{1}{1-1/2} = 2n.$$ 
As our finite sum is an integer strictly less than this upper bound, we can say it's at most $2n - 1$.
