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


  • $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?
  • $\begingroup$ 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? $\endgroup$ – Eric Tressler Oct 2 '15 at 21:47
  • $\begingroup$ @EricTressler, strictly inside the radius of convergence would do it. $\endgroup$ – Will Jagy Oct 2 '15 at 22:29

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.

  • 1
    $\begingroup$ You beat my by a pinch! $\endgroup$ – dafinguzman Oct 2 '15 at 21:51
  • $\begingroup$ We also assume that at $x_0$ the sum converges absolutely, otherwise it is a delicate matter. $\endgroup$ – Almentoe Oct 2 '15 at 21:57
  • $\begingroup$ better to say strictly within the radius of convergence, see comments to question. I don't have the book myself. $\endgroup$ – Will Jagy Oct 2 '15 at 22:33
  • $\begingroup$ @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$. $\endgroup$ – 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).$$


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.