TAOCP 1.2.9 Exercise 3

Equation (18) gives the generating function for the harmonic numbers: G(z)=\sum_{n\ge0}H_nz^n =\frac{1}{1-z}\ln\frac1{1-z}.

taocpmathematicsalgorithmsvolume-1hm-medium

Section 1.2.9: Generating Functions

Exercise 3. [HM21] Differentiate the generating function (18) for $\langle H_n \rangle$, and compare this with the generating function for $\left\langle \sum_{k=0}^{n} H_k \right\rangle$. What relation can you deduce?

Verified: yes
Solve time: 5m40s

Solution

Equation (18) gives the generating function for the harmonic numbers:

$$ G(z)=\sum_{n\ge0}H_nz^n =\frac{1}{1-z}\ln\frac1{1-z}. $$

Differentiating and using the product rule,

$$ G'(z) =\frac{1}{(1-z)^2}\ln\frac1{1-z} +\frac{1}{(1-z)^2. } $$

Hence

$$ zG'(z) =\frac{z}{(1-z)^2}\ln\frac1{1-z} +\frac{z}{(1-z)^2}. \tag{1} $$

By Eq. (14),

$$ zG'(z)=\sum_{n\ge0} nH_n z^n . \tag{2} $$

Now consider the partial sums

$$ S_n=\sum_{k=0}^{n}H_k. $$

By Eq. (7), the generating function for $\langle S_n\rangle$ is

$$ \frac{1}{1-z}G(z) =\frac{1}{(1-z)^2}\ln\frac1{1-z}. \tag{3} $$

From (1) and (3),

$$ zG'(z) =z\left(\frac{1}{1-z}G(z)\right) +\frac{z}{(1-z)^2}. $$

Using Eq. (16),

$$ \frac{z}{(1-z)^2} =\sum_{n\ge1} n z^n. $$

Also, by (3),

$$ z\left(\frac{1}{1-z}G(z)\right) =\sum_{n\ge1} S_{n-1}z^n. $$

Therefore

$$ \sum_{n\ge1} nH_n z^n = \sum_{n\ge1} \bigl(S_{n-1}+n\bigr) z^n. $$

Equality of coefficients yields

$$ nH_n=S_{n-1}+n, \qquad n\ge1. $$

Since $S_{n-1}=\sum_{k=0}^{n-1}H_k$, we obtain

$$ \sum_{k=0}^{n-1}H_k=nH_n-n. $$

Replacing $n$ by $n+1$ gives

$$ \sum_{k=0}^{n}H_k=(n+1)H_{n+1}-(n+1). $$

Using $H_{n+1}=H_n+\dfrac1{n+1}$,

$$ (n+1)H_{n+1}-(n+1) =(n+1)H_n+1-(n+1) =(n+1)H_n-n. $$

Hence

$$ \boxed{\sum_{k=0}^{n}H_k=(n+1)H_n-n.} $$

This completes the proof.

∎