16
$\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 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.)

$\endgroup$
  • $\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$ – Martin Sleziak Apr 15 '16 at 9:59
  • $\begingroup$ Maybe relevant: en.wikipedia.org/wiki/Gosper's_algorithm. (Doesn't work for any elementary function $f$, though, only for hypergeometric terms.) $\endgroup$ – Hans Lundmark Apr 15 '16 at 10:29
  • $\begingroup$ By the way, you probably mean $\sum_k f(k)$, not $\sum_k f(n)$. ;-) $\endgroup$ – Hans Lundmark Apr 15 '16 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$ – Martin Sleziak Apr 15 '16 at 10:34
1
$\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$
0
$\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

And there is a theory or an algorithm of Carsten Schneider:

Look for

Schneider Summation

and for

Schneider sums

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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