# Is there an algorithm to determine whether a series converges?

I thought of this question in connection with Calculus II (a course in the US which includes, among other things, techniques of integration and convergence tests for series, both of which are taught as a bunch of techniques that might work for a particular problem) but feel free to make the answers as complicated as necessary. The question of whether an elementary antiderivative of an elementary function $f(x)$ exists is answered by the Risch algorithm and I want to ask a similar question about convergence of series.

Let $f(x)$ be an elementary function and $a_n=f(n)$ for $n=0,1,2,\ldots$. Is there an algorithm that will tell us if $\sum_{n=0}^\infty a_n$ converges? Are there examples that are undecidable?

The integral test might help convert a solution in one problem to the other but I don't see that it solves the problem entirely.

-
What do you mean by an "Elementary function?" –  Hooman Nov 7 '12 at 16:57
See en.wikipedia.org/wiki/Elementary_function Basically functions that can be built from exponentials, logs, nth roots, complex constants through composition,+,-,*,/ (note that this includes trig functions) –  Martin Leslie Nov 7 '12 at 17:00
One should probably also insist that the complex constants are computable –  Hagen von Eitzen Nov 7 '12 at 17:01
Actually, the integral test seems to be of no help at all. For example $\sum_{n=0}^\infty e^{-n^2}$ converges in spite of $x\mapsto \int_0^x e^{-t^2}\,dt$ being non-elementary. –  Hagen von Eitzen Nov 7 '12 at 17:04
Good point Hagen. I guess if you can find an elementary antiderivative, then assuming you can take a limit to infinity (is that an assumption or can we always take limits to infinity of elementary functions?) you can determine whether the series converges. But your example shows that it doesn't work the other way. –  Martin Leslie Nov 7 '12 at 17:08

## 1 Answer

If such an algorithm would exist at the moment then we will know whether the series $$\sum\limits_{n=1}^\infty\frac{1}{n^3\sin^2 n}$$ converges. But it is not, for details see this answer.

-
This only rules out currently practical algorithms. –  hjg Nov 7 '12 at 17:30
This is pretty amazing! That certainly convinces me that there isn't a known algorithm. Also in the linked answer is an example of a sequence whose convergence is unknown which answers a question in the comments to the main question. –  Martin Leslie Nov 7 '12 at 18:06
@Norbert, you should write out $\sin^2 n$ just to avoid the series being understood as $\sin(n^2)$ –  Jean-Sébastien Nov 7 '12 at 18:10
@Jean-Sébastien, thanks! –  userNaN Nov 7 '12 at 18:34