Series acceleration - Examples of how to find faster converging algorithm for 3 different series

Question

Presume we have obtained an approximation $a$ in a set amount of time $t$ for the 3 series below.

I am looking for examples of how to find faster converging algorithm (where they exist) than $t$ for the 3 series below $\mathbf{(Updated)}$ via series acceleration methods:

1. $S_1 = 1 + \frac{1}{4}+\frac{1}{9}+...=\sum_{n=1}^{\infty}\frac{1}{n^2}$ to 4 decimal places.

2. $S_2=\sum_{n=0}^{\infty}\frac{4^{n+1}}{(3n+1)!}$ to 6 decimal places.

3. $S_2=\sum_{n=1}^{\infty}\frac{2^{n}n!}{n^n}$ to 8 decimal places.

Answer 1

Before I start, note that the first and last series should start at $n=1$ to make much sense.

---

Let $S'=\sum_{n=1}^\infty\frac{(-1)^{n+1}}{n^2}$. Now notice that

$$S_1-S'=\sum_{n=1}^\infty\frac{1+(-1)^n}{n^2}=\sum_{n=1}^\infty\frac2{(2n)^2}=\frac12S_1$$

Notice above that every odd term cancels out, and we are left with twice the even terms (even = $2n$).

Subtract half of $S_1$ and add $S'$ to both sides to get

$$\frac12S_1=S'$$

$$S_1=2S'$$

Now take the Euler transform of $S'$ to get

$$S'=\sum_{n=0}^\infty\frac1{2^{n+1}}\sum_{k=0}^n\binom nk\frac{(-1)^k}{(k+1)^2}$$

And likewise,

$$\left|S_1-\sum_{n=0}^{10}\frac1{2^n}\sum_{k=0}^n\binom nk\frac{(-1)^k}{(k+1)^2}\right|<\frac1{10^4}$$

The original series would've taken about ten thousand terms to reach this accuracy. The exact value is $S_1=\frac{\pi^2}6$.

---

Consider this more general function:

$$f(x)=\sum_{n=0}^\infty\frac{x^n}{(3n+1)!}$$

By Lagrange remainder,

$$\left|f(4)-\sum_{n=0}^N\frac{4^n}{(3n+1)!}\right|\le\frac{f^{(N+1)}(4)}{(N+1)!}4^{N+1}$$

So it is quick to see that with $N=4$, we have

$$\left|f(4)-\sum_{n=0}^4\frac{4^n}{(3n+1)!}\right|<\frac1{10^7}$$

Indeed, it is difficult to accelerate the convergence of a series that already converges very fast...

The exact value is $f(4)=\frac{e^{3/\sqrt[3]2}+2\sin\left(\frac{\sqrt3}{\sqrt[3]2}-\frac\pi6\right)}{3\sqrt[3]4e^{-1/\sqrt[3]2}}$.

---

By Stirling's approximation, notice that

$$\frac{2^nn!}{n^n}\approx\left(\frac2e\right)^n$$

and so it should take roughly 60-80 terms to get $10^{-8}$ accuracy. However, this also let's us approximate the tail pretty easily:

$$\sum_{n=k}^\infty\frac{2^nn!}{n^n}\approx\sum_{n=k}^\infty\left(\frac2e\right)^n=\frac e{e-2}\left(\frac2e\right)^k$$

And so,

$$\left|\sum_{n=80}^\infty\frac{2^nn!}{n^n}-\frac e{e-2}\left(\frac2e\right)^{80}\right|<\frac1{10^8}$$