Tuesday, September 12, 2017

Euler's transformation - series acceleration

Theorem. Assume that $(a_n)_{n\geq 0}$ satisfies $\limsup_{n\to\infty} |a_n|^{1/n} \leq 1$. Then for $x\in[0,1)$ we have $$ \sum_{n=0}^{\infty} (-1)^n a_n x^n = \frac{1}{1+x} \sum_{n=0}^{\infty} (-1)^n \Delta^n a_0 \left( \frac{x}{1+x}\right)^n . \tag{*} $$ Here, both sides converges absolutely and $\Delta^n$ is the $n$-fold forward difference defined by $$ \Delta^n a_j = \sum_{k=0}^{n} \binom{n}{k} (-1)^{n-k} a_{j+k}. $$

Proof. There is nothing to prove if $x = 0$, so we assume throughout that $0 < x < 1$. First, absolute convergence of the LHS of $\text{(*)}$ is straightforward. To verify absolute convergence of the RHS, we first note that there exist $C$ and $\beta$ such that $1 < \beta < \frac{x+1}{2x}$ and $|a_n| \leq C \beta^n$. Then $$ \frac{1}{2^n} |\Delta^n a_j| \leq \max_{0\leq k \leq n} |a_{j+n}| \leq C\beta^{j+k}. \tag{1} $$ Then absolute convergence of the RHS of $\text{(*)}$ follows from comparison together with the following estimate $$ \left| (-1)^n \Delta^n a_0 \left( \frac{x}{1+x}\right)^n \right| \leq C \left( \frac{2\beta x}{1+x}\right)^n. $$ Next we show the equality $\text{(*)}$. We write \begin{align*} \sum_{n=0}^{\infty} (-1)^n a_n x^n &= \sum_{n=0}^{\infty} (-1)^n a_0 x^n + \sum_{n=0}^{\infty} (-1)^n (a_n - a_0) x^n \\ &= \frac{a_0}{1+x} - x \sum_{n=0}^{\infty} (-1)^n (a_{n+1} - a_0) x^n. \end{align*} The latter sum can be computed as \begin{align*} \sum_{n=0}^{\infty} (-1)^n (a_{n+1} - a_0) x^n &= \sum_{n=0}^{\infty} (-1)^n \left( \sum_{l=0}^{\infty} \Delta a_l \right) x^n \\ &= \sum_{l=0}^{\infty} \Delta a_l \left( \sum_{n=l}^{\infty} (-1)^n x^n \right) \\ &= \frac{1}{1+x} \sum_{l=0}^{\infty} (-1)^l \Delta a_l x^l. \end{align*} Here, interchanging the order of summations is justified by the absolute convergence. So we obtain $$ \sum_{n=0}^{\infty} (-1)^n a_n x^n = \frac{a_0}{1+x} - \frac{x}{1+x} \sum_{l=0}^{\infty} (-1)^l \Delta a_l x^l. \tag{2} $$ Since we have $\limsup_{n\to\infty} |\Delta a_n|^{1/n} \leq 1$, we can recursively apply $\text{(2)}$ to obtain $$ \begin{split} \sum_{n=0}^{\infty} (-1)^n a_n x^n &= \frac{1}{1+x} \sum_{n=0}^{N-1} (-1)^n \Delta^n a_0 \left( \frac{x}{1+x}\right)^n \\ &\qquad + \left( -\frac{x}{1+x} \right)^N \sum_{l=0}^{\infty} (-1)^l \Delta^N a_l x^l. \end{split} \tag{3} $$ But by the estimate $\text{(1)}$, we have $$ \left| \left( -\frac{x}{1+x} \right)^N \sum_{l=0}^{\infty} (-1)^l \Delta^N a_l x^l \right| \leq \left( \frac{2\beta x}{1+x} \right)^N \sum_{l=0}^{\infty} C(\beta x)^{l}. $$ Since $\beta x < \frac{2\beta x}{1+x} < 1$, this bound vanishes as $N \to \infty$. Therefore we obtain the desired identity. ////

Example. Let $f : [0,\infty) \to \mathbb{R}$ be a completely monotone function and set $a_n = f(n)$. We know that $f$ admits the representation $$ f(s) = \int_{[0,\infty)} e^{-st} \, \mu(dt) $$ for some finite Borel measure $\mu$ on $[0,\infty)$. Then a simple computation shows that $$ (-1)^n \Delta^n a_0 = \int_{[0,\infty)} (1 - e^{-t})^n \, \mu(dt). $$ This sequence is non-negative and decreases to $0$ as $n\to\infty$. So the limiting form of $\text{(*)}$ is available and we obtain $$ \sum_{n=0}^{\infty} (-1)^n a_n = \sum_{n=0}^{\infty} \frac{(-1)^n \Delta^n a_0}{2^{n+1}}. $$ Notice that the resulting transformation converges exponentially fast regardless of how slow the original series was. As a useful example, consider $\mu(dt) = t^{p-1}e^{-t}/\Gamma(p)$ for $p > 0$. Then we have the following series acceleration for the Dirichlet eta function: $$ \sum_{n=0}^{\infty} \frac{(-1)^n}{(n+1)^p} = \sum_{n=0}^{\infty} \frac{1}{2^{n+1}} \sum_{k=0}^{n} \binom{n}{k} \frac{(-1)^{k}}{(k+1)^p}. $$ Of course this can be used to compute the Riemann zeta function.