A harmonic number is a sum of the reciprocals of the first several positive integers. For a positive integer , the th harmonic number is
The convention is also standard. Harmonic numbers are the partial sums of the harmonic series. Although they grow without bound, their growth is slow: is approximately , where is the Euler–Mascheroni constant. They occur in analysis, number theory, combinatorics, and the analysis of random processes and algorithms.
Definition and elementary properties
The first few values are
The defining sum gives the recurrence relation
Consequently, the sequence is strictly increasing, but its successive increments decrease to zero.
Every harmonic number is a rational number. Nevertheless, is not an integer for any . To see this, let be the largest power of not exceeding , and let be the least common multiple of . In the numerator
the term is odd, while every other term is even: is the only integer at most divisible by . Thus is odd, whereas is even, so cannot be an integer.
Growth and divergence
Comparison with the integral of gives
where denotes the natural logarithm. These inequalities show both that tends to infinity and that
An elementary proof of divergence groups terms between successive powers of two:
Each inner sum contains terms, all at least , so
The lower bound increases without limit. This also illustrates why terms tending to zero do not, by themselves, guarantee convergence of an infinite series.
Euler–Mascheroni constant
The difference between and approaches the Euler–Mascheroni constant:
Its rationality or irrationality remains unknown.
A more precise asymptotic expansion is
Here the remainder is expressed using big-O notation. The expansion follows from the Euler–Maclaurin formula. It is an asymptotic expansion rather than a convergent infinite series: truncating it at a fixed order gives an approximation whose accuracy improves as increases.
Useful explicit bounds are
Identities and representations
Finite sums
Reversing the order in a finite double sum yields
Indeed, the term occurs in , so its total contribution is .
A related identity is
It follows by separating the diagonal terms from the off-diagonal terms in the square of .
Harmonic numbers also have the alternating binomial representation
where is a binomial coefficient.
Integral representation
The finite geometric series gives
For integer , the apparent singularity at is removable because
Integrating each term produces .
Generating function
The ordinary generating function is
For example, it follows by interchanging two absolutely convergent sums:
Generating functions turn many identities involving harmonic numbers into algebraic operations on power series.
Generalized harmonic numbers
The generalized harmonic number of order is
For complex , the convention is . Ordinary harmonic numbers are the case .
For real , these sums converge as increases:
where is the Riemann zeta function. In particular,
More generally, convergence holds for complex with . For real , the sums diverge to positive infinity.
When , . Negative integer orders give sums of positive integer powers, such as
Extension beyond integer indices
The digamma function , the logarithmic derivative of the gamma function, satisfies
This motivates the standard extension
It defines a meromorphic function of a complex variable, with poles at the negative integers, and preserves the recurrence
where both sides are defined. Agreement at nonnegative integers alone does not uniquely determine an extension; the digamma formula specifies the conventional one.
Applications in probability and algorithms
Harmonic numbers frequently arise when a process has successive stages with reciprocal waiting times or success probabilities.
Coupon collection
In the coupon collector problem, independent draws each produce one of equally likely coupon types. After distinct types have appeared, the probability that the next draw gives a new type is . The expected number of draws needed to obtain that next new type is therefore .
Adding the stage expectations gives
Thus the expected waiting time to collect every type grows like .
Records in random sequences
Suppose are independent observations from the same continuous probability distribution. The th observation is a record high if it exceeds all its predecessors. By symmetry, each of the first observations is equally likely to be their maximum, so the probability that is a record is . Linearity of expectation then gives
Quicksort
For randomized quicksort on distinct keys, with each pivot chosen uniformly from its current subarray and partitioning using one pivot comparison for each other key, the expected comparison count is
The logarithmic growth of therefore yields a leading term of . This is an average over random pivot choices, not a bound on every execution; highly unbalanced partitions can require a quadratic number of comparisons.
Numerical computation
Direct evaluation requires reciprocal calculations and additions. For large , the asymptotic expansion is usually more efficient when an approximation rather than an exact fraction is needed.
In floating-point arithmetic, adding increasingly small terms to a growing total can lose low-order information. Summing from smaller terms toward larger ones, or using compensated summation, reduces this accumulation of rounding error. Exact rational computation avoids rounding but can require large integer numerators and denominators.