## Acceleration of alternating series

Let $f(n):\mathbb{N}\to\mathbb{R}$ be a positive decreasing function such that $\lim_{n\to\infty}f(n)=0$. Then the alternating series

$\displaystyle \sum_{n=0}^{\infty}(-1)^nf(n)$

converges. Depending on the rate at which $f$ decays it may however take many terms to get a decent approximation of the sum. Examples of such slowly converging series are

$\displaystyle \log(2) = \sum_{n=0}^{\infty}(-1)^n\frac{1}{n+1}$

$\displaystyle \frac{\pi}{4} = \sum_{n=0}^{\infty}(-1)^n\frac{1}{2n+1}$

A well known method to accelerate the convergence of such alternating series uses the binomial transform of the function $f$ as follows. For $m \geq 0$ let $\Delta^m f$ be the $m$-th difference of $f$:

$\displaystyle (\Delta^m f)(n) = \sum_{k=0}^m (-1)^k{m \choose k} f(n+k)$

Then it turns out that

$\displaystyle \sum_{n=0}^{\infty}(-1)^nf(n) = \sum_{n=0}^{\infty}\frac{(\Delta^n f)(0)}{2^{n+1}}$

and the right hand side may converge much faster. The binomial transform for the two examples above can be computed explicitly to obtain

$\displaystyle \log(2)=\sum_{n=0}^{\infty}\frac{1}{2^{n+1}(n+1)}$

$\displaystyle \frac{\pi}{4}=\sum_{n=0}^{\infty}\frac{n!}{2\cdot(2n+1)!!} = \frac{1}{2} + \frac{1}{2\cdot 3} + \frac{2}{2 \cdot 3 \cdot 5} + \frac{2 \cdot 3}{2 \cdot 3 \cdot 5 \cdot 7} + \ldots$

Both transformed series indeed converge much faster than the original ones. You may recognize the first as the series for $-\log(1-x)$ taken at $x=\tfrac{1}{2}$. The second one is harder to spot but it turns out to be the series of

$\displaystyle \frac{\arcsin(x)}{\sqrt{2-2x^2}}$

taken at $x=\tfrac{1}{2}\sqrt{2}$.

The binomial transform is a great tool if you can find an explicit expression for it such as in both examples above. This is however not a trivial transform in general. If you do not know an explicit expression for the binomial transform then it is also not very convenient to compute: $(\Delta^n f)(0)$ depends on the values $f(k)$ for all $k \leq n$.

There is however another much simpler method that only involves the repeated difference $\Delta^m f$ for a single fixed value of $m \geq 1$. This difference is now easy to compute (numerically) since $(\Delta^m f)(n)$ depends only on $m+1$ consecutive values of $f$. It is convenient for the sake of notation to extend $f$ to $\mathbb{Z}$ by setting $f(n)=0$ for all $n < 0$. Then $(\Delta^m f)(n) = 0$ for all $n < -m$.

Now the following equalities hold in which the second and third sums are taken over $\mathbb{Z}$:

$\displaystyle \sum_{n=0}^{\infty}(-1)^nf(n) = 2^{1-m}\sum_{n \textrm{ even}}(\Delta^m f)(n) = -2^{1-m} \sum_{n \textrm{ odd}} (\Delta^m f)(n)$

If all terms $(\Delta^m f)(n)$ are positive for $n \geq 0$ then partial sums increase for the second series and decrease for the third from $n=0$ onward. This means that these partial sums are lower and upper bounds for the series which is useful to estimate the remaining error for these partial sums.

As an example take $m=2$. The series for $\log(2)$ and $\tfrac{\pi}{4}$ now become

$\displaystyle \log(2) = \frac{1}{2} + \sum_{n=0}^{\infty}\frac{1}{(2n+1)(2n+2)(2n+3)} = \frac{3}{4} - \sum_{n=0}^{\infty}\frac{1}{(2n+2)(2n+3)(2n+4)}$

$\displaystyle \frac{\pi}{4} = \frac{1}{2} + \sum_{n=0}^{\infty}\frac{4}{(4n+1)(4n+3)(4n+5)} = \frac{5}{6} - \sum_{n=0}^{\infty}\frac{4}{(4n+3)(4n+5)(4n+7)}$