TAOCP 1.2.7 Exercise 6

We wish to prove that H_n = \frac{\left[{\,n+1 \atop 2\,}\right]}{n!

taocpmathematicsalgorithmsvolume-1math-simple

Section 1.2.7: Harmonic Numbers

Exercise 6. [M15] Prove that the harmonic numbers are directly related to Stirling's numbers, which were introduced in the previous section; in fact,

$$ H_n = \left[{n+1 \atop 2}\right] / n!. $$

Verified: no
Solve time: -

Solution

We wish to prove that

$$ H_n = \frac{\left[{,n+1 \atop 2,}\right]}{n!}, $$

where $\left[{n \atop k}\right]$ denotes the Stirling numbers of the first kind, as defined in Section 1.2.6.

Recall that the Stirling numbers of the first kind satisfy the recurrence

$$ \left[{n \atop k}\right] = \left[{n-1 \atop k-1}\right] + (n-1)\left[{n-1 \atop k}\right], \tag{1.2.6, 6} $$

with initial conditions $\left[{0 \atop 0}\right]=1$ and $\left[{n \atop 0}\right]=0$ for $n>0$.

Consider $\left[{n+1 \atop 2}\right]$. By the recurrence, we have

$$ \left[{n+1 \atop 2}\right] = \left[{n \atop 1}\right] + n \left[{n \atop 2}\right]. $$

Dividing both sides by $(n+1)!$ gives

$$ \frac{\left[{n+1 \atop 2}\right]}{(n+1)!} = \frac{\left[{n \atop 1}\right]}{(n+1)!} + \frac{n \left[{n \atop 2}\right]}{(n+1)!}. $$

Simplifying the fractions yields

$$ \frac{\left[{n+1 \atop 2}\right]}{(n+1)!} = \frac{\left[{n \atop 1}\right]}{(n+1)!} + \frac{\left[{n \atop 2}\right]}{(n)!} \cdot \frac{n}{n+1} = \frac{\left[{n \atop 1}\right]}{(n+1)!} + \frac{1}{n+1} \frac{\left[{n \atop 2}\right]}{n!}. $$

From Section 1.2.6, we have $\left[{n \atop 1}\right] = (n-1)!$. Substituting this gives

$$ \frac{\left[{n+1 \atop 2}\right]}{(n+1)!} = \frac{(n-1)!}{(n+1)!} + \frac{1}{n+1}\frac{\left[{n \atop 2}\right]}{n!} = \frac{1}{n(n+1)} + \frac{1}{n+1}\frac{\left[{n \atop 2}\right]}{n!}. $$

Multiplying both sides by $n+1$ yields

$$ \frac{\left[{n+1 \atop 2}\right]}{n!} = \frac{1}{n} + \frac{\left[{n \atop 2}\right]}{n!}. $$

Define $h_n = \frac{\left[{n+1 \atop 2}\right]}{n!}$. Then the previous equation becomes

$$ h_n = \frac{1}{n} + h_{n-1}, \quad n \ge 2, $$

with initial value $h_1 = \frac{\left[{2 \atop 2}\right]}{1!} = 1$ (since $\left[{2 \atop 2}\right]=1$). This recurrence is precisely the defining recurrence for harmonic numbers:

$$ H_n = H_{n-1} + \frac{1}{n}, \quad H_1 = 1. $$

By induction on $n$, $h_n = H_n$ for all $n \ge 1$. Hence

$$ H_n = \frac{\left[{n+1 \atop 2}\right]}{n!}. $$

This completes the proof.

∎