Why the Euler Transformation converges more quickly?

Question

There is a problem I've met.

I already know that the Leibniz series $\sum_{n=0}^\infty \frac{(-1)^n}{2n+1}$ converges to $\frac{\pi}{4}$, but it does very slowly.

Wikipedia says that Euler Transformation makes the series converge more quickly. Its transformation is $\sum_{n=0}^\infty \frac{(2)^n(n!)^2}{(2n+1)!}$.

By python programming, I confirmed that it converges more quickly than original one, but I don't know why it happens. Wikipedia does not give me a precise proof of rapid convergence.

I found a document that proves the rapidity of convergence. In the document, however, does not give existence of such weight function $w(t)$, satisfying $\int_0^1 t^k w(t)dt=a_k$.

Hence, the question is that, "is there a proof for rapid convergence of Euler transformation?"

Thanks.

Answer 1

A proof of rapid convergence of the Euler transformation applicable to the series \begin{align*} \sum_{n=0}^\infty \frac{(-1)^n}{2n+1}&=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\cdots\\ &=\frac{1}{2}\left(1+\frac{1}{3}+\frac{1\cdot 2}{3\cdot 5}+\frac{1\cdot2\cdot 3}{3\cdot 5\cdot 7}+\cdots\right)\\ \end{align*} is given by Konrad Knopp in Theory and Application of Infinite Series in section 155.

In order to see what's going on we need to know what is meant by rapid convergence. We find in section 166 the following definition:

• Definition 1: Given two convergent series $\sum c_n=s$ and $\sum c_n^{\prime}=s^{\prime}$ of positive terms, whose partial sums are denoted by $s_n$ and $s_n^{\prime}$, the corresponding remainders by $s-s_n=r_n, s^{\prime}-s_n^{\prime}=r_n^{\prime}$, we say that the second converges more or less rapidly (or better or less well) than the first, according as \begin{align*} \lim\frac{r_n^{\prime}}{r_n}=0\qquad\quad\text{or}\qquad\quad\lim\frac{r_n^{\prime}}{r_n}=+\infty, \end{align*}

If the limit of this ratio exists and has a finite positive value, or if it be known merely that its lower limit $> 0$ and its upper limit $< +\infty$, then the convergence of the two series will be said of the same kind. In any other case a comparison of the rapidity of convergence of the two series is impracticable.

The following theorem is stated for series which are fully monotone. These are series for which all the differences $\Delta^k a_n\ (k,n=0,1,2,\ldots)$ are positive.

• Theorem 1: If $\sum_{n=0}^\infty(-1)^na_n$ is an alternating series for which the (positive) numbers $a_0, a_1,\ldots$ form a fully monotone null sequence, while, from the first, $\frac{a_{n+1}}{a_n}\geq a>\frac{1}{2}$ (for every $n$), then the transformed series $\sum\frac{1}{2^{n+1}}\Delta^n a_0$ converges more rapidly than the given series.

The proof given by K. Knopp goes as follows:

Proof: Since $\frac{a_{n+1}}{a_n}\geq a$, we have $a_n\geq a_0\cdot a^n$. Further, for the remainder $\gamma_n$ of the given series we have \begin{align*} (-1)^{n+1}r_n=a_{n+1}-a_{n+2}+-\cdots=\Delta a_{n+1}+\Delta a_{n+3}+\Delta a_{n+5}+\cdots \end{align*} Since $\left(\Delta a_{\nu}\right)$ is itself a monotone null sequence, \begin{align*} |r_n|\geq \frac{1}{2}\left(\Delta a_{n+1}+\Delta a_{n+2}+\Delta a_{n+3}+\cdots\right)=\frac{1}{2}a_{n+1} \geq \frac{1}{2}a_0\cdot a^{n+1} \end{align*} On the other hand, as $\Delta^n a_0-\Delta^{n+1} a_0=\Delta^n a_1\geq 0$, the numerators of the transformed series also form a monotone null sequence, and in particular are all $\leq a_0$.

Consequently the remainders $\gamma_n^{\prime}$ of the transformed series, - which, moreover, is a series of positive terms, - satisfy \begin{align*} r_n^{\prime}=\frac{\Delta^{n+1} a_0}{2^{n+2}}+\cdots \leq \frac{a_0}{2^{n+2}}\left(1+\frac{1}{2}+\frac{1}{4}+\cdots\right)=\frac{a_0}{2^{n+1}} \end{align*} Consequently, we have \begin{align*} \left|\frac{r_n^{\prime}}{r_n}\right|\leq\frac{1}{a}\left(\frac{1}{2a}\right)^n, \end{align*} which proves the theorem.

Note: A paper with some other interesting discussions of the rapidity of convergence is Transformations to Speed the Convergence of Series by J. B. Rosser from 1951.

Answer 2

Since the relevance of $\int_0^1t^kw(t)\,\mathrm{d}t=a_k$ is not clear, I present a proof of the Euler Series Transformation.

---

Lemma $\bf{1}$:

For all non-negative integer $k$, $$ \sum_{n=k}^\infty\frac{\binom{n}{k}}{2^{n+1}}=1\tag1 $$ Proof: $$ \begin{align} \sum_{k=0}^\infty\sum_{n=k}^\infty\frac{\binom{n}{k}}{2^{n+1}}x^k &=\sum_{n=0}^\infty\sum_{k=0}^n\frac{\binom{n}{k}}{2^{n+1}}x^k\tag{2a}\\ &=\sum_{n=0}^\infty\frac{(x+1)^n}{2^{n+1}}\tag{2b}\\ &=\frac12\frac{1}{1-(x+1)/2}\tag{2c}\\[3pt] &=\frac{1}{1-x}\tag{2d}\\[3pt] &=\sum_{k=0}^\infty x^k\tag{2e} \end{align} $$ Explanation:
$\text{(2a)}$: Multiply the sum by $x^k$ and sum, then change the order of summation
$\text{(2b)}$: sum in $k$ using the Binomial Theorem
$\text{(2c)}$: sum in $n$ using a Geometric Series
$\text{(2d)}$: simplify
$\text{(2e)}$: write as a geometric series

Equating the coefficients of $x^k$ in $(2)$ proves the Lemma.
$\large\square$

Lemma $\bf{2}$:

For any non-negative integer $N$, $$ \sum_{k=0}^N\sum_{n=k}^N2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]=1-2^{-N-1}\tag3 $$ Furthermore, for any non-negative integers $k$ and $N$, $$ \sum_{n=k}^N2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]\ge0\tag{4} $$ Proof: $$ \begin{align} &\sum_{k=0}^N\sum_{n=k}^N2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]\tag{5a}\\ &=\sum_{n=0}^N\sum_{k=0}^n2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]\tag{5b}\\ &=\sum_{n=0}^N2^{-n-1}[2^n-(2^n-1)]\tag{5c}\\[6pt] &=1-2^{-N-1}\tag{5d} \end{align} $$ Explanation:
$\text{(5b)}$: change the order of summation
$\text{(5c)}$: Binomial Theorem
$\text{(5d)}$: sum the geometric series

$(5)$ proves $(3)$.

Lemma $1$ implies that $$ \sum_{n=k}^\infty2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right] = 1-1 = 0\tag6 $$ Note that $$ \binom{n}{k+1}=\frac{n-k}{k+1}\binom{n}{k}\tag7 $$ Therefore, under the conditions above that $0\le k\le n$, the terms in $(6)$ are positive when $n\lt2k+1$ and then negative when $n\gt2k+1$. Since the sum in $(6)$ is $0$, all of its partial sums must be positive.
$\large\square$

Corollary $\bf{2.1}$: $$ \sum_{k=0}^N\left|\sum_{n=k}^N2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]\right|=1-2^{-N-1}\tag8 $$ Proof:

Since the partial sum inside the absolute value is always positive, this is the same sum as in Lemma $2$.
$\large\square$

Theorem (Euler Series Transformation):

If $$ \sum_{k=0}^\infty a_k\tag9 $$ converges, then $$ \sum_{n=0}^\infty2^{-n-1}\sum_{k=0}^n\binom{n}{k}a_k=\sum_{k=0}^\infty a_k\tag{10} $$ Proof (Euler Series Transformation):

Formally, we would simply like to use Lemma $1$ after switching the order of summation. However, the sum of $a_k$ may not converge absolutely, so we must switch the order of summation with care.

Let $S_k$ be the partial sum $$ S_k=\sum_{j=0}^ka_j\tag{11} $$ and $S$ be the limit of $S_k$ as $k\to\infty$.

Then, $a_k=S_k-S_{k-1}$. This yields the partial sum $$ \begin{align} &\sum_{n=0}^N2^{-n-1}\sum_{k=0}^n\binom{n}{k}a_k\tag{12a}\\ &=\sum_{n=0}^N2^{-n-1}\sum_{k=0}^n\binom{n}{k}(S_k-S_{k-1})\tag{12b}\\ &=\sum_{n=0}^N2^{-n-1}\sum_{k=0}^n\left[\binom{n}{k}-\binom{n}{k+1}\right]S_k\tag{12c}\\ &=\sum_{k=0}^N\sum_{n=k}^N2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]S_k\tag{12d} \end{align} $$ Pick an $\epsilon\gt0$. Choose an $M$ so that $|S_k - S|\lt\epsilon$ for all $k\ge M$ and so that $2^{-M-1}\lt\epsilon$. Lemma $1$ implies that for each non-positive integer $k$, $$ \sum_{n=k}^\infty2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]=1-1=0\tag{13} $$ Choose an $N\ge M$ so that for all $m\ge N$ and $k\lt M$, $$ \left|\,\sum_{n=k}^m2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]\,\right|\lt\frac{\epsilon}{M}\tag{14} $$ Now we have $$ \begin{align} &\left|\,\left(\sum_{n=0}^N2^{-n-1}\sum_{k=0}^n\binom{n}{k}a_k\right)-S\,\,\right|\tag{15a}\\ &=\left|\,\left(\sum_{k=0}^N\sum_{n=k}^N2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]S_k\right)-S\,\,\right|\tag{15b}\\ &=\left|\,\left(\sum_{k=0}^N\sum_{n=k}^N2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]\left(S_k-S\right)\right)-2^{-N-1}S\,\,\right|\tag{15c}\\ &\le\left|\,\left(\sum_{k=0}^{M-1}\sum_{n=k}^N2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]\left(S_k-S\right)\right)\,\right|\tag{15d}\\ &+\left|\,\left(\sum_{k=M}^N\sum_{n=k}^N2^{-n-1}\left[\binom{n}{k}-\binom{n}{k+1}\right]\left(S_k-S\right)\right)\,\right|\tag{15e}\\[9pt] &+2^{-N-1}\left|\,S\,\right|\tag{15f}\\[12pt] &=\frac\epsilon{M}M\max_k\left(\left|\,S_k-S\,\right|\right)+\epsilon+\epsilon\left|\,S\,\right|\tag{15g} \end{align} $$ Explanation:
$\text{(15a)}$: partial sum minus the expected sum
$\text{(15b)}$: apply $(12)$
$\text{(15c)}$: apply Lemma $2$
$\text{(15d)}$: first part of $\text{(15c)}$
$\phantom{\text{(15d):}}$ $(14)$ says that each of the $M$ terms is bounded by $\frac\epsilon{M}$ times $\max_k|S_k-S|$
$\text{(15e)}$: next part of $\text{(15c)}$
$\phantom{\text{(15e):}}$ bounded by Corollary $2.1$ and $|S_k-S|\le\epsilon$
$\text{(15f)}$: last part of $\text{(15c)}$
$\phantom{\text{(15f):}}$ bounded by $2^{-M-1}\le\epsilon$ times $S$
$\text{(15g)}$: triangle inequality

Thus, $(15)$ says that $$ \sum_{n=0}^\infty2^{-n-1}\sum_{k=0}^n\binom{n}{k}a_k=S=\sum_{k=0}^\infty a_k\tag{16} $$ $\large\square$

Answer 3

You are done once you have found a measure $\mu$ for which $a_n=\int_0^1 t^n\,d\mu$, where $a_n=\frac1{2n+1}$. Hausdorff proved that $\mu$ exists if and only if $a_n$ is completely monotonic, meaning that $a_n$ decreases monotonically to zero, and the differences $a_{n+1}-a_{n}$ increase monotonically to zero, and the second differences $(a_{n+2}-a_{n+1})-(a_{n+1}-a_{n})$ decrease monotonically to zero, and so on for all higher order differences. See https://en.wikipedia.org/wiki/Hausdorff_moment_problem for references and more details.

It is indeed true that $a_n=\frac1{2n+1}$ is completely monotonic. Letting $\Delta a_n$ denote $a_{n+1}-a_n$, then $$ a_n=\frac1{2n+1}\searrow 0 $$ $$ \Delta a_n=\frac1{2n+3}-\frac1{2n+1}=\frac{-2}{(2n+3)(2n+1)}\nearrow 0 $$ $$ \Delta^2 a_n=\frac{-2}{(2n+5)(2n+3)}-\frac{-2}{(2n+3)(2n+1)}=\frac{2\cdot 4}{(2n+5)(2n+3)(2n+1)}\searrow 0 $$ The pattern continues. You can prove by induction that $$ \Delta^k a_n=(-1)^k\frac{2\cdot 4\cdots (2k)}{(2n+1)(2n+3)\cdots(2n+2k)} $$

Answer 4

For your specific case note that $$\frac1{2n+1}=\int_0^1x^{2n}\mathrm dx.$$ Then $$\sum_{n=0}^{\infty}\frac{(-1)^n}{2n+1}=\int_0^1\frac1{1+x^2}\mathrm dx.$$ The Euler transform is based on the following series for the integrand: $$\frac1{1+x^2}=\sum_{n=0}^{\infty}\frac{(1-x^2)^n}{2^{n+1}}.$$ The $k^{\mathrm{th}}$ partial sum on the right (summing over $n<k$) is a pretty good approximation on the interval $[0,1]$. The greatest difference occurs for $x=0$ and equals $2^{-k}$. Therefore the integral $$\int_0^1 \sum_{n=0}^{k-1}\frac{(1-x^2)^n}{2^{n+1}}\mathrm dx$$ is a low estimate for the alternating sum and is off by less than $2^{-k}$. Now this last integral is exactly the $k^{\mathrm{th}}$ partial sum of the Euler transform of the original sequence.