An algorithm for making conditionally convergent series take arbitrary values?

This thread reminded me of an old unsettled question I have.

Given an arbitrary conditionally convergent series $\beta=\sum\limits_{k=1}^\infty a_k$ and a target value $\alpha$, is there an algorithm for finding the permutation of the original series that will make it sum to $\alpha$? Alternatively, if the permutation cannot be explicitly given, is there an algorithm for finding the first few terms of the rearrangement of the series for $\beta$ to make it sum to $\alpha$?

So far, what I've seen is a method for rearranging the alternating harmonic series $\log\,2=\sum\limits_{k=1}^\infty \frac{(-1)^k}{k}$ in Stan Wagon's Mathematica in Action. I would like to know if the method there is generalizable to arbitrary conditionally convergent series.

• @Sri: That settles the alternative question, it looks. But let's take the $\log\,2$ series again as an example. Is there an algorithm that starts from the series and the target value $\log\sqrt 2$ and returns the series $$\sum_{k=0}^\infty \left(\frac1{2k+1}-\frac1{4k+2}-\frac1{4k+4}\right)$$? – J. M. is a poor mathematician Sep 8 '11 at 14:35
• For specific "nice" target values, there could be "nice" rearrangements that does the job. I am sure how we can tell the algorithm: "$\log \sqrt{2}$ is nice, so I prefer a nice rearrangement as my answer". (By the way, have you tried Ross's algorithm with $\log \sqrt{2}$. What rearrangement does that give?) – Srivatsan Sep 8 '11 at 14:42
• I'm far away from my box with Mathematica; so I'll try programming Ross's algorithm later. For now, I don't know what the algorithm will give for that case. – J. M. is a poor mathematician Sep 8 '11 at 14:46
• Actually, the "overshoot-undershoot" algorithm seems to work for $\alpha = \log \sqrt{2}$ to give the rearrangement you have in mind. I haven't proved it, but I tried it in a calculator for the first 5 summands ($k=0$ till $k=4$ in your new series). (By the way, a small nitpick. The way you have written the series for $\log \sqrt{2}$, it is not a rearrangement of the $\log 2$ series. In fact, the new series is even absolutely convergent :-). But I get what you mean, of course...) – Srivatsan Sep 8 '11 at 14:51
• @J.M., that's a bit much to call for unless you have some serious restrictions on the target value in mind. Otherwise, there are uncountably many possible targets, but at most countably many nicely-shaped series expressions. (Yes, this argument is a little frayed at the edges, since we can arguably assume that the target can be finitely described somehow or we wouldn't be able to run an algorithm on it -- but if we accept arbitrary finite descriptions of the target, then the over/undershoot algorithm shoud also itself count as a "series expression".) – Henning Makholm Sep 8 '11 at 15:10

The following paper might answer your question: C. C. Cowen, K. R. Davidson, and R. P. Kaufman, Rearranging the alternating harmonic series, American Mathematical Monthly 87 (1980) 17-19.

The useful (old) theorem here is:

THEOREM. Suppose the Alternating Harmonic Series is rearranged so that, if $p_n$ and $m_n$ are the numbers of positive and negative terms among the first $n$ terms, then $r =$

$$\lim_{n \to \infty}\; p_n / m_n$$

exists. Then series sums to $\log 2 + \frac12 \log r$.

So to hit a target $T$, just let the positive:negative ratio be $(1/4) e^{2T}$.

Of course, if this last expression turns out to be rational (as when $T = \log 2$), things are particularly nice.

Stan Wagon

• Thanks! I have to wonder if there's a similar theorem for e.g. $\frac{\pi}{4}=\sum_{k=0}^\infty \frac{(-1)^k}{2k+1}$... and thank you also for writing a wonderful book. :) – J. M. is a poor mathematician Sep 8 '11 at 15:49
• The result (for harmonic series) is intuitive due to $\sim \log n$ growth, but will not be applicable for other conditionally convergent series, e.g. $\sum_{n \ge 1} (-1)^n n^{-1/2}$. – Sasha Sep 8 '11 at 16:37
• @Sasha, for the series you write, one can reach any limit with $p_n=an+c\sqrt{n}+O(1)$ and $m_n=bn+O(1)$ for $a=2b(3-2\sqrt2)$ and a suitable $c$ depending on $a$ and the desired limit. The proof uses only the fact that there exists $u$ such that $\sum_{k\le n}1/\sqrt{k}=\frac12\sqrt{n}+u+o(1)$. – Did Sep 8 '11 at 17:20
• @Didier Thanks, I stand corrected. I misread the theorem, and incorrectly thought that $p_n$ and $m_n$ are partial sums for positive and negative terms in conditionally convergent series. – Sasha Sep 8 '11 at 18:00
• @J.M. The analogue result for the series $\sum_k(-1)^k/(2k+1)$ is that a positive:negative ratio $\exp(4T-\pi)$ hits the target $T$. – Did Sep 8 '11 at 19:37

The first few terms can be anything you want, because by the Riemann series theorem you can rearrange the rest to give the proper sum. In the proof of the theorem, you basically add enough positive terms to get greater than your target, then enough negative terms to get smaller, and so on. This gives an effective procedure and works on any conditionally convergent series, but it doesn't tell you what the 1000th term (say) of the rearranged series will be.

• Thanks, that settles the "alternative" question. :) I'm still looking out for something that works on what I presented in the comments though. – J. M. is a poor mathematician Sep 8 '11 at 14:43

A slight formal modification of the series $$\log\left(\frac{p}{q}\right)=\sum_{i=0}^\infty \left(\sum_{j=pi+1}^{p(i+1)}\frac{1}{j}-\sum_{k=qi+1}^{q(i+1)}\frac{1}{k}\right)$$ allows to compute numbers other than the logarithms of positive rationals.

Instead of positive integers $p,q$, consider integer sequences $p_n, q_n$ such that $$p_0=q_0=0$$ $$p_{n+1}>p_n$$ $$q_{n+1}>q_n$$ and $$\lim_{n \to \infty} \frac{p_n}{q_n}=e^T$$

The following rearrangement of the cancelling harmonic series converges to the target $$T=\sum_{n=0}^\infty \left(\sum_{i=p_n+1}^{p_{n+1}} \frac{1}{i} - \sum_{j=q_n+1}^{q_{n+1}} \frac{1}{j}\right)$$