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.
Advertisements
This entry was posted in combinatorics, sequences and series. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s