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

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