Sum n, n/2, n/4, ...

Question

Stackoverflow, I am trying to train my old analysis knowledge from back in the day and did come to the following question: Imagine I am on a number line at zero and I would like to go to a number $n$. I am doing this in the following way: I go 1 to the left $(-1)$, 2 to the right $(-1+2=1)$, 4 to the left $(1-4=-3)$, 8 to the right $(-3+8=5)$ and so on, until I reach $n$. Now I would like to know how many natural numbers I have passed this way. So in fact, the length of my entire "way" from 1 to $n$ was $2n+n+n/2+n/4+n/8$ ... So in the end its something like the sum of $n/(2^x)$, so it is: $$\sum_{i=1}^{x} \frac{n}{2^i}.$$ I might got it wrong. If it is correct, how many $n$ do I get in the end? It looks a little bit lake the geometric series, but I am absolutely unsure.

Answer 1

The formula for the geometric series is: $$ \sum_{i=0}^N q^i = \frac{1-q^{N+1}}{1-q}. $$ Applied to your problem, $$ \sum_{i=1}^x \frac{n}{2^i} =n \sum_{i=0}^x \frac{1}{2^i} -n = n \frac{1-\tfrac{1}{2^{x+1}}}{\tfrac{1}{2}} - n = 2n (\tfrac{1}{2}- 2^{-1-x}) .$$