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.) 



Proving that a combinatorial sequence has no compact formula
Yes, there are. See the book *[A=B](http://www.math.upenn.edu/~wilf/Downld.html)* 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
>  coeﬃcients has a "simple" solution,
>  which, together with the algorithms
>  above, enables the automated discovery
>  of the simple evaluation of a given
>  *deﬁnite* sum, if one exists, or a proof of nonexistence, if none exists
>  (see Chapter 8). A *deﬁnite*
>  hypergeometric sum is one of the form
>  $f(n) = \sum\_{k=-\infty}^\infty
> > F(k,n)$, where $F$ is hypergeometric.
> 
> 
> 


