1 + 2 + 4 + 8 + 16 + 32... = -1 ?!

[Frylock]

In this thread someone points out you seemingly can derive the equation 1+2+4+8+16+... = -1 as follows:

x = 1+2+4+8+16+...
x = 1+2(1+2+4+8+...)
x = 1+2x
x = -1

My question is, what do mathematicians take to be the right way to respond to this.

Is there a consistent way to build a mathematics of such "sums"? Or do there turn out to be more than one way to "sum" some infinite series? If the latter, then do we rule out such sums on this basis, or come up with a math which takes into account not only the members of the list of addends but also their order and groupings?

Or do we just call these kinds of sums "undefined" and move on?

It appears to me that there are some infinite sums which do not come out to a nice neat answer like this one does (I think 1+2+3+4+5... is an example of this), while some (like this one) do. Am I right to think this is the case? Or is there some way to find such a "sum" for any arbitrary infinite list of addends?

And so on.

-FrL-

[Giles]

The series 1+2+4+8+16+... does not have a limit, so it's meaningless to do arithmetic with it.[/quote]

[Frylock]

Originally Posted by Giles

The series 1+2+4+8+16+... does not have a limit, so it's meaningless to do arithmetic with it.

[/quote]

So mathematicians say that a "sum" like this is undefined?

It seems so weird that it come out so nicely and neatly to a simple answer of -1. I'm used to seeing "undefined" appear wherever an answer to a problem ends u being something that intuitvely looks to me like infinity. In my head I think I have almost unconsciously conflated the two.

So am I right to suspect that if you changed the order of the numbers in the list, or changed the way you group them in your derivation, you can get nice neat little answers other than -1?

-FrL-

[Frylock]

Hmm... can anyone explain anything from the following: Theorems on methods for summing divergent series to a(n intelligent) layman?

-FrL-

[Frylock]

Ah... I bet if someone could explain this comment from here:

In fact, if instead of using the absolute value for our metric we used the 2-adic valuation, the sum honestly converges to -1.

then I'd start to understand. Whats a metric? Whats a 2-adic valuation?

-FrL-

[Sunspace]

But you can also do this:

x = 1+2+4+8+16+...
x = 1+2+4(1+2+4+8+...)
x = 1+2+4x
x-4x = 3
-3x = 3
x = -1

Oh, wait. It comes out the same. So... um... I dunno. I thought it was going to come out with a different value of x, and then it would be like dividing by zero, where if you allow it, you can prove that 1 = 2.

[Napier]

I think that the problem is that you are dealing with infinities. It's obvious that x is infinite in the first line. What is less obvious is that infinity would be a solution to the equation x = 1+2x. And I'm not sure how correct I am in saying that. But, I don't see how you could say that twice infinity plus one would not be infinity, so infinity would have to be a solution, wouldn't it? Though, this doesn't explain why -1 wouldn't also be a solution.

[Giles]

There's some weird voodoo going on there. If you assume that the limit is a number s, you can prove that it's -1, and that's consistent with some other facts about this kind of series. However, the partial sums are clearly always positive, so if it had a limit, the limit would have to be positive (or possibly zero) -- the limit can't be -1. So what G.H. Hardy seems to have done might work in some axiom system, but it doesn't work in ordinary real or complex analysis.

[Colophon]

Well, it's obvious. You keep adding in an infinite series, you'll go right round the back of the number line and come up the other side at -1.

[ZenBeam]

Isn't the "2-adic valuation" bit related to 2s complement? For a 4 bit signed number, you have the following binary representations

0 = 0000
1 = 0001
...
7 = 0111
-8 = 1000
-7 = 1001
...
-1 = 1111

so -8 + -4 + -2 + -1 becomes(*) in binary

1000 + 1100 + 1110 + 1111 = 0001

or -8 + -4 + -2 + -1 = 1

This generalizes for N-bit 2s complement numbers.

I think this is why Sunspace is getting the same result, instead of being able to get an arbitrary result, like you'd expect to be able to get from infinity - infinity.

(*)I can't sum 8 + 4 + 2 + 1 because there is no +8. If you interpret 1000 as +8 instead of -8, you could.

[Giles]

Originally Posted by ZenBeam

Isn't the "2-adic valuation" bit related to 2s complement?

I think that works (in this case), except that you need to represent integers with an unlimited number of bits. For positive integers, you have a infinite number of 0's, followed by the usual binary representation; for negative integers, you have an infinite number of 1's, followed by the usual 2's-complement representation, e.g.:

+8 = ...0000000001000
-8 = ...1111111110111

So the sum looks like this:

...0000000000001 (+1)
...0000000000010 (+2)
...0000000000100 (+4)
...0000000001000 (+8)
......
____________________
...1111111111111 (-1)

Of course, that's not normal arithmetic, or even normal computer arithmetic.

[CalMeacham]

The problem is that, as Napier points out, the sum on the right diverges, so you
ve got infinity on the right. Then you equate that infinity to 1 plus two times itself, whivh is correct -- it's just as infinite, and you can make a one-to-one correspondence of the terms (except the one). What you can't do, themn, is subtract the one from the other as you could in "normal" math. Infinities don't behanve nicely when you do that, no matter how they're written.


Notyice that, if you replace this infinite sum with something similar that converges, like x = 1 + (1/2) + (1/4) + (1/8)+... and do the same steps, everything works out fine, and you get x = 2. But that's because you;re not trying to subtract one infinity from another, but one finite sum from another (even though both have an infinite number of sums).


As it stands, yor "proof" is like those proofs that rely on a "hidden" division by zero -- you get in trouble because you're trying to use infinity as if it's just another number. It ain't.

[gazpacho]

Originally Posted by ZenBeam

Isn't the "2-adic valuation" bit related to 2s complement? For a 4 bit signed number, you have the following binary representations

0 = 0000
1 = 0001
...
7 = 0111
-8 = 1000
-7 = 1001
...
-1 = 1111

so -8 + -4 + -2 + -1 becomes(*) in binary

1000 + 1100 + 1110 + 1111 = 0001

or -8 + -4 + -2 + -1 = 1

This generalizes for N-bit 2s complement numbers.

I think this is why Sunspace is getting the same result, instead of being able to get an arbitrary result, like you'd expect to be able to get from infinity - infinity.

(*)I can't sum 8 + 4 + 2 + 1 because there is no +8. If you interpret 1000 as +8 instead of -8, you could.

The series does not converge with twos complement number either. It just cycles through 1,3,7 -1 etc.

[Hypnagogic Jerk]

Originally Posted by Frylock

then I'd start to understand. Whats a metric? Whats a 2-adic valuation?

A metric is a function that gives you the distance between two points (in a metric space). Now, given that every rational x can be written as x = 2ⁿ u/v, with u and v indivisible by 2, with n being a unique choice, we can then define the 2-adic valuation in this way: |x|₂ = (1/2)ⁿ. If x = 0, then |x|₂ = 0. In the same way that the absolute value defines a metric on the rationals (d(x,y) = |x-y|), the 2-adic valuation does the same.

It's been some time since I last worked with the p-adic numbers, but I've posted in the other thread to invite other mathematicians whose knowledge of the subject is better than mine to come explain why this series does converge (and to -1) in the 2-adic numbers.

[Hypnagogic Jerk]

Missed the edit window.

Of course, the convergence of sequences and series is defined in a metric space. A sequence x_n converges to x if, for every e > 0, then there exists a point N such that if n > N, then |x_n - x| < e. From this, we can see how different metrics lead to different definitions of convergence, and we can probably explain how this series converges in the 2-adic numbers.

[Hypnagogic Jerk]

Let x_n = 1 + 2 + 4 + ... + 2ⁿ = 2ⁿ⁺¹ - 1. Then x_n - (-1) = 2ⁿ⁺¹, and therefore |x_n - (-1)|₂ = |2ⁿ⁺¹|₂ = (1/2)ⁿ⁺¹, which converges to 0 as n goes to infinity. This isn't a very formal proof (I haven't even proved that the 2-adic valuation really defines a metric on the rationals), but it can help you see how this series converges to -1 in the 2-adic numbers.

[ZenBeam]

The series does not converge with twos complement number either.

With N-bit numbers, there are always N terms to sum, so it converges. For all finite N, it converges to
-2^(N-1) + ... + -8 + -4 + -2 + -1 = 1.

[Thudlow Boink]

Originally Posted by Frylock

So mathematicians say that a "sum" like this is undefined?

It seems so weird that it come out so nicely and neatly to a simple answer of -1. I'm used to seeing "undefined" appear wherever an answer to a problem ends u being something that intuitvely looks to me like infinity. In my head I think I have almost unconsciously conflated the two.

The standard Calculus II definition for the sum of an infinite series is that it's limit of the sequence of partial sums, if such limit exists. So the sum of 1 + 2 + 4 + 8 + ... would be the limit, as n approaches infinity, of 1 + 2 + 4 + ... + 2ⁿ. Since this limit doesn't exist, the series diverges: it doesn't have a sum.

In the earlier days of infinite series, mathematicians played around with them without being all that careful about whether or not they converged, leading to some weird, contradictory or controversial results.

So am I right to suspect that if you changed the order of the numbers in the list, or changed the way you group them in your derivation, you can get nice neat little answers other than -1?

Well, there's a theorem that says that if you have a conditionally convergent series (i.e. a convergent series in which some of the terms are positive and some negative, which would diverge if you made all the terms positive), you can, by a suitable rearrangement of the terms, get it to add up to any sum you want.

[ultrafilter]

I'm playing fast and loose with p-adic integers here, but this should express the basic idea:

Fix a prime p, and consider sequences of integers a = (a₀, a₁, a₂, ...). We introduce an equivalence relation such that a and b are equivalent iff a_i = b_i mod p except at finitely many points. The p-adic integers are the equivalence classes of this relation.

In the 2-adic integers, (1, 1, 1, 1, 1, ...) = (0, 1, 1, 1, 1, ...), (2, 2, 2, 2, 2, ...) = (0, 0, 2, 2, 2, ...), (4, 4, 4, 4, 4, ...) = (0, 0, 0, 4, 4, ...), (8, 8, 8, 8, ...) = (0, 0, 0, 8, ...), and so on. If you add together the right-hand side of every power of two in this form, you get (0, 1, 3, 7, 15, ...), which is the same as (0, -1, -1, -1, -1, ...), and that's the same as (-1, -1, -1, -1, -1, ...). Again, this is just a sketch, but the details work out well.

In the case of complex numbers, the power series 1 + r + r² + r³ + ... converges to 1/(1 - r) whenever |r| < 1. This is an analytic function on the unit disk, meaning that it's defined there and its derivatives behave nicely, so there's a unique analytic function defined on the complex plane that agrees with it on the unit disk. That function happens to be 1/(1 - r), which is defined everywhere except r = 1. That allows us to say in some sense that the sum of any geometric series is 1/(1 - r) as long as the common ratio r is not 1.

[ErmesMarana]

It might seem as though we can arbitrarily change the limits of sequences by changing the metric, but this is not the case. If we want to change the limit of even a single sequence, then the new metric will not be able to provide a limit for the exact same sequences the old one could.

If we had another metric that gave us limits for exactly the same sequences as 2-adic valuation, then the limit here would still be -1.

[The Them]

Did I start all this? Good thing I have the excuse that my math education was a long time ago.
The only point I was trying to make was the fallacy of treating infinity as an algebraic number. Use it as a solution in a polynomial, I dare you.
A lot of what is being said here may be different nomenclature. CalMeacham, what you said sounds almost like Fourier Transform, and I don't remember that either.

[Liberal]

I don't understand the jump from this

x = 1+2+4+8+16+...

to this

x = 1+2(1+2+4+8+...).

How is the "1+2" introduced on the right without being introduced on the left?

[jovan]

Originally Posted by Liberal

How is the "1+2" introduced on the right without being introduced on the left?

Because 2(1+2+4+8+...) is just another way of writing 2+4+8+16+...

[Liberal]

D'oh! Must learn to read digits.

[Derleth]

This demonstrates the Universe is being run on two's-complement hardware, as opposed to one's-complement or signed-magnitude. Further demonstration is the fact there is no such algebraic entity as negative zero.

[RickJay]

I don't understand things like "P-adic," which sounds to me like a remedy for urinary tract infections. However, I found the intrinsic problem easy to understand if I just replaced the infinite-sums set with "infinity," which is what it is. Unfortunately, I do not know how to make the infinity symbol appear with my keyboard, so instead I am going to use a tilde - ~ - so just pretend that's the infinity symbol:

X = ~
X= 1 + ~

Since 1 plus infinity is more infinity,

X = ~

No matter how you slice this, if you acknowledge the identity of infinity, the equation always simplifies to:

X = ~ (infinity.)

[Frylock]

Originally Posted by Hypnagogic Jerk

A metric is a function that gives you the distance between two points (in a metric space). Now, given that every rational x can be written as x = 2ⁿ u/v, with u and v indivisible by 2, with n being a unique choice, we can then define the 2-adic valuation in this way: |x|₂ = (1/2)ⁿ. If x = 0, then |x|₂ = 0. In the same way that the absolute value defines a metric on the rationals (d(x,y) = |x-y|), the 2-adic valuation does the same.

Thanks, this is really interesting. I don't quite understand the role of u and v i n what you wrote above, though. You say they must be indivisible by two. This seems to mean they can be anything as long as they are odd. Does each choice of values for u and v give you a different 2-adic valuation, or do they all somehow collapse into giving the same 2-adic valuation?

So in other words: from x = 2ⁿ u/v I get n = log₂(xv/u), so the metric would be (1/2)^log₂(xv/u). My question is, does it make a difference what you pick for u and v? Do different choices mean different metrics?

Also, why is there not both an x and a y in the formula for the metric? How can it be a measure of distance if it only takes a single point as "input" so to speak?

-FrL-

[Giles]

Originally Posted by Frylock

Also, why is there not both an x and a y in the formula for the metric? How can it be a measure of distance if it only takes a single point as "input" so to speak?

Thinking just in terms of Euclidean geometry (which was what gave rise to the more general idea of metric spaces), a line is just as much a metric space as is a plane, 3-dimensional space, or a higher dimensional space. On a line, you just need one variable x to define a point.

[Frylock]

Originally Posted by Giles

Thinking just in terms of Euclidean geometry (which was what gave rise to the more general idea of metric spaces), a line is just as much a metric space as is a plane, 3-dimensional space, or a higher dimensional space. On a line, you just need one variable x to define a point.

Yes, on a line you need only one variable to define a point. But I thought a metric was supposed to give a way of measuring the distance between two points.

(I didn't take us to be talking about anything other than a line--though it did occur to me that the distance formula must be a metric for planes. Notice that no matter how many dimensions are in your space, the distance between two points is the distance between two points. )

-FrL-

[Hypnagogic Jerk]

Originally Posted by Frylock

Thanks, this is really interesting. I don't quite understand the role of u and v i n what you wrote above, though. You say they must be indivisible by two. This seems to mean they can be anything as long as they are odd. Does each choice of values for u and v give you a different 2-adic valuation, or do they all somehow collapse into giving the same 2-adic valuation?

Each integer has a unique prime factorisation. So if you have a rational x, you can write x = p/q, where p = 2^n₁ * 3^n₂ * 5^n₃ * ... and q = 2^m₁ * 3^m₂ * 5^m₃ * ... Therefore, x = 2^{n₁ - m₁} * u / v, where u = 3^n₂ * 5^n₃ * ... and v = 3^m₂ * 5^m₃ * ... u and v are basically the "junk" left in the prime factorisation of x (i.e. everything that is not a power of 2). You could define the p-adic valuation for any prime p in the same way.

Also, why is there not both an x and a y in the formula for the metric? How can it be a measure of distance if it only takes a single point as "input" so to speak?

In the same way that we can define a metric d on the rationals using the absolute value (d(x,y) = |x-y|), we can also define another metric d_p on the rationals using the p-adic valuation (d_p = |x-y|_p).

Now, there are a number of properties that a function must satisfy in order to be a metric. (The properties are shown near the beginning of the page.) Most of them are easy to show for the p-adic metric d_p, but we will show that this metric satisfies the ultrametric inequality (a stronger version of the triangle inequality). Let x, y, z be three rational numbers such that x = p^l u₁/v₁, y = p^m u₂/v₂, z = pⁿ u₃/v₃.
d_p(x, z) = |x-z|_p = |p^min(l,n)|_p |p^{l - min(l,n)} u₁/v₁ - p^{n - min(l,n)} u₃/v₃|_p = (1/p)^min(l,n), since we can show that p^{l - min(l,n)} u₁/v₁ - p^{n - min(l,n)} u₃/v₃ is not divisible by p. In the same way, d_p(x, y) = (1/p)^min(l,m) and d_p(y, z) = (1/p)^min(m,n). Then, we can see that (1/p)^min(l,n) <= max((1/p)^min(l,m), (1/p)^min(m,n)), and therefore the p-adic metric satisfies the ultrametric inequality. (I've left out many of the steps.)

Here we've only worked with the p-adic metric on the rationals. Defining the p-adic numbers is more complicated. I've seen them defined as equivalence classes of Cauchy sequences of rationals in the p-adic metric. I will compare this construction with the construction of the reals. Consider the following sequence: (3, 3.1, 3.14, 3.141, 3.1415, 3.14159, ...). This sequence appears to converge to pi (using the usual metric on the rationals, as defined by the absolute value), but if we're working in the rationals, it doesn't, since pi isn't a rational. Still, it is what we call a Cauchy sequence: the points in the sequence get arbitrarily close to each other. So what we can do is consider the space of equivalence classes of these Cauchy sequences of rationals. We will call this space the real numbers, and in the reals we call "pi" the equivalence class of Cauchy sequences of rationals that contains this sequence and every other sequence that eventually gets arbitrarily close to it. We can then show that, with a suitable definition of the addition and multiplication on the reals, it remains an algebraic field, and it is also complete: every Cauchy sequence of reals converges to a real. This construction should be done (and in more detail) in any good analysis book. And now, the construction of the p-adic numbers is similar, except that we're using the p-adic metric on the rationals instead of the usual metric.

I see that ultrafilter has also offered a definition of the p-adic integers, which I will have to read again.

[C K Dexter Haven]

Originally Posted by Sunspace

But you can also do this:

x = 1+2+4+8+16+...
x = 1+2+4(1+2+4+8+...)
x = 1+2+4x
x-4x = 3
-3x = 3
x = -1

Oh, wait. It comes out the same. So... um... I dunno. I thought it was going to come out with a different value of x, and then it would be like dividing by zero, where if you allow it, you can prove that 1 = 2.

Since the sum of 1 + 2 + 4 + ... + 2ⁿ = 2ⁿ⁺¹-1, that trick will always produce -1, methinks.

[dtilque]

Originally Posted by Derleth

This demonstrates the Universe is being run on two's-complement hardware, as opposed to one's-complement or signed-magnitude. Further demonstration is the fact there is no such algebraic entity as negative zero.

OK, but how many bits are in the Universal Computer's registers? And does it ever crash (BSOD?) so that God has to reboot the Universe?

[Malacandra]

Originally Posted by dtilque

OK, but how many bits are in the Universal Computer's registers? And does it ever crash (BSOD?) so that God has to reboot the Universe?

Yeah, he rebooted it last Thursday. Ran a full restore, though, so it was nice and seamless.

[Derleth]

Originally Posted by dtilque

OK, but how many bits are in the Universal Computer's registers?

It's a Lisp Machine, so it automatically rolls over to bignums on overflow.

And does it ever crash (BSOD?) so that God has to reboot the Universe?

No, Lisp Machines invoke a debugger. god can inspect stack frames, local variables, and the heap from the console and make changes in real-time.