# A statement about harmonic numbers from Knuth's The Art of Computer Programming

The following problem is from:

D. E. Knuth.: The Art of Computer Programming. Vol. 1., Third Edition, at page 79, Exercise 20.

If $f(x) = \sum_{n=0}^\infty a_n x^n$, and this series converges for $x=x_0$, then $$\sum_{n=0}^\infty a_n x_0^n H_n = \int_0^1 \frac{f(x_0)-f(x_0t)}{1-t}dt,$$ where $H_n$ is the $n$-th harmonic number, given by: $$H_n = \sum_{k=1}^n \frac{1}{k}.$$

Questions.

• $1^{\text{st}}$ question: Is there a name of this statement, or any authoritative reference for this theorem?
• $2^{\text{nd}}$ question: How could we prove the statement?
• $3^{\text{rd}}$ question: Are there any generalization of the statement for the $H_n^{(m)}$ generalized harmonic numbers? Or at least for $H_n^{(2)}$? Here $H_n^{(m)}$ is given by: $$H_n^{(m)} = \sum_{k=1}^n \frac{1}{k^m}.$$ Maybe this formula could be a start point for the generalization?
• Let $x_0 = 1$ and $a_n = 1/(n (\ln n)^2)$. Then $\sum a_n$ converges, but $\sum a_nH_n \sim \sum 1/(n \ln n)$ does not. Am I missing something, or is there a missing condition? – Eric Tressler Oct 2 '15 at 21:47
• @EricTressler, strictly inside the radius of convergence would do it. – Will Jagy Oct 2 '15 at 22:29

## 3 Answers

This is based on the following formula for the harmonic numbers: $$H_n = \int_0^1 \frac{1-t^{n}}{1-t} \, dt$$ Why is this true? In the integer case, we can just remember the identity $$1-t^{n} = (1-t)(1+t+t^2+\dotsb+t^{n-1});$$ then the integral is $$\int_0^1 \sum_{k=1}^{n} t^{k-1} \, dt = \sum_{k=1}^n \int_0^1 t^{k-1} \, dt = \sum_{k=1}^n \frac{1}{k} = H_n.$$

Okay, that's the easy part. The sum now holds as a formal identity if we equate the coefficients of $x_0^n$: $$a_n H_n x_0^n = \int_0^1 \frac{a_n x_0^n-a_n x_0^n t^{n}}{1-t} \, dt.$$

As for convergence: if $x_0$ is strictly within the radius of convergence, the ratio test implies that $\lvert x_0 a_{n+1}/a_n \rvert<1$. Since $H_n \sim \log{n}$, $H_{n+1}/H_n \to 1$, and so the ratio test implies that the sum converges (and is bounded by a geometric series, which is good enough to swap the sum and the integral). If $x_0$ is on the circle of convergence, this is not true in general, as pointed out in the comments.

Now, for generalisation. The key integral is $$\frac{1}{\Gamma(m)}\int_0^1 \frac{1-t^n}{1-t}(-\log{t})^{m-1} \, dt,$$ which looks quite nasty until you notice that it is a sum of terms that look like $$\int_0^1 t^{k-1}(-\log{t})^{m-1} \, dt,$$ and if you set $u=-k\log{t}$, you find that this is just $k^{-m}\Gamma(m)$. Hence the integral just comes out as $$\frac{1}{\Gamma(m)}\int_0^1 \frac{1-t^n}{1-t}(-\log{t})^{m-1} \, dt = \sum_{k=1}^n \frac{1}{k^m} = H_n^{(m)}.$$ Then, doing all sorts of manipulations that absolute convergence would justify (Dominated Convergence Theorem and so on), $$\sum_{n=0}^{\infty} a_n x_0^n H^{(m)}_n = \sum_{n=0}^{\infty} a_n x_0^n \frac{1}{\Gamma(m)}\int_0^1 \frac{1-t^n}{1-t}(-\log{t})^{m-1} \, dt \\ = \frac{1}{\Gamma(m)}\int_0^1 \frac{\sum_{n=0}^{\infty} a_n x_0^n- \sum_{n=0}^{\infty} a_n (x_0t)^n}{1-t}(-\log{t})^{m-1} \, dt \\ = \frac{1}{\Gamma(m)}\int_0^1 \frac{f(x_0)-f(x_0 t)}{1-t}(-\log{t})^{m-1} \, dt,$$ which is a similar sort of representation to the first one. In this case, since the generalised harmonic numbers are bounded for $m>1$, it should still work on the circle of convergence.

My attempt at (2):

$$\int_0^1 \frac{f(x_0)-f(t)}{1-t}dt = \int_0^1 \frac{\sum_{n=0}^\infty a_n x_0^n - \sum_{n=0}^\infty a_n (x_0t)^n}{1-t}dt = \int_0^1 \frac{\sum_{n=0}^\infty a_n x_0^n( 1 - t^n) }{1-t}dt = \int_0^1 \sum_{n=0}^\infty a_n x_0^n\sum_{j=0}^{n-1}t^j dt = \sum_{n=0}^\infty a_n x_0^n\sum_{j=0}^{n-1} \int_0^1t^j dt = \sum_{n=0}^\infty a_n x_0^n\sum_{j=0}^{n-1}\frac{1}{j+1} = \sum_{n=0}^\infty a_n x_0^n H_n$$

I used: $(1-t)\sum_{j=0}^{n-1}t^j = 1-t^n$, so the third equals sign makes sence because the functions differ at only one point.

The sum converges (and hence the integral) because $H_n \leq n$.

I will think about generalisations now.

• You beat my by a pinch! – dafinguzman Oct 2 '15 at 21:51
• We also assume that at $x_0$ the sum converges absolutely, otherwise it is a delicate matter. – Almentoe Oct 2 '15 at 21:57
• better to say strictly within the radius of convergence, see comments to question. I don't have the book myself. – Will Jagy Oct 2 '15 at 22:33
• @WillJagy You are correct. @ All I would be interested in an example of $x_0$ not strictly in the radius of convergence of a power series, and also the sum converging absolutely at $x_0$. – Almentoe Oct 2 '15 at 23:53

To answer your second question:

Start from $\frac{f(x_0)-f(x_0t)}{1-t}$ and replace $f$ with its series representation. A little algebra yields $$\frac{\sum a_n x_0^n-\sum a_n x_0^nt^n}{1-t} =\frac{\sum a_n x_0^n(1-t^n)}{1-t} =\sum a_n x_0^n(1+t+\dots+t^{n-1}).$$ You can integrate the last expression term-by-term in $[0,1]$ to get $$\sum a_n x_0^n(1+1/2+\dots+1/n).$$