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): Each proof uses a different property of the Stirling numbers.
Proof 1: Stirling cycle numbers convert rising factorial powers to normal powers via .
Start with the product
Then, let . We get
Now, look at the coefficient of in both expressions. On the left-hand side we have , and on the right we have , yielding
(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 .
From the recurrence we get as long as . Divide both sides by , and we have
Let . Then the recurrence is , with . The solution is clearly , and so we have, again,
(This proof appears in Concrete Mathematics , p. 275.)
Proof 3: Stirling cycle numbers count the number of ways to permute objects into disjoint cycles.
By definition, the number of permutations of objects into 2 cycles is .
For another way, suppose there are elements in the cycle that does not contain 1. There are ways to choose these elements, ways to permute them into a cycle, and ways to permute the remaining elements into the other cycle. Thus there are permutations of objects into 2 cycles.
Thus we get, once again,
(This proof appears in Proofs that Really Count , p. 97.)
Arthur T. Benjamin and Jennifer J. Quinn, Proofs that Really Count, MAA, 2003.
- Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.