# 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

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! – Norbert Nov 7 '12 at 18:34

There are multiple algorithms, but let's use one that might interest you -- the ratio test.

The ratio test doesn't require using your series to determine convergence -- it depends on one limit. Let's let $f(n)$ be an "arbitrary" function and let $a_n = f(n) \ \forall \ \mathbb N$ (which was already defined in the question you asked, so I am sorry for duplicating that). The ratio test states that $\forall \ n, n \neq 0$, the following rules apply (recited from another website I credit):

Let's define $L$ to be: $$\lim_{n \to \infty} |\frac {a_{n + 1}}{a_n}|$$ If $L < 1$, then the series converges. If $L > 1$, then the series diverges. If $L = 1$, the test is inconclusive (which partly answers your second question).

The ratio test is undecidable for $L = 1$ (as I already stated). The root test also is undecidable for $L = 1$, but $L$ is equal to: $$\lim_{n \to \infty} |a_n|^{\frac 1n}$$ Hopefully this may help you.

References:

-
This does not exactly answer the question. We know that there are several tests, but the question really is given any random series, is here an algorithm to find out. – Shailesh Feb 4 at 2:11
I believe I answered the question well. The author of the question can apply these tests to the series (or will that not work?). – Obinna Nwakwue Feb 12 at 0:06