Are there some techniques which can be used to show that a sum "does not have a closed form"?
I am aware that there are some techniques which can be used to show that some function does not have an antiderivative expressible using elementary functions, such as Liouville's theorem. (More broadly, this falls into the area of differential Galois theory and differential algebra. Such topics were discussed also on this site, for example, here or here.
Are there some analogous results for finite sums? More precisely, suppose we have a sum $$s(n)=\sum_{k=1}^n f(k)$$ where $f$ is a given elemantary function. Are there some methods which can be used to show that $s(n)$ is not equal to an elementary function (restricted to $\mathbb N$)?
To give a specific example, let us take $f(n)=\frac1n$. Are there some methods which can be used to show that we cannot express the $n$-the harmonic number $H_n=\sum_{k=1}^n\frac1k$ as $H_n=s(n)$ for an elementary function $s(x)$? (And is such result for harmonic numbers even known?)
EDIT: Very shortly after posting this question I found this: Do harmonic numbers have a “closed-form” expression?
Which definitely answers the second part about harmonic numbers. (Gerry Myerson's answer mentions also others sums, not only $H_n$. So it can definitely be considered as an answer for this question, too. We will see whether somebody will post some additional interesting information as an answer to this question.)
Solution 1:
One source of information about this theme is the book $A= B$ by M. Petkovsek, H. Wilf and D. Zeilberger.
In section 5.6 we can read following
Question 1: Given a hypergeometric term $t_n$, how can we decide if the sum \begin{align*} s_n=\sum_{k=0}^{n}t_k \end{align*} is expressible as a linear combination of several (but a fixed number of) hypergeometric terms? For example, since $k!$ is not Gosper-summable we know that the sum \begin{align*} \sum_{k=0}^nk! \end{align*} cannot be expressed as a hypergeometric term plus a constant.
A few sections later we can read about the algorithm Hyper, which can find a spanning set for the space of closed form solutions (provided some conditions are fulfilled). But, if it returns $\emptyset$ instead, it proves this way, that a given recurrence with polynomial coefficients does not have a closed form solution. In this way, they are able to prove that many well known combinatorial sequences cannot be expressed in closed form.
In section 8 we find
Theorem 8.8.1: The following sequences cannot be expressed in closed form. That is to say, in each case the sequence cannot be exhibited as sum of a fixed (independent of $n$) number of hypergeometric terms:
The sum of the cubes of the binomial coefficients of order $n$, i.e., $\sum_k\binom{n}{k}^3$.
The number of derangements (fixed-point free permutations) of $n$ letters.
The central trinomial coefficient, i.e., the coefficient of $x^n$ in the expansion of $(1+x+x^2)^n$.
The number of involutions of $n$ letters, i.e., the number of permutations of $n$ letters whose square is the identity permutation.
The sum of the first third of the binomial coefficients, i.e., $\sum_{k=0}^n\binom{3n}{k}$.