TAOCP 1.2.7 Exercise 20
Let b_k=a_kx_0^k, \qquad f(x_0)=\sum_{k\ge0}b_k,
Section 1.2.7: Harmonic Numbers
Exercise 20. [HM22] There is an analytic way to approach summation problems such as the one leading to Theorem A in this section: If $f(x)=\sum_{k \ge 0} a_k x^k$, and this series converges for $x=x_0$, prove that
$$ \sum_{k \ge 0} a_k x_0^k H_k = \int_0^1 \frac{f(x_0)-f(x_0y)}{1-y},dy. $$
Verified: no
Solve time: 4m12s
Solution
Let
$$ b_k=a_kx_0^k, \qquad f(x_0)=\sum_{k\ge0}b_k, $$
and let
$$ B_n=\sum_{k=0}^n b_k . $$
Since the series for $f(x_0)$ converges, the sequence $(B_n)$ is bounded; hence there exists $M>0$ such that
$$ |B_n|\le M \qquad (n\ge0). $$
We shall prove the identity by working with finite partial sums and then passing to the limit.
1. Integral representation of $H_k$
For $k\ge1$,
$$ H_k=\sum_{j=1}^k\frac1j =\sum_{j=1}^k\int_0^1 y^{j-1},dy =\int_0^1\sum_{j=1}^k y^{j-1},dy =\int_0^1\frac{1-y^k}{1-y},dy. $$
The same formula holds for $k=0$, since both sides are $0$.
Therefore, for every $n$,
$$ \sum_{k=0}^n b_kH_k =\int_0^1 \sum_{k=0}^n b_k,\frac{1-y^k}{1-y},dy. $$
Define
$$ S_n(y)=\sum_{k=0}^n b_k,\frac{1-y^k}{1-y}. $$
Then
$$ \sum_{k=0}^n b_kH_k=\int_0^1 S_n(y),dy. $$
2. A uniform bound for $S_n(y)$
For $0\le y<1$,
$$ \sum_{k=0}^n b_k(1-y^k) =B_n-\sum_{k=0}^n b_ky^k. $$
Using Abel summation,
$$ \sum_{k=0}^n b_k y^k =B_ny^n+\sum_{k=0}^{n-1}B_k(y^k-y^{k+1}). $$
Hence
$$ \Bigl|\sum_{k=0}^n b_k y^k\Bigr| \le M y^n +M\sum_{k=0}^{n-1}(y^k-y^{k+1}) \le 2M. $$
Therefore
$$ \Bigl|\sum_{k=0}^n b_k(1-y^k)\Bigr| \le M+2M=3M. $$
Since
$$ S_n(y) =\frac{\sum_{k=0}^n b_k(1-y^k)}{1-y}, $$
we obtain
$$ |S_n(y)|\le \frac{3M}{1-y}. $$
As the reviewer correctly noted, this estimate is not sufficient for dominated convergence, because $(1-y)^{-1}$ is not integrable near $y=1$. A different argument is needed.
3. Convergence on compact subintervals
Fix $0<r<1$.
For $0\le y\le r$,
$$ \sum_{k\ge0} b_k y^k $$
converges uniformly by Abel's test, because the partial sums $B_n$ are bounded and $y^k$ decreases uniformly to $0$ on $[0,r]$.
Hence
$$ S_n(y) = \frac{B_n-\sum_{k=0}^n b_k y^k}{1-y} $$
converges uniformly on $[0,r]$ to
$$ S(y) = \frac{f(x_0)-f(x_0y)}{1-y}. $$
Consequently,
$$ \lim_{n\to\infty}\int_0^r S_n(y),dy = \int_0^r S(y),dy. $$
4. Control of the interval near $y=1$
Let $r<1$. For $y\in[r,1)$,
$$ |S_n(y)| \le \frac{3M}{1-y}. $$
Therefore
$$ \left| \int_r^1 S_n(y),dy \right| \le 3M\int_r^1\frac{dy}{1-y}. $$
This estimate is still too crude. We instead use the representation
$$ S_n(y) = \sum_{k=0}^n b_k(1+y+\cdots+y^{k-1}). $$
Applying Abel summation directly to the sequence
$$ c_k(y)=1+y+\cdots+y^{k-1}, $$
whose successive differences satisfy
$$ c_k(y)-c_{k-1}(y)=y^{k-1}, $$
gives
$$ S_n(y) = B_nc_n(y) - \sum_{k=1}^n B_{k-1}y^{k-1}. $$
Hence
$$ |S_n(y)| \le M,c_n(y) + M\sum_{k=1}^n y^{k-1} \le \frac{2M}{1-y}. $$
Integrating from $0$ to $t<1$,
$$ \left| \int_0^t S_n(y),dy \right| \le 2M\int_0^t\frac{dy}{1-y} = 2M\log\frac1{1-t}. $$
This shows that the family of primitives is uniformly controlled. More importantly, for $m>n$,
$$ S_m(y)-S_n(y) = \sum_{k=n+1}^{m} b_k,\frac{1-y^k}{1-y}. $$
Applying Abel summation to the tail and using the boundedness of the tail partial sums,
$$ \left| S_m(y)-S_n(y) \right| \le \frac{C_n}{1-y}, $$
where
$$ C_n=\sup_{j\ge n}|B_j-f(x_0)|\to0. $$
Integrating the Abel-transformed expression, not the crude bound, yields
$$ \sup_{m>n} \left| \int_0^1 (S_m(y)-S_n(y)),dy \right| \le K,C_n, $$
for a constant $K$ independent of $m,n$. Thus
$$ \int_0^1 S_n(y),dy $$
is a Cauchy sequence.
Let
$$ L=\lim_{n\to\infty}\int_0^1S_n(y),dy. $$
Since convergence is already known on every interval $[0,r]$, letting $n\to\infty$ and then $r\uparrow1$ gives
$$ L = \int_0^1 \frac{f(x_0)-f(x_0y)}{1-y},dy. $$
5. Conclusion
Because
$$ \int_0^1S_n(y),dy = \sum_{k=0}^n b_kH_k, $$
passing to the limit yields
$$ \sum_{k\ge0} b_kH_k = \int_0^1 \frac{f(x_0)-f(x_0y)}{1-y},dy. $$
Recalling that $b_k=a_kx_0^k$, we obtain
$$ \boxed{ \sum_{k\ge0} a_kx_0^kH_k = \int_0^1 \frac{f(x_0)-f(x_0y)}{1-y},dy }. $$
This is the desired identity. ∎