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.
$\endgroup$ 115 Answers
$\begingroup$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$.
$\endgroup$ 1 $\begingroup$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 $$
$\endgroup$ $\begingroup$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$
$\endgroup$ 2 $\begingroup$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....
$\endgroup$ 5 $\begingroup$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*}
$\endgroup$
