# Inexpressibility of certain coefficients and discrete versions of Hölder's theorem

In an answer to a recent question, I noted that there were probably no explicit formulas for Stirling numbers (of the first kind, specifically) and speculated that this might be coupled to a sort of discrete version of Hölder's theorem that the Gamma function doesn't satisfy any algebraic differential equation. This got me wondering whether anything is known about 'closed-form inexpressibility' of certain coefficients such as Stirling numbers or partition numbers, and what discrete analogues to Hölder's theorem there might be.

There's one straightforward, obvious one:

The sequence $s_n = n!$ does not satisfy any linear homogeneous recurrence relation with constant coefficients $\sum_{i=0}^k a_i s_{n-i} = 0$.
(The simplest proof goes through order-of-growth arguments, since the solutions of any such recurrence relation are of the form $\sum_{i,j\lt k} c_{ij}n^i\alpha_j^n$ for some sets of constants $c_{ij}$ and $\alpha_j$, but the factorial grows essentially faster than any exponential of fixed base.)

Anything much beyond this, of course, requires some sense of what 'explicit formula' means - for instance, Ken Ono's recent formula for the partition numbers gives a means of computing them, but seems difficult if not impossible to convert to something like a simple 'sum-of-binomials' form; on the other hand, the Bernoulli numbers are known to have relatively simple forms such as $\displaystyle{B_m=\sum_{k=0}^m\sum_{v=0}^k(-1)^v{k\choose v}\frac{v^m}{k+1}}$.

It seems like it would be possible to do something like define a '$\Sigma_0$ closed-form' formula in some set of variables $m, n, \ldots$ as a rational function of the variables themselves and expressions like $f(m)^{g(n)}, {f(m,n)\choose g(m,n)}, f(m,n)!$, etc, where $f$ and $g$ can probably be restricted to be linear functions; then one can get '$\Sigma_k$ formulas' by 'summing out' $k$ of the indices in some fashion. For instance, a $\Sigma_1$ formula in $n$ would be of the form $\sum_{m=f(n)}^{g(n)}s(m,n)$ where $s(m,n)$ is a $\Sigma_0$ formula in $m$ and $n$.

Obviously there's a lot of generatingfunctionology in working with these sorts of formulas and I know that hypergeometric series and WZ pairs provide a means for proving identities involving them; it seems as though hypergeometric series can also be used 'in converse' for showing that certain expressions can't be of an appropriate form. I'm looking for pointers in general for any further results along these lines, in particular using characteristics of generating functions to show that certain expressions can't be of certain forms, but any related results would be welcome!

-