Straight Dope Message Board > Main 1 + 2 + 4 + 8 + 16 + 32... = -1 ?!
 Register FAQ Calendar Mark Forums Read

#1
03-06-2008, 10:54 AM
 Frylock Guest Join Date: Jun 2001
1 + 2 + 4 + 8 + 16 + 32... = -1 ?!

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-

Last edited by Frylock; 03-06-2008 at 10:54 AM.
#2
03-06-2008, 10:59 AM
 Giles Charter Member Join Date: Apr 2004 Location: Newcastle NSW Posts: 11,555
The series 1+2+4+8+16+... does not have a limit, so it's meaningless to do arithmetic with it.[/quote]
#3
03-06-2008, 11:01 AM
 Frylock Guest Join Date: Jun 2001
Quote:
 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-
#4
03-06-2008, 11:04 AM
 Frylock Guest Join Date: Jun 2001
Hmm... can anyone explain anything from the following: Theorems on methods for summing divergent series to a(n intelligent) layman?

-FrL-
#5
03-06-2008, 11:07 AM
 Frylock Guest Join Date: Jun 2001
Ah... I bet if someone could explain this comment from here:

Quote:
 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-

Last edited by Frylock; 03-06-2008 at 11:07 AM.
#6
03-06-2008, 11:09 AM
 Sunspace Charter Member Join Date: Jun 1999 Location: Back in the GT eeehhhh... Posts: 24,940
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.
#7
03-06-2008, 11:10 AM
 Napier Charter Member Join Date: Jan 2001 Location: Mid Atlantic, USA Posts: 7,175
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.
#8
03-06-2008, 11:17 AM
 Giles Charter Member Join Date: Apr 2004 Location: Newcastle NSW Posts: 11,555
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.
#9
03-06-2008, 11:26 AM
 Colophon Guest Join Date: Sep 2002
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.
#10
03-06-2008, 12:15 PM
 ZenBeam Charter Member Join Date: Oct 1999 Location: I'm right here! Posts: 6,885
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.
#11
03-06-2008, 12:28 PM
 Giles Charter Member Join Date: Apr 2004 Location: Newcastle NSW Posts: 11,555
Quote:
 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.
#12
03-06-2008, 12:31 PM
 CalMeacham Guest Join Date: May 2000
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.
#13
03-06-2008, 12:44 PM
 gazpacho Charter Member Join Date: Oct 1999 Posts: 4,895
Quote:
 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.
#14
03-06-2008, 12:51 PM
 Hypnagogic Jerk Guest Join Date: Apr 2005
Quote:
 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 = 2n 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|2 = (1/2)n. If x = 0, then |x|2 = 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.
#15
03-06-2008, 12:57 PM
 Hypnagogic Jerk Guest Join Date: Apr 2005
Missed the edit window.

Of course, the convergence of sequences and series is defined in a metric space. A sequence xn converges to x if, for every e > 0, then there exists a point N such that if n > N, then |xn - 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.

Last edited by Hypnagogic Jerk; 03-06-2008 at 12:58 PM.
#16
03-06-2008, 01:03 PM
 Hypnagogic Jerk Guest Join Date: Apr 2005
Let xn = 1 + 2 + 4 + ... + 2n = 2n+1 - 1. Then xn - (-1) = 2n+1, and therefore |xn - (-1)|2 = |2n+1|2 = (1/2)n+1, 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.

Last edited by Hypnagogic Jerk; 03-06-2008 at 01:05 PM.
#17
03-06-2008, 01:21 PM
 ZenBeam Charter Member Join Date: Oct 1999 Location: I'm right here! Posts: 6,885
Quote:
 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.
#18
03-06-2008, 01:32 PM
 Thudlow Boink Charter Member Join Date: May 2000 Location: Springfield, IL Posts: 15,575
Quote:
 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 + ... + 2n. 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.

Quote:
 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.
#19
03-06-2008, 02:31 PM
 ultrafilter Guest Join Date: May 2001
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 = (a0, a1, a2, ...). We introduce an equivalence relation such that a and b are equivalent iff ai = bi 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 + r2 + r3 + ... 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.
#20
03-06-2008, 02:49 PM
 ErmesMarana Guest Join Date: Mar 2008
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.
#21
03-06-2008, 03:36 PM
 The Them Guest Join Date: Jul 2007
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.
#22
03-07-2008, 05:26 AM
 Liberal Guest Join Date: Nov 1999
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?
#23
03-07-2008, 05:53 AM
 jovan Guest Join Date: Aug 2001
Quote:
 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+...
#24
03-07-2008, 07:16 AM
 Liberal Guest Join Date: Nov 1999
D'oh! Must learn to read digits.
#25
03-07-2008, 07:52 AM
 Derleth Guest Join Date: Apr 2000
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.
__________________
"Ridicule is the only weapon that can be used against unintelligible propositions. Ideas must be distinct before reason can act upon them."
If you don't stop to analyze the snot spray, you are missing that which is best in life. - Miller
I'm not sure why this is, but I actually find this idea grosser than cannibalism. - Excalibre, after reading one of my surefire million-seller business plans.
#26
03-07-2008, 07:53 AM
 RickJay Charter Jays Fan Moderator Join Date: Jun 2000 Location: Burlington, Ontario Posts: 29,757
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.)
#27
03-07-2008, 09:39 AM
 Frylock Guest Join Date: Jun 2001
Quote:
 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 = 2n 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|2 = (1/2)n. If x = 0, then |x|2 = 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 = 2n u/v I get n = log2(xv/u), so the metric would be (1/2)log2(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-
#28
03-07-2008, 09:55 AM
 Giles Charter Member Join Date: Apr 2004 Location: Newcastle NSW Posts: 11,555
Quote:
 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.
#29
03-07-2008, 10:25 AM
 Frylock Guest Join Date: Jun 2001
Quote:
 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-
#30
03-07-2008, 11:09 AM
 Hypnagogic Jerk Guest Join Date: Apr 2005
Quote:
 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 = 2n1 * 3n2 * 5n3 * ... and q = 2m1 * 3m2 * 5m3 * ... Therefore, x = 2n1 - m1 * u / v, where u = 3n2 * 5n3 * ... and v = 3m2 * 5m3 * ... 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.

Quote:
 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 dp on the rationals using the p-adic valuation (dp = |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 dp, 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 = pl u1/v1, y = pm u2/v2, z = pn u3/v3.
dp(x, z) = |x-z|p = |pmin(l,n)|p |pl - min(l,n) u1/v1 - pn - min(l,n) u3/v3|p = (1/p)min(l,n), since we can show that pl - min(l,n) u1/v1 - pn - min(l,n) u3/v3 is not divisible by p. In the same way, dp(x, y) = (1/p)min(l,m) and dp(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.
#31
03-07-2008, 11:37 AM
 C K Dexter Haven Right Hand of the Master Administrator Join Date: Feb 1999 Location: Chicago north suburb Posts: 14,679
Quote:
 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 + ... + 2n = 2n+1-1, that trick will always produce -1, methinks.
#32
03-08-2008, 01:57 AM
 dtilque Charter Member Join Date: Jan 2000 Location: My own private Nogero Posts: 3,244
Quote:
 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?
#33
03-08-2008, 02:54 AM
 Malacandra Guest Join Date: Jan 2003
Quote:
 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.

Last edited by Malacandra; 03-08-2008 at 02:56 AM.
#34
03-09-2008, 09:12 PM
 Derleth Guest Join Date: Apr 2000
Quote:
 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.
Quote:
 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.
__________________
"Ridicule is the only weapon that can be used against unintelligible propositions. Ideas must be distinct before reason can act upon them."
If you don't stop to analyze the snot spray, you are missing that which is best in life. - Miller
I'm not sure why this is, but I actually find this idea grosser than cannibalism. - Excalibre, after reading one of my surefire million-seller business plans.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     Straight Dope Chicago     General Questions     Great Debates     Elections     Cafe Society     The Game Room     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit Side Conversations     The Barn House

All times are GMT -5. The time now is 10:53 AM.