17
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ This could be possibly considered a duplicate of the question I linked to. (In the last paragraph the OP says that they are interested also in more general problem, not only harmonic problems.) OTOH with the exception of one answer, other answer to that question only deal with $H_n$. In any case, I will leave the decision whether this should be closed as a duplicate or not to the community. $\endgroup$ Apr 15, 2016 at 9:59
  • 1
    $\begingroup$ Maybe relevant: en.wikipedia.org/wiki/Gosper's_algorithm. (Doesn't work for any elementary function $f$, though, only for hypergeometric terms.) $\endgroup$ Apr 15, 2016 at 10:29
  • $\begingroup$ By the way, you probably mean $\sum_k f(k)$, not $\sum_k f(n)$. ;-) $\endgroup$ Apr 15, 2016 at 10:30
  • $\begingroup$ Thanks for noticing that @HansLundmark. I have corrected this typo in both sums (for $s(n)$ and for $H_n$.) $\endgroup$ Apr 15, 2016 at 10:34

2 Answers 2

2
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

Look for "Hypergeometric Summation", "Summation in finite terms" and "Symbolic summation".

There are parallels to the Risch algorithm.

Read e.g. the chapter "Symbolic Summation" in Bona, Miklos: Handbook of Enumerative Combinatorics. Chapman and Hall/CRC 2015.

There is a theory or an algorithm of Michael Karr:
Karr, Michael: Summation in finite terms. J. Assoc. Comp. Mach. 28 (1981) (2)305-350
Karr, Michael: Theory of Summation in Finite Terms. J. Symbolic Computation 1 (1985) (3) 303-315
Karr's algorithm is the analogue of Risch algorithm for summation.

And there is a theory or an algorithm of Carsten Schneider:
Look for
Schneider Summation
and for
Schneider sums

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .