MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have a sequence $a_n$ given by some combinatorial formula, e.g. involving a sum of n terms (like ${n \choose k}^{10}3^{-k}$ etc.). Sometimes it is plausible that there is no compact formula for the $a_n$, where one has to adopt a reasonable definition of "compact" (i.e. using a constant, independent of $n$, number of primitive operations). Are there any methods of proving that a certain sequence $a_n$ has no compact formula, in much the same way differential Galois theory allows one to prove that certain integrals are nonelementary? Of course this would relative the choice of "computational primitives" (factorial, ${n \choose k}$ etc.)

share|cite|improve this question
up vote 14 down vote accepted

Yes, there are. See the book A=B by Petkovsek, Wilf, and Zeilberger. I will quote from it:

[Petk91] is the Ph.D. thesis of Marko Petkovsek, in 1991. In it he discovered the algorithm for deciding if a given recurrence with polynomial coefficients has a "simple" solution, which, together with the algorithms above, enables the automated discovery of the simple evaluation of a given definite sum, if one exists, or a proof of nonexistence, if none exists (see Chapter 8). A definite hypergeometric sum is one of the form $f(n) = \sum_{k=-\infty}^\infty > F(k,n)$, where $F$ is hypergeometric.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.