Rearrangement Patterns for the 
     Alternating Harmonic Series

Mathematica in Education
Vol.3 No.2
Spring 1994
(c) TELOS/Springer-Verlag

by
Ed Packel
Volwiler Professor and Chairperson
Mathematics and Computer Science Department
Lake Forest College
Lake Forest, IL 60045
packel@davinci.lfc.edu

and

Stan Wagon
Department of Mathematics and Computer Science
Macalester College
St. Paul, MN  55105
wagon@macalstr.edu

Introduction

As educators,we hope that the use of software such as Mathematica will allow students to explore, experiment, and perhaps discover ideas and results that are new, at least to them. While this idealized process may not happen with students as often as we might like, we describe here how Mathematica gave us such an experience when we were designing a calculus laboratory notebook. The results we ``discovered'', with major help from a relatively simple Mathematica routine, were new and appealing to us, and the excitement of discovery far outweighed the slight letdown when we learned that the results had been known for more than a century ([Cowen, Davidson, and Kaufman, 1980], [Pringsheim, 1883]).

The results in question allow us to find the sum of virtually any rearranged alternating harmonic series (henceforth AHS) whose rearrangement pattern can be clearly described. Working in the other direction, we can use the results to specify a regular rearrangement pattern that will cause the AHS to have a sum as close as we please to any preassigned real number. Our purpose in this article is to highlight Mathematica's role in revealing these results and in facilitating their explanation and proof to an interested calculus student. In doing so, we borrow freely from a Mathematica notebook in our recently published collection of calculus lab notebooks [Packel and Wagon, 1994].

Much has been written about the value of using Mathematica to help us visualize abstract mathematical constructions. It is worth pointing out that such visualizations are not limited to geometrical contexts, but can arise, as they do here, in an algebraic setting, where they can be just as valuable.

The Harmonic Series and Euler's Gamma

We need a quick way to generate the partial sums of the harmonic series, known as the harmonic numbers and denoted by Hn. While the straightforward

H[n_] := Sum[1./k, {k, 1, n}]

may be appropriate for student use, experienced Mathematica users will appreciate the extra speed that comes by applying Plus to integer reciprocals, and will want to let H[n_] be Apply[Plus, 1/Range[1., n]].

Readers may be wondering why this common sequence is not built into Mathematica. In fact it is, since Hn equals EulerGamma + PolyGamma[0, n+1], which is by far the fastest way to get these numbers. The reader wishing to efficiently examine lots of harmonic numbers should substitute the code that follows in the earlier definition of H[].

HFast[n_] := N[EulerGamma] + PolyGamma[0., n+1]

TECHNICAL COMMENT.   We use N and 0. to define HFast, for if we omitted these and called for results with N[HFast[10000]], we would be asking Mathematica to perform an unnecessary high-precision computation involving rational numbers.

H[10000] //Timing
Apply[Plus, (1. / Range[1., 10000])] //Timing
HFast[10000] //Timing
(* Computation times are for a Macintosh IIfx *)

The following plot compares the growth of the harmonic numbers with that of the natural logarithm function.

Show[ListPlot[Table[{n, H[n]}, {n, 1, 100, 2}]],
     Plot[Log[n], {n, 1, 100}]];

The discrete plot of the harmonic numbers appears, as n increases, to be growing in parallel with the natural log. The difference between the two curves does in fact approach a limit near 0.577. This important mathematical constant is usually denoted by γ and is known as Euler's constant. It is available in symbolic form in Mathematica as EulerGamma.

H[10000] - Log[10000.]
{EulerGamma, N[EulerGamma], N[EulerGamma, 30]}

Another view further motivates the upcoming definition of Euler's gamma.

ListPlot[Table[{n, H[n] - Log[n]}, {n, 1, 240, 3}],
     PlotRange->{0, 1}];

If the preceding graph could be trusted to eventually ``become'' a horizontal line, we could safely conclude the existence of limn→∞ Hn - ln n. We now offer a visual proof that this limit does indeed exist.

The terms of the harmonic series can be compared with the function y = 1/x. This leads to a study of the infinitely many white regions under the graph; their total area is the limit of ln n — (Hn — 1).

Sliding all the white regions above the gray rectangles leftward into the first rectangle shows that their total area is finite. Thus
1 — total white area (i. e., the black area in the first rectangle) equals the limit of Hn — ln n, showing that γ exists and geometrically representing its value (the black area). Moreover, the black region takes up more than half of the first rectangle, so 1/2 <  γ < 1.

For future reference (we will need it later) we formally summarize:

γ   =  limn→∞  Hn — ln n

Rearrangements of the AHS

After studying the alternating harmonic series (and the general idea of a conditionally convergent series), one is always eager to dazzle students with the surprising fact that rearrangements of such series can be constructed to sum to any real number. With that in mind, we defined a  Mathematica function that, for any desired target sum, produces a rearranged AHS converging to the target (code at end of paper). Our hope was that students, by looking at examples, would discover the standard rearrangement technique by which a given sum can be obtained. That technique ± which is how the HarmonicRearrangement function works ± adds odd reciprocals until the target is passed, subtracts even reciprocals until the target is passed in the opposite direction, and continues this infinite sequence of U-turns. Standard methods prove that this leads to an infinite series — a rearrangement of the AHS — that sums to the target. In all that follows, we use the phrase rearrangement of the AHS to mean a permutation of terms in which the subsequence of positive terms occurs in its original decreasing order and likewise for the subsequence of negative terms.

TECHNICAL COMMENT.   A tricky bit of programming was necessary so that output such as
1/2 - 1/3 is not automatically turned into 1/6. We did this by converting everything to strings, which works, but is a little tedious. Perhaps there is a better way to get the desired output.

?HarmonicRearrangement

As mentioned in the introduction, playing with this routine sent us onto our own path of discovery. Here was our first surprise.

HarmonicRearrangement[0.0]

As the final piece of output indicates, a very regular pattern of four negative terms to each positive term emerges, suggesting the surprising identity: 
 
          0  =  1 — 1/2 — 1/4 — 1/6 — 1/8 + 1/3 — 1/10 — 1/12 — 1/14 — 1/16 + 1/5 — ⋯ .
 
This identity, and infinitely many others, will follow from the results of the next section. Here is another example that gives a clue about where we are going.

HarmonicRearrangement[Pi, bailOut->5000, 
	showSeries->False, showPartialSums->False]

The results suggest that a ratio of somewhere between 133 and 134 (much closer to the latter) positive terms to each negative term will yield a rearranged AHS whose sum is close to π. The fact that only one negative term is needed for each clump of positive terms (and vice versa if the targeted sum is less than ln 2) follows inevitably from the special nature of the AHS and the standard rearrangement approach we are using. The output of partial sums is not included here, but we note that the partial sums at the last two sign changes are approximately 3.14165 and 3.1285.

A Formula for Rearranged AHS: Gamma Returns

The identity suggested earlier for 0 and some well-known identities involving the AHS provide clues to a general formula. The AHS itself (ratio of positive to negative terms is 1) converges to ln 2. The series
1 — 1/2 — 1/4 + 1/3 — 1/6 — 1/8 + ⋯ (ratio equals 1/2) has sum 1/2 ln 2 using the celebrated trick of pairing each positive term with the one that follows and arriving at one half of the AHS. Our identity for 0 had a ratio of 1/4. These three identities alone suggest the statement of the following theorem.

HARMONIC REARRANGEMENT THEOREM.  Given a rearranged alternating harmonic series, let 
r = limn→∞ pn/mn, where pn and mn are the number of positive and negative terms, respectively, among the first n terms (provided this limit exists). Then the series must converge and it converges to the sum 
ln 2 + 1/2 ln r. 

By solving S = ln 2 + 1/2 ln r for S, we can obtain the ratio value r that gives rise to any sum S.

r /. Solve[S == Log[2] + 1/2 Log[r], r] //First //Expand

COROLLARY.  To achieve the sum S for a rearranged AHS, let r = 1/4 e2S.

These results support our ``1 positive term, 4 negative term'' identity for 0 and also shed light on the results we got in seeking a rearranged AHS summing to π. Indeed,1/4 e2„ is 133.873², which corresponds to the ratio between 133 and 134 that showed up earlier.

If the desired ratio r should happen to be a rational number, say p/m, an easy way to achieve this is to alternate p positive terms with m negative terms. If r is irrational, giving a simple specification for the rearrangement method is not so clear. But if we are willing to settle for approximate results, we can simply replace r by an appropriate rational approximation and use it to build a rearrangement.

With the help of the definition of γ developed earlier, we can give what is close to a general proof of the harmonic rearrangement theorem.

PROOF (for the case where r = p/m is rational and the AHS is rearranged by alternating p positive terms and m negative terms ad infinitum).

Let On denote the sum of the first n odd terms of the harmonic series and En the sum of the first n even terms (ignoring the minus signs). We then have the following identities: 

            (1)   H2n  =   On + En,
            (2)   En    =   1/2 Hn,
            (3)   On    =   H2n — 1/2 Hn.

Consider a rearrangement of the AHS that alternates p positive terms with m negative terms. Its partial sum corresponding to k repetitions of this pattern is precisely Okp — Ekm. Using (3), (2), and the fact that 
Hn ≈ γ + ln n (≈ means the difference goes to zero as n approaches infinity), we get

Okp — Ekm    =   H2kp  —  1/2 Hkp  —  1/2 Hkm 
	          ≈   ln(2kp)  +  γ  —  (1/2 ln(kp)  +  γ/2)  —   (1/2 ln(km) + γ/2)
	          =   ln 2  +  ln(kp)  —  1/2 ln(kp)  —  1/2 ln(km)
	         =   ln 2  +  1/2  (ln(kp)  —   ln(km))
	         =    ln 2  +  1/2 ln(p/m)  =  ln 2  +  1/2 ln r.
									
Taking limits as k goes to infinity shows that partial sums consisting of k repetitions of the ``p positive terms and m negative terms'' pattern converge to the desired limit of ln 2  +  1/2 ln r. But partial sums that stop without completing such a pattern must also converge to the same limit.  Indeed, there are always fewer than p + m unit fractions in an ``incomplete'' term, and each of them goes to 0 as k goes to infinity; therefore the difference between complete and incomplete partial sums approaches 0. This completes the proof in the special case we are considering. For the general proof see the article by Cowen, Davidson, and Kaufman cited earlier.

Suggestions for Student Exercises

We certainly enjoyed the experience of exploration and discovery on this topic that were made possible by Mathematica. There is much that we have left unsaid and more to be explored and discovered. For starters, all students can find their own personal rearranged AHS identities (there are plenty to go around). For more of a challenge, there are other conditionally convergent series to be investigated. But without the magical γ, results may not come out so harmonically!

Here are some student exercises based on the ideas of this paper and the Mathematica function HarmonicRearrangement presented earlier.

• Use the standard rearrangment technique (repeated U-turns) and hand computations to find the 20 terms of a rearranged AHS that converges to 1/3. Do you see any patterns that look like they might persist? Then use the HarmonicRearrangement function and check that your pattern of sign changes agrees with its output. Does this cause you to revise your guess about the ultimate pattern for target 1/3?

• Using the formula log 2 + 1/2 log r, find the exact sum of the series 1 — 1/2 — 1/4 + 1/3 — 1/6 — 1/8 + 1/5 — 1/10 — 1/12 + 1/7 — 1/14 — 1/16 + ⋯.

• Suppose we wish to create a rearrangement of the AHS that is made up of repetitions of a ``p positive terms and m negative terms'' pattern and has sum equal to 1/2. Explain why this is impossible and then find values for p and m that give a sum that is within 0.001 of 1/2.

• Using HarmonicRearrangement, investigate the patterns that arise in the rearranged AHS's for various targets between 0 and 5. In particular, look at the patterns of sign changes, assume they persist, and keep track of the ratios of positive terms to negative terms for your targets. Make a plot (by hand) of ratios vs. targets, and then redo the plot on semilog paper (equivalently, use Mathematica's Plot command to plot the logarithms of the ratios against the targets). This last plot should allow you to make a good guess about a formula that might underlie this relationship.

Rearrangement Code

HarmonicRearrangement::usage = "HarmonicRearrangement[target] \
rearranges terms of the alternating harmonic series so that \
partial sums converge to target. The bailOut option controls the \
number of terms of the rearranged series. The output contains any \
of three items depending on the options showSeries, showPartialSums, \
and showSignChanges. The default is to show all three.";

showSeries::usage = "showSeries is an option that, when True, \
causes the rearranged series to be shown.";

showPartialSums::usage = "showPartialSums is an option that, \
when True, causes the partial sums of the rearranged series \
at the sign changes to be shown.";

showSignChanges::usage = "showSignChanges is an option that, \
when True, causes the positions of the sign changes in the \
rearranged series to be shown.";

bailOut::usage = "bailOut is an option that gives a number of \
terms at which the program should look for a convenient place to \
bail out. The default value is 70.";

Options[HarmonicRearrangement] = {bailOut->70,
  showSeries->True, showPartialSums->True, showSignChanges->True};

(* g and collapse are auxiliary functions used to turn a list of
   series terms into a list of partial sums at the sign changes. *)

g[s_List, a_] := If[Sign[a] == Sign[Last[Last[s]]], 
    Append[Drop[s, -1], Append[Last[s], a]], Append[s, {a}]];

collapse[series_] := Rest[FoldList[Plus, 0, (Plus @@ #) & /@ 
    Fold[g, {{First[series]}}, Rest[series]]]];

HarmonicRearrangement[target_, opts___] := Module[ 
  {maximum, outputSeries, partials, signChanges, currentSum = 0.,
   j = 1, iEven = 2, iOdd = 1, counters = {}, makeNewSeries,
   jOld = 1, newSeries = {}, NTarget = N[target]},

{maximum, outputSeries, partials, signChanges} = 
  {bailOut, showSeries, showPartialSums, showSignChanges} /. 
    {opts} /. Options[HarmonicRearrangement];

(* makeNewSeries[] is a function that turns a list of sign changes,
which is what counters will be, into a list of terms of the
rearranged series. *)

 makeNewSeries[clist_] := Module[ {j = {1, 2}, i = 2},
  If[newSeries != {}, newSeries,  newSeries = 1 / (Flatten[
    clist /. n_Integer :> Range[j[[i = 3-i]], (j[[i]] += 2 n) - 2, 2]] /.
               x_?EvenQ :> -x) ]];

 While[j <= maximum,  (* The next two While loops do the adding until 
                       an overshoot and subtracting to an undershoot *)
  While[currentSum <= NTarget, j++; currentSum += 1/iOdd;   iOdd += 2];
  AppendTo[counters, j - jOld];  jOld = j;
 
  While[currentSum > NTarget, j++; currentSum -= 1/iEven; iEven += 2];
  AppendTo[counters, j - jOld];  jOld = j];

(* The following code uses Print to generate output
   according to the settings of the output options. *)
   
(Print[#]; Print[" "]) & /@ Select[{
    If[outputSeries, StringForm["The rearranged series: ``", 
      StringTake[StringReplace[
         ToString[InputForm[makeNewSeries[counters]]], 
         {", -" -> " - ", "," -> " +"}], {2, -2}]]],
    If[partials, StringForm[
        "The partial sums just before the sign changes: `` \n", 
          collapse[makeNewSeries[counters]//N]]],
    If[signChanges, StringForm[
     "Numbers of terms that are positive, negative, positive,...: ``",
      counters]]},  # =!= Null &];]

References

C. C. Cowen, K. R. Davidson, and R. P. Kaufman. 1980. Rearranging the alternating harmonic series. American Mathematical Monthly, 87, 817—819.

A. Pringsheim. 1883. Über die Werthveränderungen bedingt convergierten Reihe und Producte, Mathematische Annalen, 22, 455—503.

E. W. Packel and S. Wagon. 1994. Animating Calculus: Mathematica Notebooks for the Laboratory. 
W. H. Freeman, New York.



Ed Packel
Department of Mathematics and Computer Science
Lake Forest College
Lake Forest, IL 60045
packel@math.lfc.edu


Stan Wagon
Department of Mathematics and Computer Science
Macalester College
St. Paul, MN 55105
wagon@macalstr.edu

Code to Generate the Proof By Diagram Figures

a[i_] := 1/i;
rects = Table[Rectangle[{i-1, 0}, {i, a[i]}], {i, 10}];
lines = Table[Line[
  {{i-1, 0}, {i-1, a[i]}, {i, a[i]}, {i,0}}], {i, 10}];
	

Plot[1/x, {x,.5,10.5}, PlotPoints->50,
PlotStyle->AbsoluteThickness[1.5],
  Prolog->{{GrayLevel[0.5], rects}, {AbsoluteThickness[.5], lines}},
	Axes->Automatic, PlotRange->{{0,10.5},{0,1}},
	DefaultFont->{"Helvetica", 6},
	AxesOrigin->{0, 0}, 
	Ticks->{Range[0,10], {ToExpression@#,#}& /@ {"1/2","1/3","1/4","1"}}];

a[i_] := 1/i;   nPieces = (200);  step = (20);
rects = Table[Rectangle[{i-1, 0}, {i, a[i]}], {i, 2, 10}];
lines = Table[Line[{{i-1, 0}, {i-1, a[i]}, {i, a[i]}, {i, 0}}], {i, 2,10}];
{gray, black, white} = GrayLevel /@ {.5,0,1};


pieces = Table[Polygon[Join[Table[{j/step, a[j/step + i]}, {j, 0, step}],
                   {{1, a[i+1]}, {1, a[i]}}]], {i, nPieces}];

image = Plot[1/x, {x, 1.01, 10.5}, PlotPoints->(50), MaxBend->1,
    PlotStyle->{black, AbsoluteThickness[1.5]},

	Prolog->{Text[FontForm["y = ", {"Times-Italic", 14}], {2.3, 0.7}, {-1,0}],
										Text[FontForm["1", {"Times", 14}], {3.5, 0.75}, {-1,0}],
										Text[FontForm["/", {"Times", 14}], {3.73, 0.7}, {-1,0}],
										Text[FontForm["x", {"Times-Italic", 14}], {3.88, 0.65}, {-1,0}],
									{white, Rectangle[{0,0}, {1,1}]},
									{AbsoluteThickness[1], Line[{{11,0},{0,0}, {0,1}, {1,1}}]},
	        	{pieces},
	 {white, 
	   Polygon[Join[Table[{i,a[i]}, {i,1,10,.1}], {{10,0}, {1,0}}]]},
	         {AbsoluteThickness[.5], lines},
	           {gray, rects, black, AbsoluteThickness[.5], lines}
	           }, 
	 Axes->Automatic, PlotRange->{{0,11},{0,1.07}}, 
	 AxesOrigin->{0,0}, DefaultFont->{"Helvetica", 6},
	 Ticks->{Range[0,10], {ToExpression@#,#}& /@ {"1/2","1/3","1/4","1"}}, 
	 DisplayFunction->Identity];
	   
Show[image, DisplayFunction->$DisplayFunction];