# The sum of powers of two and two's complement – is there a deeper meaning behind this?

Probably everyone has once come across the following "theorem" with corresponding "proof": $$\sum_{n=0}^\infty 2^n = -1$$ Proof: $\sum_{n=0}^\infty q^n = 1/(1-q)$. Insert $q=2$ to get the result.

Of course the "proof" neglects the condition on $q$ for this formula, and the sum really diverges. However I now noticed an interesting fact:

If you use two's complement to represent negative numbers on computers, $-1$ is represented by all bits set. Also, sign extending to a larger number of bits (that is, getting the same number in two's complement representation on more bits) works by copying the left-most bit (also known as sign bit) into the additional bits on the left.

Now imagine that formally you sign-extend the number $-1$ to infinitely many bits. What you get is an infinite-to-the-left string of $1$s. Which, using the normal base-2 formula $n = \sum_k b_k 2^k$ (where $b_k$ is the bit k positions from the right, i.e. $b_0$ is the rightmost bit), that infinite string of $1$s translates into exactly the sum above! So in some sense we have an independent re-derivation of that equation.

Now my question is: Is there something deeper behind this? Somehow I cannot imagine it is just coincidential.

-
What does "sign-extend" mean? The reason the formula works out soundly is because the geometric series formula works out in the formal power series ring and in particular the $2$-adics. –  anon Jul 24 '12 at 19:53
see this and these p-adic link1 link 2. $-1$ is for all digits equal to $p-1$, $-2$ for all the digits at $p-2$ and so on. –  Raymond Manzoni Jul 24 '12 at 19:54
@anon I believe he means if you take some binary string, say $1001_{2}=-7$ using two's-complement in 4-bits, and then 'sign-extend' it to 8 bits, we'd have $11111001_{2}=-7$. –  Shaktal Jul 24 '12 at 19:56
@anon: I said what "sign extending to a larger number of bits" means in the parenthesis directly following that phrase (starting with "that is"), and described the mechanism how to do it afterwards in the same sentence. –  celtschk Jul 24 '12 at 20:35
Incidentally, infinite two's complement integers are found in Common Lisp, Ruby, and I have recently implemented them in a language called TXR. A negative value is taken to be infinitely padded with 1's, as if sign-extended out to infinity. Of course, the underlying bignums are stored in sign-magnitude, so this is just a charade perpetrated by the carefully implemented semantics of the bit operations. –  Kaz Sep 30 '12 at 17:43

Yes. What you are doing is known as working in the $2$-adic numbers.
The $2$-adic numbers are equipped with a curious notion of distance given by the $2$-adic metric. In this metric, two numbers are close together if their difference is divisible by a large power of $2$. In particular, large powers of $2$ are very small. So relative to the $2$-adic metric the geometric series you wrote down really does converge, and the value it converges to really is $-1$.
Yes. Large powers of $2$ get close to $0$ so the two's complement of a number, for sufficiently large powers of $2$, approximates the negative of that number $2$-adically. –  Qiaochu Yuan Jul 24 '12 at 19:57
All the $2$s on this page made me misinterpret the word odd at first glance. Perhaps unusual, or just different? –  Rahul Jul 24 '12 at 20:09