Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

One of the joys of high-school mathematics is summing a complicated series to get a “closed-form” expression. And of course many of us have tried summing the harmonic series $H_n =\sum \limits_{k \leq n} \frac{1}{k}$, and failed. But should we necessarily fail?

More precisely, is it known that $H_n$ cannot be written in terms of the elementary functions, say, the rational functions, $\exp(x)$ and $\ln x$? If so, how is such a theorem proved?

Note. When I started writing the question, I was going to ask if it is known that the harmonic function cannot be represented simply as a rational function? But this is easy to see, since $H_n$ grows like $\ln n+O(1)$, whereas no rational function grows logarithmically.

Added note: This earlier question asks a similar question for “elementary integration”. I guess I am asking if there is an analogous theory of “elementary summation”.

share|improve this question
1  
So what is the question? –  Ross Millikan Jul 20 '11 at 5:07
6  
Ross, the second paragraph explicitly and directly states the question. If the first paragraph is too verbose, I can trim it a bit. –  Srivatsan Jul 20 '11 at 5:25
4  
There is an expression which might loosely be called "closed form": $H_n = \Psi(n+1) + \gamma$, where $\Psi$ is the "digamma" function $\Psi(x) = \frac{d}{dx} \ln \Gamma(x)$. I don't know how to prove that $\Psi$, or $\Gamma$ for that matter, is not elementary. –  Robert Israel Jul 20 '11 at 5:58
    
In addition to $\Psi$, I am not sure if using everyone will agree with using constant $\gamma$ which itself doesn't have a nice form. But I am ok with it. (After all, I did allow $e$!) –  Srivatsan Jul 20 '11 at 6:12
2  
FWIW, I consider harmonic numbers as closed forms in themselves, just as I consider $n!$ to be the closed form for $\prod_{k=1}^n k$ and $(a)_n$ to be the closed form of $\prod_{k=0}^{n-1} (a+k)$... –  J. M. Jul 20 '11 at 11:19

3 Answers 3

up vote 15 down vote accepted

There is a theory of elementary summation; the phrase generally used is "summation in finite terms." An important reference is Michael Karr, Summation in finite terms, Journal of the Association for Computing Machinery 28 (1981) 305-350. Quoting,

This paper describes techniques which greatly broaden the scope of what is meant by 'finite terms'...these methods will show that the following sums have no formula as a rational function of $n$: $$\sum_{i=1}^n{1\over i},\quad \sum_{i=1}^n{1\over i^2},\quad \sum_{i=1}^n{2^i\over i},\quad \sum_{i=1}^ni!$$

Undoubtedly the particular problem of $H_n$ goes back well before 1981. The references in Karr's paper may be of some help here.

share|improve this answer
4  
For lazy people like me... –  J. M. Jul 20 '11 at 11:20
1  
There is also this paper: Michael Karr, "Theory of summation in finite terms", Journal of Symbolic Computation 1 (1985), no. 3, 303–315. MR0849038 (89a:12016) –  lhf Jul 21 '11 at 22:10

This is probably not what you were looking for (since it isn't in terms of rational or elementary functions), but for the harmonic numbers we have

$$H_n=\frac{1}{n!}\left[{n+1 \atop 2}\right]$$

where $\left[{n \atop k}\right]$ are the (unsigned) Stirling numbers of the first kind (page 261 from the book Concrete Mathematics by Graham, Knuth and Patashnik - second edition).

For the generalized harmonic numbers I like this formula - even though it does involve an integral and Riemann zeta...

Maybe you prefer this

share|improve this answer
    
Minor formatting note: on this site, it is preferable to use asterisks to set text in italics (*like this*), instead of using \textit inside math mode. –  Rahul Jul 20 '11 at 10:38
    
thanks that's more convenient - i should have read the help before... sorry about that –  Peter Sheldrick Jul 20 '11 at 10:44

Harmonic numbers can be represented in terms of integrals of elementary functions: $$H_n=\frac{\int_0^{\infty} x^n e^{-x} \log x \; dx}{\int_0^{\infty} x^n e^{-x} dx}-\int_0^{\infty} e^{-x} \log x \; dx.$$ This formula could also be used to generalize harmonic numbers to fractional or even complex arguments. These generalized harmonic numbers retain some of their useful properties, for example, $$H_z=H_{z-1}+\frac{1}{z}.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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