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
 A: Let $n= 2^p$ where $p = 1, 2, 3, ...$
$2n = n + n$
$2n  = n + n/2 + n/4 + n/4$
Similarly, it can be expanded as
$2n = n + n/2 + n/4 + n/8 + .....+ n/2^p  + n/2^p$ 
$2n = n + n/2 + n/4 + n/8 + n/16 + ......+ 1 + 1$ where ($n = 2^p$)
$n + n/2 + n/4 + n/8 + n/16 + ......+ 1  = 2n - 1$
A: 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$.
A: The formula provided on the wikipedia page works if you know how many terms you are adding. For example, if you want to calculate the sum $1 + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + \dots \frac{1}{2^9}$, you know you are adding 10 terms (so $n = 10$). Also, $a = 1$ (the number you begin with) and $r = \frac{1}{2}$ (the common ratio). Now you could use the provided formula to calculate the sum:
\begin{align*}
a \frac{1-r^n}{1-r} &= 1 \frac{1 - \left(\frac{1}{2}\right)^{10}}{1 - \frac{1}{2}}\\
&= \frac{1 - \frac{1}{2^{10}}}{\frac{1}{2}}\\
&= 2(1 - \frac{1}{2^{10}})\\
&= 2 - \frac{2}{2^{10}}\\
&= 2 - \frac{1}{2^9}
\end{align*}
You are talking abouth the sum $a + \frac{a}{2} + \frac{a}{4} + \dots + 1$, so the last term is 1, instead of $ar^{n-1}$. Note that $r = \frac{1}{2}$ in your case, as each term is twice as small as the term before. The formula could still solve this problem, but you will have to set $a\left(\frac{1}{2}\right)^{n-1}$ equal to 1:
\begin{align*}
a\left(\frac{1}{2}\right)^{n-1} &= 1\\
a &= \frac{1}{\left(\frac{1}{2}\right)^{n-1}} = \frac{1}{\frac{1}{2^{n-1}}} = 2^{n-1}
\end{align*}
So, your formula will only work when $a$ is a power of two. For example, if $a = 4$:
$$
4 + 2 + 1 = 7 = 8 - 1 = 2*4 - 1
$$
So for $a=4$, your formula works. Let's try $a = 16$:
$$
16 + 8 + 4 + 2 + 1 = 31 = 32 - 1 = 2 * 16 - 1
$$
Again, your formula works. How would we prove this? The formula you found on wikipedia has a $r^n$ term that we would like to get rid of:
\begin{align*}
a\left(\frac{1}{2}\right)^{n-1} &= 1\\
\left(\frac{1}{2}\right)^{n-1} &= \frac{1}{a}\\
\left(\frac{1}{2}\right)^n &= \frac{1}{a} * \frac{1}{2} = \frac{1}{2a}
\end{align*}
So, $r = \frac{1}{2}$ and $r^n = \left(\frac{1}{2}\right)^n = \frac{1}{2a}$. Now, let's plug that in:
\begin{align*}
a \frac{1-r^n}{1-r} &= a \frac{1 - \frac{1}{2a}}{1 - \frac{1}{2}}\\
&= a \frac{1 - \frac{1}{2a}}{\frac{1}{2}}\\
&= 2a(1 - \frac{1}{2a})\\
&= 2a - \frac{2a}{2a}\\
&= 2a - 1
\end{align*}
So there you have it: for every $a = 2^k$ (with $k \in \mathbb{N}$):
$$
a + \frac{a}{2} + \frac{a}{4} + \dots + 1 = 2a - 1
$$
A: If you have knowledge of progression than this is a geometric series with common ratio of $\frac{1}{2}$ and formula you have written is sum to n terms of geometric progression. 
But you  require to calculate the sum of this series upto $2n-1$ term, so you can replace $n$ with $(2n-1)$ and then proceed. Here , $a = n$ (which is your first term).
So, by putting these values we get : $\frac{a(1-r^{2n-1})}{1-r}$ = 
$\frac{n(1-(\frac{1}{2})^{2n-1})}{1-\frac{1}{2}}$
I hope from here you  will get your answer.... 
A: Assuming $n$ is a power of $2$, say $n = 2^p$. Then the sum is
$$
S = n + \frac n2 + \frac n4 + \ldots + 1 =
2^p + 2^{p-1} + 2^{p-2} + \ldots + 1.
$$
Multiply by $2$ on both sides to get
$$
2S_p = 2^{p+1} + 2^p + 2^{p-1} + \ldots + 2.
$$
Compute the difference $2S_p - S_p$ using the two equations above:
\begin{align*}
2S_p - S_p & = 2^{p+1} - 1 \\
\therefore S_p & = 2^{p+1} - 1 = 2n - 1.
\end{align*}

For a discussion of the general series, suppose $a \ne 1$ and $p \in \mathbb N$ are given, and suppose we want to compute
$$
S = 1 + a + a^2 + \ldots + a^p = \sum_{i=0}^p a^i.
$$
We can use the same idea as above: multiply by $a$ to get
$$
aS = a + a^2 + a^3 + \ldots + a^{p+1} = \sum_{i=1}^{p+1} a^i.
$$
Compute the difference:
\begin{align*}
aS - S & = a^{p+1} - 1 \\
(a - 1)S & = a^{p+1} - 1\\
S & = \frac{a^{p+1} - 1}{a - 1}.
\end{align*}
