Rearrangements of Series

Blake Stacey directed me towards a terrific tool for embedding TeX code into a web page. So how about we do ourselves a math post!

Remember the harmonic series? No doubt you encountered it in some calculus class or other. It's the one that goes like this:

$$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\dots$$

The series is divergent. If you keep adding more and more of the terms your running tally will just get bigger and bigger forever.

There are many ways to show that it is divergent. If you remember your calculus then you know there is a little gadget called the integral test that settles things very quickly. A more elementary argument goes like this. First we group our terms thusly:

$$1+\frac{1}{2}+\left( \frac{1}{3}+\frac{1}{4} \right) + \left( \frac{1}{5}+\dots+\frac{1}{8} \right) +\left( \frac{1}{9}+\dots+ \frac{1}{16} \right) \dots$$

We group things so that the final term in each grouping has a power of two on the bottom. If you keep in mind that fractions get smaller as their denominators get bigger, then we can say that the sum above must be larger than this:

$$1+\frac{1}{2}+\left( \frac{1}{4}+\frac{1}{4} \right)+ \left( \frac{1}{8}+\dots+\frac{1}{8} \right)+ \left( \frac{1}{16}+\dots+\frac{1}{16} \right) \dots$$

But now it is easy to see that each of the groupings adds up to one half. That means we are effectively adding one half to itself infinitely many times, which clearly gets bigger and bigger forever.

You might then wonder about how many terms we have to throw out before we get something that converges. For example, suppose we only kept the fractions with prime number denominators:

$$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\frac{1}{13} \dots$$

Since the prime numbers are very sparse you might think that the series would now converge. But you would be wrong. This still diverges, though the proof will have to wait for a different post.

What if we only kept the perfect squares. Now it converges! In fact, we have:

$$1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}+\frac{1}{25}+\dots=\frac{\pi^2}{6}$$

That the series converges at all is easily shown with standard techniques of calculus. That it adds up to pi squared over six is harder to show, so we will save that for a different post too.

Now for the interesting part. Suppose we took the harmonic series, but changed every other plus sign to a minus sign. The result would be the alternating harmonic series, and it converges! In fact, we get this:

$$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\frac{1}{6}+\dots= \ln 2$$

This equation can be proved using the Taylor series for the natural logarithm. Since the harmonic series diverges, but the alternating harmonic series converges, we say the harmonic series is “conditionally convergent.” This distinguishes it from an absolutely convergent series, which still converges even if you turn all the negative terms into positive terms.

What happens if you start rearranging the terms in the series? Intuitively that really should not change anything. Addition is commutative, right, meaning that it just does not matter the order in which you add things up. That's often true for infinite series. For example, if you take our series with the perfect squares on the bottoms and jumble up the terms however you like, the result will still be pi squared over six. So far so good.

One day, during a college class in real analysis (which is basically a calculus class where you stop to prove all the details you used to take for granted) my professor casually tossed off the fact that with a conditionally convergent series it is always possible to rearrange the terms to make them add up to anything you like. He was quickly on to other things, and I figured I must have heard him wrong. It just sounded too absurd.

But it's really true! I can rearrange the terms in the alternating harmonic series so that they add up to any real number at all. Rational, irrational, integer, doesn't matter. I can make the series diverge if I wanted to. As an example, I will show how to make the series add up to zero.

The first step is to separate the positive terms from the negative terms. The positive terms are

$$1, \phantom{x} \frac{1}{3}, \phantom{x} \frac{1}{5}, \phantom{x} \frac{1}{7}, \phantom{x} \frac{1}{9}, \dots$$

while the negative terms are

$$\frac{1}{2}, \phantom{x} \frac{1}{4}, \phantom{x} \frac{1}{6}, \phantom{x} \frac{1}{8}, \phantom{x} \frac{1}{10} \dots$$

If we add up the positive terms separately and the negative terms separately, we would find that both are divergent. That follows from the fact that the original series was only conditionally convergent. If our two separated series both converged, then they would still both converge if we made the negative terms positive. But then the original series would be absolutely convergent.

A similar argument will show that you cannot have one of the series be convergent while the other is divergent. Thus, the only possibility is that both are divergent on their own.

Now for the rearrangement:

$$1-\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{8}\right)+\left(\frac{1}{3}\right)-\left(\frac{1}{10}+\frac{1}{12}\right)+\left(\frac{1}{5} +\dots \right)$$

It may not look very promising, but watch what happens when you start adding up terms. We began with 1. Then we added four negative terms in a row. After adding the fourth negative number the running total becomes negative for the first time. Then we start adding positive terms until the running total is positive again. It turns out that only requires one positive fraction. Then we add two more negative fractions to make the running total negative once more. Then we add enough positive fractions to make the running total positive once more.

Since the separated series of positive and negative terms both diverge, we know that we will always have enough of each of them to make the running total positive or negative as needed. And since the individual fractions are getting smaller and smaller, we know that the amount by which we overshoot, or undershoot, zero will get smaller and smaller as well. In the limit, the running total (or “sequence of partial sums” as we say in the biz) will converge to zero.

No doubt you see how to adapt that to make the series converge to whatever you like. If you want it to add up to pi, for example, just add up positive terms until the sum is bigger than pi. Then take negative terms until the sum goes down below pi. Then go back to the positive terms, and so on.

Pretty neat, and very counterintuitive. We tend to use the familiar terminology of addition when we are dealing with infinite series. That makes it easy to forget that finite sums and infinite sums are very different beasts.

Tags

More like this

Euler's Solution to the Basel Problem
I'm in the mood for some math today, so here's an amusing little proof I recently showed to my History of Mathematics class. We shall derive the formula $\frac{\pi^2}{6}=1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}+\frac{1}{25}+\dots$ Note that the denominators of the fractions on the right are…
Monday Math: The Euler Product for the Zeta Function
In this week's edition of Monday Math we look at what I regard as one of the prettiest equations in number theory. Here it is: $\sum_{n=1}^\infty \frac{1}{n^s} = \prod_p \left( \frac{1}{1-\frac{1}{p^s}}\right)$   Doesn't it just make your heart go pitter-pat? You are probably familiar with…
Monday Math: The Sum of the Reciprocals of the Primes
Time for the big finale! We now have all the pieces in place to establish the divergence of the sum of the reciprocals of the primes. Recall that we have the Euler product expansion of the harmonic series: $\sum_{n=1}^\infty \frac{1}{n}= \prod_p \left( \frac{1}{1-\frac{1}{p}} \right)$   We…
Sunday Function
Consider this not-so-difficult sum: It consists of just a string of fractions up to whichever N you happen to choose. Add them up, and you certainly and unambiguously have a number. If you chose to stop at N = 10, you'd find that f(10) = 1627/2520, which is about 0.645635. If you chose to stop…

You wrote:

then we can say that the sum above must be smaller than this:

(I won't try to copy sums)

Didn't you mean _larger_, since (1/3 +1/4) > (1/4 + 1/4), for example?

FWIW this didn't work in google reader, it just displayed the raw latex syntax.

Hmm, in Internet explorer, on my machine, only the first series in your post gets properly formated. The others later on in the post are not. For example, the 2nd series comes in as $$1+\frac{1}{2}+\left( \frac{1}{3}+\frac{1}{4} \right) + \left( \frac{1}{5}+\dots+\frac{1}{8} \right) +\left( \frac{1}{9}+\dots+ \frac{1}{16} \right) \dots$$

But if I fire up firefox (which I don't prefer), it works.

hmm some more (last one and I shut up). If I look at *my* post just above here in EI, the equation I pasted in (the second one from your post) is unformated, but if I use Firefox to view my post, the equation is properly formated.

DaleP -

Thanks for catching the error. I've corrected the post.

Stuart and Divalent -

It does seem to be working on Safari, and it worked for me with Firefox, too. I'm not sure what the problem is with the other browsers, but it certainly dampens my enthusiasm some.

Looks fine in Chrome.

And interesting post too Jason - MOAR MATH PLZ!!!!111one :)

You do have to permit scripts from amazonaws.com.

Same as Divalent. I'm using IE (7) and I only see the first formula as it should be.

Maybe it's time I switched browsers. (I have other problems with IE.) Sorry to go off topic, but will other browsers keep my IE favourites list?

By Richard Wein (not verified) on 18 Jul 2010 #permalink

P.S. No need to answer. I should have googled before asking. It seems other browsers will import favourites and other settings. I'll try switching to Firefox later today.

By Richard Wein (not verified) on 18 Jul 2010 #permalink

Jason,

When I teach our mathematical physics course I love to show, as you did here, that the alternating harmonic series can be summed to get any number.

What I like most is the student reaction--some think it is cool, some are sure you cheated--but almost everyone gets into it.

It is one of those--and all teachers have a catalog of them--instructive yet simple teachable moments that are guaranteed to wake-up even those students in the back row.

By the way, does your book (sorry I haven't picked it up yet--but I will) go into the Tuesday Child problem? I ask because some have likened it to the MH problem--but I don't see it. (I wrote a little about it here, and was hoping you would post your own explanation.)

The <script> block which calls the mathcache code isn't included in the RSS feed; changing that would require some devious hacking inside the SB configuration, and I'm not sure it'd work in all feedreaders. Temporary fix: I'd suggest keeping equations below the fold.

For something which came out of CERN, the Web is remarkably bad at communicating mathematics . . . you think we would have solved this problem by now! :-/

But if I fire up firefox (which I don't prefer), it works.

Clearly a PEBKAC error.

All that the script does is take the TeX code, escape some characters, massage the string a bit, and pass the whole thing as a CGI argument to:

http://mathcache.appspot.com/?tex=

Which takes it and returns a PNG image of the equation.

If you wanted to, you might be able to implement a similar search-and-replace macro using your favourite editor. And I think the result would be visible in an RSS feed.

Just a thought.

By Owlmirror (not verified) on 19 Jul 2010 #permalink

I set up mathcache -- sorry folks are having trouble.

I'll try to get the IE problem solved today. It crashes on the code "child = child.nextSibling" on this page, but works on the simple example at mathcache.appspot.com. I'll break down what's going on.

Owlmirror is right: the script generates image tags pointing to PNGs, which you can also do by hand. There's also a bookmarklet on the mathcache page which will replace TeX with static PNG images in some rich-text editors. I don't know whether it works in the blog software scienceblogs uses; it Works For Me(tm) in GMail on Chrome, for instance.

Erp: you're using something like NoScript, right? In general, I don't have to allow cross-site scripts (like Google-hosted jQuery) explicitly.

By the way, does your book (sorry I haven't picked it up yet--but I will) go into the Tuesday Child problem

Heh, heddle, I googled "Tuesday Child problem" since I had not heard of it, and clicked on the first promising link I saw... which turned out to be your blog. Didn't even realize it until I had finished reading the post. heh...

My wife reports that the fact that P(7)=1/3 (in your notation) is being used by people on pregnancy/childbirth forums to argue that you are more likely to have a child of the opposite gender for your second! Facepalm...

James Sweet,

My wife reports that the fact that P(7)=1/3 (in your notation) is being used by people on pregnancy/childbirth forums to argue that you are more likely to have a child of the opposite gender for your second! Facepalm...

Nothing surprises me more than the lack of intuition regarding probability. I'm certainly not immune--I am guilty of "it's due" gambling fallacy: He's gonna get a hit, he's due! Also, I play a game where I pick the top ten drivers in the next NASCAR race. I am always rearranging my selections to make them look "more random."

Recently I read of a woman who won the lottery four times in Texas. The report said a) she didn't cheat and b) the odds of winning four times were one in 10^25. If so, I say she cheated. That's harder than picking the right molecule out of a mole of molecules.

An interesting incident to investigate is the weird case of an exact bid of $23,743 on the Price is Right. Apparently there was, in the studio, a 45 minute delay between when the bids were made and when they announced the prices, because the producers were concerned about cheating. I know--all off topic--but the weirdness of the probability-human intuition interface is fascinating. I've been using http://hausheer.osola.com/latex2png Which converts LaTex directly to a .png file. The site you listed does the conversion each time the page is rendered, and it would fail if the service were ever changed or disappeared. By Greg Esres (not verified) on 20 Jul 2010 #permalink The exact bid on The Price Is Right does not seem too surprising. The other lady came within$500 of the price. If we assume a reasonably adept TPIR player can consistently get within $1500 or so of the price, then we'd only need to have 3000 bids made by reasonably adept players in order to hit one exact match. I'm pretty sure there have been many more episodes of TPIR than this! "It was due." :D You're damn right that nobody is immune from intuitive failures when it comes to probability. When my wife told me she had read that, if you had two children and one was a son, there was a 2/3 chance the other was a daughter, it took me a full day of pondering before I figured out why that was and could clearly explain why, despite this, the odds of our 2nd kid being a girl are still (about*) 50/50. I must admit, I don't grasp the Tuesday Child problem at all yet... not even on paper. I can proudly say, though, that I have managed to get a decent intuitive understand of the Monty Hall problem. The way I envision it is that instead of me picking, say, Door #2 and then changing my mind, what I am doing is asking Monty Hall, "If it was behind door #1 or door #3, which would it be?" And from that I get information about those doors, whereas I still have no information about door #2. It's a rough and messy explanation, but it helps me intuit the math. (And the math is irrefutable, of course) * It's my understanding that the odds are not quite exactly there. First of all, it seems like there is a very slight bias towards females anyway (something like 50.1%), and it's also my impression, though I might be mistaken, that if you've had one child, your odds of continuing to have the same gender rise very slightly -- basically, the dad could have some sort of problem with either his X or his Y chromosome that makes it difficult to produce a viable offspring of the corresponding gender. I think I heard that someplace reputable, but I might be just making that up... Oh, human brain, how fallible thou art! James Sweet, I think the Price Is Right is a little more complicated. Having watched a gazillion episodes (it has always been my son's favorite show) I am guessing the average winning bit on the showcase is more like$3K to $4K off. But more importantly, you have to factor in the probability that someone gives a bid like:$23,743. The bids are not on any sort of continuous distribution--they are found preferentially around even hundreds, like $23,700. If my intuition is right, then the odds of an exact bid of$23,743 are maybe 50-100 times less than your estimate. Still, I agree they are not small enough that your "nixplanatory filter" screams: cheat!

The best, absolute best case of "it's due" is when the Pennsylvania lottery was rigged. Paint was injected into all the pingpong balls except 4's and 6's. The number 666 came up (perfect!). The head of the PA lottery commission, trying to calms fears that the lottery was rigged (he wasn't in on it, but he was trying to stop the rumors, which turned out to be true) had this explanation: "Since the lottery began every three digit combination 111, 222, etc has hit except 666. People should not be surprised about the 666 drawing--it was due!"

The IE bug is fixed.

(For any JavaScript-obsessed readers, the problem was that if you remove a node from a document, asking for the orphaned node's parent or sibling is an error in IE. Other browsers just say the orphan has no parent/sibling, without throwing an error.)

@Greg Esres: I know some sites' math rendering depends on mathcache staying up and I definitely won't casually change the service or let it disappear.

Each bit of math is rendered once by a server that's been up for a few years, then served from a cache in Google App Engine. If the rendering server it's using goes down, old math will normally still display, and I can point the cache at another server or set up my own.

Anyway, mathcache isn't for everybody, and I definitely want to fix up some of the deficiencies when I get time. Just figured it would be useful to some folks who want an easy rendering solution so I put it out there.

I must admit, I don't grasp the Tuesday Child problem at all yet... not even on paper.

1) Columns represent child 1, rows represent child 2 (you can make this explicit as a header)

2) For each child set up 14 rows/columns

3) Seven of these rows/columns are for girl and seven for boy

4) The seven slots for each gender correspond to a day of the week.

5) It should be obvious by now how to read the spreadsheet, yes?

6) Highlight all the entries that meet the known data (in this case, the entire column corresponding to the first child being a boy born on Tuesday, and the entire row corresponding to the second child being a boy born on Tuesday). This is your denominator.

7) Put an X in all the entries where the criterion is met (here, where the other child is a boy). This is your numerator.

Now, you should be able to see why it isn't exactly 1/2: the column and the row overlap where both children are boys born on Tuesday. Intuitively, we treat the possibility of the first child being the known entity separate from the possibility that the second child is the known entity, ending up with (7+7)/(14+14)=14/28=1/2 as our calculation. But that calculation double counts the both boys born on Tuesday possibility.

Let's see if I can get a fixed width format to illustrate what I just said graphically.

CHILD 1
boy | girl
UMTWRFSUMTWRFS
U X
M X
bTXXXXXXXOOOOOOO
oW X
CyR X
H F X
I_S X
L U O
DgM O
iT O
2rW O
lR O
F O
S O

If that displayed properly, there should be 13 Xs, 14 Os, and 169 blank spaces. 13/(13+14)=13/27, which is our answer.

've learned it last year..
and now , i'm not sure I can solve it or not..

Then you should learn it again, trust me, it's worth the effort

I am trying. It seems to be working, but it's not great.
For fun, I wrote another proof of the divergence of harmonic series on my blog. It would be great if people could tell me whether the LaTeX code renders or not.

@Kevin Vicklund: Thanks for the attempt. I didn't actually go through the construction of the spreadsheet, but I think I am visualizing it now... The "double-counting" thing was actually what triggered it for more, except the way I visualize it is that everything except both-boys-born-on-Tuesday should be double-counted, i.e. should be counted more than my intuition tells me. Because there are two combinations.

To try and generalize it... and this is not the most general way of stating it, but it is a start... And it lays bare the paradoxical aspect of it, which perhaps leaves me even more confused! Anyway, without further ado:

Let's say you have experiment X, with two broad categories of outcomes A and B -- but there are many sub-categories of outcomes as well, given by A1, A2, etc. You know that experiment X has been performed twice, and furthermore, you know that the outcome of one of them (but you don't know which) was An.

Knowing this fact reduces the probability that the outcome of the other trial fell into category A. Furthermore, the larger the fraction P(An)/P(A), the less likely it is that the outcome of the other trial fell into category A, finally reaching a minimum probabiltiy at the case where P(An)=P(A), i.e. when the sub-category is the category.

I'm not going to try to calculate the odds, but from this I would deduce the following:

If there are two people in the room and I know one them is born in December, the odds that the other person is born in December are less than 1/12.

If there are two people in the room and I know that one of them was born on December 25th, the odds that the other person was born in December are less than 1/12, but greater than the probability in the previous paragraph.

Right?

The subcategory doesn't even have to be a strict subset of the category, does it?

I present to you: The Peach-Loving Child Problem.

Half of all boys love peaches. Three-quarters of all girls love peaches.

One of my children loves peaches. What is the probability that the other one is a boy?

I haven't worked out the odds, but I am pretty sure it's not 50%!

James @33:

Yes. However, perhaps not the best example, because the possibilities are not equally distributed. To accurately account for this, you have to weight the possibilites, which leads to the correct odds* to your scenario @34:

p=36/55=65.7%, or just a tad under 2/3.

Interesting observation: if half of all girls love peaches, then the answer to:

One of my children loves peaches. What is the probability that the other one is a boy?

Works out to 7/12. But the answer to:

One of my children loves peaches. What is the probability that the other one is a girl?

Also works out to 7/12!

Wacky, huh?

*Of course, assuming I evaluated the situation properly

As a side note, my answer requires that "One of my children loves peaches" means that at least one loves peaches, not exactly one. It was discussed earlier in the comments, but I thought I'd better make it explicit for those joining late.

Interesting observation: if half of all girls love peaches, then the answer to:

One of my children loves peaches. What is the probability that the other one is a boy?
Works out to 7/12. But the answer to:

One of my children loves peaches. What is the probability that the other one is a girl?
Also works out to 7/12!

Wacky, huh?

Okay, that just topped Monty Hall Paradox and Tuesday's Child put together.

I went through it step by step to show that you were wrong, and found that you were, after all, right. Since I had already typed it all up (in hopes of proving you wrong), here it is for posterity:

Half of all children love peaches. One of my children loves peaches. What are the odds the other is a boy?

Notation: B notates boy, G notates girl, P notates "loves peaches", p notates "does not love peaches".

All possible outcomes, without the "one of my children loves peaches" qualifier, with accompanying probability:

BPBP = 1/16
BPBp = 1/16
BPGP = 1/16
BPGp = 1/16
BpBP = 1/16
BpBp = 1/16
BpGP = 1/16
BpGp = 1/16
GPBP = 1/16
GPBp = 1/16
GPGP = 1/16
GPGp = 1/16
GpBP = 1/16
GpBp = 1/16
GpGP = 1/16
GpGp = 1/16

One of my children loves peaches, so that eliminates all of the ones that are *p*p:

BPBP = 1/16
BPBp = 1/16
BPGP = 1/16
BPGp = 1/16
BpBP = 1/16
BpGP = 1/16
GPBP = 1/16
GPBp = 1/16
GPGP = 1/16
GPGp = 1/16
GpBP = 1/16
GpGP = 1/16
Total = 12/16

Categories that satisfy "the other one is a boy":

BPBP = 1/16
BPBp = 1/16
BPGP = 1/16
BpBP = 1/16
BpGP = 1/16
GPBP = 1/16
GPBp = 1/16
Total = 7/16

No. no no no no no no!!!!

Ah hah! I figured out the linguistic trick that makes this work.

If I had said, "I have three children, one of them loves peaches, what are the odds that another one is a boy?", then it is not so disturbing that summing it with the probability for s/boy/girl might come up over 100%.

If I had said, "I have tow children, one of them loves peaches, what are the odds that another one is a boy?", again, now this is less disturbing.

It is the phrase "the other one" that tricks us into thinking the one who likes peaches is fixed.

Believe-you-me, James, I spent about an hour trying to prove myself wrong. I found it on a whim when I was looking at your example. I still have some struggle wrapping my brain around it - I understand it on one level, but there's a monkey in there screaming in terror.

After discussing with a co-worker (who of course was equally incredulous) I am now quite comfortable with it. As I said in #38, the linguistic trick is that saying "the other one" implies a fixed choice, when of course there is no such thing.

The ones that are double-counted are BPGP and GPBP, of course. For those configurations, the answer to both of the following two statements are true:

"One of my children loves peaches, and the other is a boy."
"One of my children loves peaches, and the other is a girl."

Another way to make it more comfortable is to consider if it were a bet. Does this bizarre 7/12 observation have any bearing on the following proposition?

"One of my children loves peaches. Place a bet on the gender: Boy or girl?"

No. Well, depending on the rules, you probably just never want to make that bet, because your odds of winning are always 5/12 (the person offering the bet can pick the subject of the first sentence after you place your bet -- a sort of virtual shell game).

In order to make a bet for which you can exploit this information, the wording gets pretty awkward -- and illustrates exactly what we are observing:

"Which bet do you want: It is true that one of my children loves peaches and the other is a boy, or it is not true that one of my children loves peaches and the other is a boy?" If you attempt to distribute any of the terms outside of the bet, then the bet falls apart.

Heh, I just thought of a different way to phrase the original question:

"One of my children loves peaches. What are the odds that either a) I have two boys, OR b) I have one boy and a girl who likes peaches?"

Now the fact that peaches influence the result doesn't seem quite so crazy...

Heh, okay, well here's a short one that graphically illustrates the "the other one" cheat:

I have two children. One of them is from planet Earth. What are the odds that the other one is a boy?

heh.

The ones that are double-counted are BPGP and GPBP, of course. For those configurations, the answer to both of the following two statements are true:

"One of my children loves peaches, and the other is a boy."
"One of my children loves peaches, and the other is a girl."

Yep! That's the secret. I showed this to my wife last night. She had pretty much the same reaction you did, as well as trying to kick me in the nuts (file under "Some people juggle geese"). She finally accepted it when I gave her the same explanation. I also put it terms of families:
16 families (each representing one of the 16 possible arrangements), families without a child who loves peaches, get kicked out (4 leave), families with the other child a boy told to stand up (7 stand up),families with the other child a girl told to stand up (5 sit, 5 stand up, 2 remain standing).

My wife's reaction when I unveiled the 7/12 thing was, "That's totally meaningless! You're just relating two things that have nothing to do with each other." At first I thought the second sentence was an objection to the result, but no it was not. After pondering it for a bit and trying to decide how to respond, I realized that my wife was in a sense correct: While the 7/12 answer is indubitably true, it doesn't really have much "meaning", in that the scenario it describes doesn't really have much applicability to... well, anything.

Sort of took the piss out of the whole thought experiment. Grumble grumble, oh well... :D