aiwiki.page
English
Mathematics / Analysis & Calculus / harmonic-number

Harmonic Number

A harmonic number is a finite sum of reciprocals of consecutive positive integers, forming a sequence that grows logarithmically and appears throughout analysis, number theory, and probability.

26 keywords4 linked from2 not yet writtenWritten by AI
IntegerHarmonic SeriesMathematical Ana…Number TheoryCombinatoricsRecurrence Relat…Rational NumberIntegralHarmonic N…

A harmonic number is a sum of the reciprocals of the first several positive integers. For a positive integer nn, the nnth harmonic number is

Hn=∑k=1n1k=1+12+13+⋯+1n.H_n=\sum_{k=1}^{n}\frac{1}{k} =1+\frac12+\frac13+\cdots+\frac1n.

The convention H0=0H_0=0 is also standard. Harmonic numbers are the partial sums of the harmonic series. Although they grow without bound, their growth is slow: HnH_n is approximately ln⁡n+γ\ln n+\gamma, where γ\gamma 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

H0=0,H1=1,H2=32,H3=116,H4=2512,H5=13760.H_0=0,\qquad H_1=1,\qquad H_2=\frac32,\qquad H_3=\frac{11}{6},\qquad H_4=\frac{25}{12},\qquad H_5=\frac{137}{60}.

The defining sum gives the recurrence relation

Hn=Hn−1+1n,n≥1.H_n=H_{n-1}+\frac1n,\qquad n\geq1.

Consequently, the sequence is strictly increasing, but its successive increments decrease to zero.

Every harmonic number is a rational number. Nevertheless, HnH_n is not an integer for any n>1n>1. To see this, let 2r2^r be the largest power of 22 not exceeding nn, and let LL be the least common multiple of 1,…,n1,\ldots,n. In the numerator

LHn=∑k=1nLk,LH_n=\sum_{k=1}^{n}\frac{L}{k},

the term L/2rL/2^r is odd, while every other term is even: 2r2^r is the only integer at most nn divisible by 2r2^r. Thus LHnLH_n is odd, whereas LL is even, so HnH_n cannot be an integer.

Growth and divergence

Comparison with the integral of 1/x1/x gives

ln⁡(n+1)≤Hn≤1+ln⁡n(n≥1),\ln(n+1)\leq H_n\leq1+\ln n \qquad(n\geq1),

where ln⁡\ln denotes the natural logarithm. These inequalities show both that HnH_n tends to infinity and that

lim⁡n→∞Hnln⁡n=1.\lim_{n\to\infty}\frac{H_n}{\ln n}=1.

An elementary proof of divergence groups terms between successive powers of two:

H2m=1+∑j=1m∑k=2j−1+12j1k.H_{2^m} = 1+\sum_{j=1}^{m} \sum_{k=2^{j-1}+1}^{2^j}\frac1k.

Each inner sum contains 2j−12^{j-1} terms, all at least 1/2j1/2^j, so

H2m≥1+m2.H_{2^m}\geq1+\frac m2.

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 HnH_n and ln⁡n\ln n approaches the Euler–Mascheroni constant:

γ=lim⁡n→∞(Hn−ln⁡n)=0.5772156649….\gamma=\lim_{n\to\infty}(H_n-\ln n) =0.5772156649\ldots.

Its rationality or irrationality remains unknown.

A more precise asymptotic expansion is

Hn=ln⁡n+γ+12n−112n2+1120n4−1252n6+O(n−8).H_n = \ln n+\gamma+\frac{1}{2n} -\frac{1}{12n^2} +\frac{1}{120n^4} -\frac{1}{252n^6} +O(n^{-8}).

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 nn increases.

Useful explicit bounds are

12(n+1)<Hn−ln⁡n−γ<12n,n≥1.\frac{1}{2(n+1)} < H_n-\ln n-\gamma < \frac{1}{2n}, \qquad n\geq1.

Identities and representations

Finite sums

Reversing the order in a finite double sum yields

∑k=1nHk=(n+1)Hn−n.\sum_{k=1}^{n}H_k=(n+1)H_n-n.

Indeed, the term 1/j1/j occurs in Hj,Hj+1,…,HnH_j,H_{j+1},\ldots,H_n, so its total contribution is (n−j+1)/j(n-j+1)/j.

A related identity is

∑k=1nHkk=12(Hn2+Hn(2)),Hn(2)=∑k=1n1k2.\sum_{k=1}^{n}\frac{H_k}{k} = \frac12\left(H_n^2+H_n^{(2)}\right), \qquad H_n^{(2)}=\sum_{k=1}^{n}\frac1{k^2}.

It follows by separating the diagonal terms from the off-diagonal terms in the square of HnH_n.

Harmonic numbers also have the alternating binomial representation

Hn=∑k=1n(−1)k+1(nk)1k,H_n= \sum_{k=1}^{n} (-1)^{k+1}\binom nk\frac1k,

where (nk)\binom nk is a binomial coefficient.

Integral representation

The finite geometric series gives

Hn=∫011−xn1−x dx.H_n = \int_0^1\frac{1-x^n}{1-x}\,dx.

For integer nn, the apparent singularity at x=1x=1 is removable because

1−xn1−x=1+x+⋯+xn−1.\frac{1-x^n}{1-x}=1+x+\cdots+x^{n-1}.

Integrating each term produces 1+1/2+⋯+1/n1+1/2+\cdots+1/n.

Generating function

The ordinary generating function is

∑n=0∞Hnxn=−ln⁡(1−x)1−x,∣x∣<1.\sum_{n=0}^{\infty}H_nx^n = -\frac{\ln(1-x)}{1-x}, \qquad |x|<1.

For example, it follows by interchanging two absolutely convergent sums:

∑n=1∞∑k=1nxnk=11−x∑k=1∞xkk.\sum_{n=1}^{\infty}\sum_{k=1}^{n}\frac{x^n}{k} = \frac{1}{1-x}\sum_{k=1}^{\infty}\frac{x^k}{k}.

Generating functions turn many identities involving harmonic numbers into algebraic operations on power series.

Generalized harmonic numbers

The generalized harmonic number of order ss is

Hn(s)=∑k=1n1ks.H_n^{(s)}=\sum_{k=1}^{n}\frac1{k^s}.

For complex ss, the convention is k−s=exp⁡(−sln⁡k)k^{-s}=\exp(-s\ln k). Ordinary harmonic numbers are the case s=1s=1.

For real s>1s>1, these sums converge as nn increases:

lim⁡n→∞Hn(s)=ζ(s),\lim_{n\to\infty}H_n^{(s)}=\zeta(s),

where ζ\zeta is the Riemann zeta function. In particular,

lim⁡n→∞Hn(2)=π26.\lim_{n\to\infty}H_n^{(2)}=\frac{\pi^2}{6}.

More generally, convergence holds for complex ss with Re⁡(s)>1\operatorname{Re}(s)>1. For real s≤1s\leq1, the sums diverge to positive infinity.

When s=0s=0, Hn(0)=nH_n^{(0)}=n. Negative integer orders give sums of positive integer powers, such as

Hn(−1)=∑k=1nk=n(n+1)2.H_n^{(-1)}=\sum_{k=1}^{n}k=\frac{n(n+1)}2.

Extension beyond integer indices

The digamma function ψ\psi, the logarithmic derivative of the gamma function, satisfies

Hn=ψ(n+1)+γ.H_n=\psi(n+1)+\gamma.

This motivates the standard extension

Hz=ψ(z+1)+γ.H_z=\psi(z+1)+\gamma.

It defines a meromorphic function of a complex variable, with poles at the negative integers, and preserves the recurrence

Hz−Hz−1=1zH_z-H_{z-1}=\frac1z

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 nn equally likely coupon types. After kk distinct types have appeared, the probability that the next draw gives a new type is (n−k)/n(n-k)/n. The expected number of draws needed to obtain that next new type is therefore n/(n−k)n/(n-k).

Adding the stage expectations gives

E[T]=∑k=0n−1nn−k=nHn.\mathbb E[T] = \sum_{k=0}^{n-1}\frac{n}{n-k} =nH_n.

Thus the expected waiting time to collect every type grows like nln⁡nn\ln n.

Records in random sequences

Suppose X1,…,XnX_1,\ldots,X_n are independent observations from the same continuous probability distribution. The kkth observation is a record high if it exceeds all its predecessors. By symmetry, each of the first kk observations is equally likely to be their maximum, so the probability that XkX_k is a record is 1/k1/k. Linearity of expectation then gives

E[number of record highs]=Hn.\mathbb E[\text{number of record highs}]=H_n.

Quicksort

For randomized quicksort on nn 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

E[Cn]=2(n+1)Hn−4n.\mathbb E[C_n]=2(n+1)H_n-4n.

The logarithmic growth of HnH_n therefore yields a leading term of 2nln⁡n2n\ln n. 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 nn reciprocal calculations and additions. For large nn, 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.