Main Index Mathematical Analysis Mathematical Constants
  Subject Index
comment on the page

Harmonic number

The typeset structureth harmonic number typeset structure is defined as the truncation of the harmonic series after the typeset structureth term

H _ n = Underoverscript[∑, k = 1, arg3] 1/k,           n ϵ N .

The first ten harmonic numbers are:

typeset structure.

To compute more harmonic numbers visit .

typeset structureis integral only for typeset structure [1] .

To see the first statement note that the greatest power of  2  not exceeding typeset structure do not divide any other term if typeset structure. Therefore the numerator of typeset structure must be odd while the denominator is even.  In other words, the denominator of typeset structure is a multiple of  typeset structure where  typeset structure is determined by relations typeset structure.

L.Kürschák [2]  proved more: the difference between two distinct harmonic numbers is never an integer.  He proved this in the form that typeset structurewith typeset structure is never an integer.

T.Nagell  [3]  proved  that even  typeset structure, typeset structure, cannot be an integer. This result was later reproved by P.Erdõs [4] .

The Bertrand postulate says that for every positive integer typeset structure there is a prime typeset structure such that typeset structure. Consequently, if typeset structure the denominator of typeset structure is divisible by at least one odd prime. As we saw above, the denominator of typeset structure is divisible by the largest power of 2 less or equal to typeset structure. Consequently, typeset structure is the only harmonic number with a prime denominator.    

An analogous question for which typeset structure the numerator of typeset structure is a prime number is more delicate. The first 10 values of typeset structure are   (for more details visit ):

H _ 2 = 3/2, H _ 3 = 11/6, H _ 5 = 137/60, H _ 8 = 761/280, H _ 9 = 7129/2520, H _ 21 = 188580 ... 654789/54749786241679275146400, H _ 62 = 928551009361054917576341971/197044480683803711251893600 .

L.Theisinger  [1]  also proved that

H _ n = 1/(1 !    2 !    3 ! ...    n !) | ... 2 3 ··· n(1)

A combinatorial interpretation of harmonic numbers says that ( [5] , p.275 )

H _ n = [(n + 1)/2]/n ! ,(2)

where  typeset structure  denotes the unsigned Stirling number of the first kind, counting the permutation of typeset structure elements that are product of typeset structure disjoint cycles.

Euler found the following integral representation

H _ n = ∫ _ 0^1 (1 - x^n)/(1 - x) d x .(3)

It can be shown using the integral comparison criterion applied to the function  typeset structure for typeset structure that

ln n + 1/n < H _ n < ln n + 1.(4)

This implies that typeset structure, and that typeset structure, that is that typeset structure grows about as fast (or better as slowly)  as typeset structure. Actually more can be shown. Using the fact that typeset structure converges in the infinite product typeset structure there follows that there exists a non-vanishing finite limit

lim _ (n -> ∞) e^H _ n/n,(5)

say typeset structure. Clearly typeset structure. Consequently there exists also the limit

lim _ (n -> ∞) (H _ n - ln n) = ln c = γ .(6)

The constant typeset structure is the Euler-Mascheroni constant .  To see this we can use Euler’s summation formula which gives that

H _ n = ln n + γ + 1/(2 n) - Underoverscript[∑, k = 1, arg3] B _ (2 k)/(2 k n^(2 k ... + 2) n^(2 m + 2)),          ϵ(m, n) ∈ (0, 1),(7)

where typeset structure stands for the typeset structureth Bernoulli number. This formula can be used in several ways:

For instance if typeset structure we get that typeset structurewithout adding up 1000 unit fractions.

Last statement can be extended also in the following form: typeset structure is monotone increasing and converges to typeset structure. Since  

1/(n + 1) < Underoverscript[∫, n, arg3] 1/x d x < 1/n,

we have

H _ (k n) - H _ (n + a) < Underoverscript[∫, n + a, arg3] 1/x d x < H _ (k n - 1) - H _ (n + a - 1) = H _ (k n) - 1/(k n) - (H _ (n + a) - 1/(n + a)) .

Moreover

Underoverscript[∫, n + a, arg3] 1/x d x = Underoverscript[∫, 1 + a/n, arg3] 1/y d y = ln k - ln(1 + a/n)

using the substitution typeset structure.

Graphical representation of values (red points) of typeset structure and their asymptotic curve (blue line) typeset structure

[Graphics:HTMLFiles/HarmonicNumber_74.gif]

A generating function for harmonic numbers is

Underoverscript[∑, n = 1, arg3] H _ n z^n = -ln(1 - z)/(1 - z) .(8)

If typeset structure denotes the number of divisors of an integer typeset structure then

H _ n < 1 + 1/n Underoverscript[∑, i = 1, arg3] τ(n)      for     n >= 2 .

In the following graph the harmonic numbers are represented by red points and the values of right hand side by blue points

[Graphics:HTMLFiles/HarmonicNumber_80.gif]

J.C.Lagarias [6]  proved an interesting link to the Riemann hypothesis. He proved that the problem of showing that

Underscript[∑, d | n] d <= H _ n + e^H _ n log H _ n(9)

for all typeset structurewith equality only for typeset structure, is equivalent to the Riemann Hypothesis.  The proof uses two bounds for the sums-of-divisors function typeset structure proved by G. Robin [7] . One of the inequalities says that the inequality typeset structure for typeset structure is equivalent with Riemann hypotheses (Robin also showed that one can take typeset structure).

In the graph the blue points represent the sum-of-divisors functions and the red ones the values of the right hand side of (9)

[Graphics:HTMLFiles/HarmonicNumber_89.gif]

For the first multiples of 12  we have

n 12 24 36 48 60 LHS 28 60 91 124 168 RHS 28.3218 61.7575 97.0761 133.592 170.977

It is possible to extend the above definition of a harmonic number also to non-integral values of typeset structure using the observation that

Underscript[∑, k >= 1] (1/k - 1/(k + z))(10)

converges for all complex values of typeset structure, except when typeset structure is a negative number. If typeset structure denotes the value of the series, then when typeset structure is a positive integer typeset structure we get typeset structure.

Wolstenholme's Theorem: If typeset structure is a prime, then  [8]

An interesting problem in which solution harmonic numbers unexpectedly occur was discovered by R.T.Sharp [9] [10] :  determine how far an overhang we can achieve by stacking dominoes over the table edge, accounting for the force of gravity.

The center of gravity is a geometric property of any object and it is the point where all the weight of the object can be considered to be concentrated. In other words, it is defined as the average location of the weight of an object. Thus the radiusvector typeset structure of the center of a system of particles is the average of the positions typeset structure of center of the typeset structureth particle weighted by its mass typeset structure

Overscript[R, ->] = (m _ 1 Overscript[r, ->] _ 1 + m _ 2 Overscript[r, ->] _ 2 + ...)/(m _ 1 + m _ 2 + ...) .(11)

Since we shall suppose that edges of the cards are parallel to the edge of the table, we shall only work with the typeset structure-coordinate. Let typeset structure be the shift distance of the extreme edge of the typeset structureth domino to the corresponding edge of the typeset structurest domino piece counting from the top.     

[Graphics:HTMLFiles/HarmonicNumber_118.gif]

For the sake of simplicity suppose that length of each domino piece is 2 units, the weight is 1 unit with uniformly distributed mass along the length,, and that the pile contains typeset structure pieces. Then the typeset structure-coordinate of the center of gravity of typeset structureth piece from the top is typeset structure, typeset structure. Then the typeset structure-coordinate of the center of such complex of typeset structure superimposed domino pieces is  

c _ n = (n + d _ 1 + 2 d _ 2 + ... + (n - 1) d _ (n - 1))/n      for     n > 1,(12)

while typeset structure.

The stability criterion is that the typeset structure-coordinate of the center of gravity of pieces typeset structure must lie exactly above the right edge of piece typeset structure. Since the right edge of piece typeset structure has typeset structure-coordinate 2, we get from (12)

n = d _ 1 + 2 d _ 2 + 3 d _ 3 + ... + (n - 1) d _ (n - 1) .(13)

This implies that typeset structure for typeset structure. This implies that the total extension for block of typeset structure dominoes is typeset structure. In the following picture the typeset structureth triangle shaped point from top always shows the position of the center of gravity of top typeset structure dominoes.   

[Graphics:HTMLFiles/HarmonicNumber_141.gif]

A bit surprising consequence of the solution is that given sufficiently large number of dominoes, arbitrary large overhangs can be achieved.

In the above way of stacking of dominoes we achieved an overhang of  typeset structure, We  stacked here all the dominoes one on top of another with the typeset structureth domino from the top displaced by  typeset structure beyond the block below. This solution is however not optimal. M.Paterson and U.Zwick  [11]  showed that it is exponentially far from optimal and gave explicit constructions with an overhang of typeset structure .

Generalized harmonic number

Generalized harmonic number typeset structure of order typeset structure is defined as truncation of  the series of reciprocals of the typeset structureth powers of positive integers

H _ (n, m) = Underoverscript[∑, k = 1, arg3] 1/k^m,           n ϵ N .

Clearly, typeset structure.

The first ten generalized harmonic numbers typeset structure are:

typeset structure

To compute more generalized harmonic numbers visit .

Comparison graph of values of typeset structure for typeset structure.

[Graphics:HTMLFiles/HarmonicNumber_156.gif]

The following identity goes back to Euler  (  [5]  , p.278 )

H _ n = 1 + ln n - 1/2 (H _ n^(2) - 1) - 1/3 (H _ n^(3) - 1) - 1/4 (H _ n^(4) - 1) - ...(14)

Similarly to  (10) we can take the series

Underscript[∑, k >= 1] (1/k^s - 1/(k + z)^s),     s ∈ Z,

to get a generalization to non-integral values of indices.

The generalized harmonic number converges to the Riemann zeta function in the following sense

lim _ (n -> ∞) H _ (n, m) = ζ(m) .

Hyperharmonic number

J.H.Conway and R.K.Guy   [12] defined the hyperharmonic numbers, the typeset structureth harmonic number of order typeset structure: typeset structure, and typeset structure for  typeset structure.

The first ten harmonic numbers of order 2 are:

n ... 2 6 12 60 20 140 280 2520 2520 2520

The first ten harmonic numbers of order 3 are:

n (2) ... 2 3 12 10 20 35 280 252 2520 420

We have  [13]

H _ n^(r) = [(n + r)/(r + 1)] _ ( r)/n ! ,(15)

where typeset structure is the number of permutations of the set typeset structure having typeset structure disjoint non-empty cycles in which the elements typeset structure are restricted to appear in different cycles (the so-called typeset structure-Stirling numbers  [14] , where  typeset structure ),  or   [12]  

H _ n^(r) = ((n + r - 1)/(r - 1)) (H _ (n + r - 1) - H _ (r - 1)) . (16)

To compute more hyperharmonic numbers visit .

References

[1]  Theisinger, L. (1915). Bemerkung über die harmonische Reihe. (German). Monatsh. f. math., 26, 132-134.

[2]  Kürschák, J. (1918). Über die harmonische Reihe. (Hungarian). Math. és phys. lapok, 27, 299-300.

[3]  Nagell, T. (1923 (1924)). Eine Eigenschaft gewisser Summen. Skr. Norske Vid. Akad. Kristiania, I(13), 10-15.

[4]  Erdõs, P. (1932). Generalization of an elementary number-theoretic theorem of Kürschák (Hungarian). Mat. Fiz. Lapok, 39, 17-24.

[5]  Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete mathematics: a foundation for computer science (2nd ed.). Amsterdam: Addison-Wesley Publishing Group.

[6]  Lagarias, J. C. (2002). An elementary problem equivalent to the Riemann hypothesis. Amer. Math. Montly, 109(6), 534-543.

[7]  Robin, G. (1984). Grandes valeurs de la fonction somme des diviseurs et hypothèse de Riemann. J. Math. Pures Appl., IX. Sér. 63, 187-213.

[8]  Wolstenholme, J. (1862). On certain properties of prime numbers. Quarterly Journal of Mathematics, 5, 35-39.

[9]  Sharp, R. T. (1954). Problem 52: Overhanging dominoes. Pi Mu Epsilon Journal, 1(10), 411-412.

[10]  Trigg, C. W. (1954). Problem 52: Overhanging dominoes, (proposer: R. T. Sharp). Pi Mu Epsilon Journal, 1(10), 411-412.

[11]  Paterson, M., & Zwick, U. (2006). Overhang. In: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (pp. 231-240). New York: ACM.

[12]  Conway, J. H., & Guy, R. K. (1996). The Book of Numbers. Berlin: Springer Verlag.

[13]  Benjamin, A. T., Gaebler, D., & Gaebler, R. (2003). A combinatorial approach to hyperharmonic numbers. Integers, 3, Paper A15.

[14]  Broder, A. Z. (1984). The r-Stirling numbers. Discrete Math., 49, 241-259.

Cite this web-page as:

Štefan Porubský: Harmonic Number.

Page created  , and updated .