## Harmonic Numbers and Stirling Numbers

This post will present three proofs of the following representation of harmonic numbers in terms of Stirling cycle numbers (or unsigned Stirling numbers of the first kind): $\displaystyle H_n = \frac{1}{n!} \left[n + 1 \atop 2 \right].$  Each proof uses a different property of the Stirling numbers.

Proof 1: Stirling cycle numbers convert rising factorial powers to normal powers via $x^{\overline{n}} = \sum_{k=0}^n \left[n \atop k\right] x^k$.

Start with the product $\displaystyle \prod_{k=1}^n \left(x + \frac{1}{k}\right) = \frac{x^{n+1}}{n!} \prod_{k=0}^n \left(\frac{1}{x} + k \right).$

Then, let $y = 1/x$.  We get
$\displaystyle \prod_{k=0}^n \left(\frac{1}{x} + k\right) = \prod_{k=0}^n (y+k) = y^{\overline{n+1}} = \sum_{k=0}^{n+1} \left[n +1 \atop k\right]y^k.$

Thus $\displaystyle \prod_{k=1}^n \left(x + \frac{1}{k}\right) = \frac{1}{n!} \sum_{k=0}^{n+1} \left[n +1 \atop k\right] x^{n+1-k}.$

Now, look at the coefficient of $x^{n-1}$ in both expressions.  On the left-hand side we have $\sum_{k=1}^n \frac{1}{k} = H_n$, and on the right we have $\frac{1}{n!} \left[n +1 \atop 2\right]$, yielding $\displaystyle H_n = \frac{1}{n!} \left[n + 1 \atop 2 \right].$

(This is a slight modification of this answer of mine on math.SE.  And, of course, this proof yields formulas for the other Stirling cycle numbers, too.)

Proof 2: Stirling cycle numbers satisfy the recurrence $\left[n \atop k\right] = (n-1)\left[n-1 \atop k\right] + \left[n-1 \atop k-1\right]$.

From the recurrence we get $\displaystyle \left[n+1 \atop 2\right] = n\left[n \atop 2\right] + \left[n \atop 1\right] = n\left[n \atop 2\right] + (n-1)!,$ as long as $n > 0$.  Divide both sides by $n!$, and we have $\displaystyle \frac{1}{n!} \left[n+1 \atop 2 \right] = \frac{1}{(n-1)!} \left[n \atop 2 \right] + \frac{1}{n}.$

Let $A_n = \frac{1}{n!}\left[n+1 \atop 2\right]$.  Then the recurrence is $A_n = A_{n-1} + \frac{1}{n}$, with $A_1 = 1$.  The solution is clearly $H_n$, and so we have, again, $\displaystyle H_n = \frac{1}{n!} \left[n + 1 \atop 2 \right].$

(This proof appears in Concrete Mathematics [2], p. 275.)

Proof 3: Stirling cycle numbers $\left[n \atop k\right]$ count the number of ways to permute $n$ objects into $k$ disjoint cycles.

By definition, the number of permutations of $n+1$ objects into 2 cycles is $\left[n+1 \atop 2\right]$.

For another way, suppose there are $k$ elements in the cycle that does not contain 1.  There are $\binom{n}{k}$ ways to choose these elements, $(k-1)!$ ways to permute them into a cycle, and $(n-k)!$ ways to permute the remaining elements into the other cycle.  Thus there are $\displaystyle \sum_{k=1}^n \binom{n}{k} (k-1)! (n-k)! = n! \sum_{k=1}^n \frac{1}{k} = n! H_n$ permutations of $n+1$ objects into 2 cycles.

Thus we get, once again, $\displaystyle H_n = \frac{1}{n!} \left[n + 1 \atop 2 \right].$

(This proof appears in Proofs that Really Count [3], p. 97.)

References

1. Arthur T. Benjamin and Jennifer J. Quinn, Proofs that Really Count, MAA, 2003.
2. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.