# computational complexity: do we gain acceleration?

There is a technique we developed for series acceleration using the Wilf-Zeilberger method. Here is a simple Maple code in this regard, you need to download this too.

The idea is you start with a WZ-pair $(F,G)$ and you get an infinite family of hypergeometric series that help compute your constant. Take for example, the Riemann zeta $\zeta(3)=\sum_{n=1}^{\infty}\frac1{n^3}$ which is slow in its rate of convergence. We are able to generate an endless list, call these $s$-step accelerations. The first few include: $$\zeta(3)=\frac52\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{\binom{2n}n\binom{n}nn^3} \tag {1-step}$$ $$\zeta(3)=\frac14\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{\binom{3n}n\binom{2n}nn^3}\frac{56n^2-32n+5}{(2n-1)^2} \tag {2-step}$$ $$\zeta(3)=\frac1{18}\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{\binom{4n}n\binom{3n}nn^3}\frac{5265n^4-7182n^3+3717n^2-828n+68}{(3n-1)^2(3n-2)^2} \tag {3-step}$$ This continues ad infinitum.

(1) At each step, we gain large binomial denominator (desirable);

(2) At each step, we incur a rational polynomial with increasing degrees.

Question. In view of the competing gain-loss, (1) and (2), does the computational complexity or efficiency improve or gets worse?

Caveat. I don't know much about Complexity Theory, hence my question here. Thank you for help.

• Actually, I think that for the case in question it's a complete no-brainer. For the 3-step sum by the time you've taken 20 terms you're correct to about 37 decimal places, and for the first sum it would take something like $10^{12}$ terms to get that far. I am pretty confident that you can compute 80 choose 20 in fewer than $10^{12}$ steps :-) – Kevin Buzzard Jan 16 '17 at 20:01