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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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