Harmonic sum

In mathematics, the harmonic series is the infinite series formed by summing all positive unit fractions:
$\sum_^\infty\frac = 1 + \frac + \frac + \frac + \frac + \cdots.$

The first $n$ terms of the series sum to approximately $\ln n + \gamma$, where $\ln$ is the natural logarithm and $\gamma\approx0.577$ is the Euler–Mascheroni constant. Because the logarithm has arbitrarily large values, the harmonic series does not have a finite limit: it is a divergent series. Its divergence was proven in the 14th century by Nicole Oresme using a precursor to the Cauchy condensation test for the convergence of infinite series. It can also be proven to diverge by comparing the sum to an integral, according to the integral test for convergence.

Applications of the harmonic series and its partial sums include Euler's proof that there are infinitely many prime numbers, the analysis of the coupon collector's problem on how many random trials are needed to provide a complete range of responses, the connected components of random graphs, the block-stacking problem on how far over the edge of a table a stack of blocks can be cantilevered, and the average case analysis of the quicksort algorithm.

History

The name of the harmonic series derives from the concept of overtones or harmonics in music: the wavelengths of the overtones of a vibrating string are etc., of the string's fundamental wavelength. Every term of the harmonic series after the first is the harmonic mean of the neighboring terms, so the terms form a harmonic progression; the phrases ''harmonic mean'' and ''harmonic progression'' likewise derive from music.
Beyond music, harmonic sequences have also had a certain popularity with architects. This was so particularly in the Baroque period, when architects used them to establish the proportions of floor plans, of elevations, and to establish harmonic relationships between both interior and exterior architectural details of churches and palaces.

The divergence of the harmonic series was first proven in 1350 by Nicole Oresme. Oresme's work, and the contemporaneous work of Richard Swineshead on a different series, marked the first appearance of infinite series other than the geometric series in mathematics. However, this achievement fell into obscurity. Additional proofs were published in the 17th century by Pietro Mengoli and by Jacob Bernoulli. Bernoulli credited his brother Johann Bernoulli for finding the proof, and it was later included in Johann Bernoulli's collected works.

The partial sums of the harmonic series were named harmonic numbers, and given their usual notation $H_n$, in 1968 by Donald Knuth.

Definition and divergence

The harmonic series is the infinite series
$\sum_^\infty\frac = 1 + \frac + \frac + \frac + \frac + \cdots$
in which the terms are all of the positive unit fractions. It is a divergent series: as more terms of the series are included in partial sums of the series, the values of these partial sums grow arbitrarily large, beyond any finite limit. Because it is a divergent series, it should be interpreted as a formal sum, an abstract mathematical expression combining the unit fractions, rather than as something that can be evaluated to a numeric value. There are many different proofs of the divergence of the harmonic series, surveyed in a 2006 paper by S. J. Kifowit and T. A. Stamps.
Two of the best-known are listed below.

Comparison test

One way to prove divergence is to compare the harmonic series with another divergent series, where each denominator is replaced with the next-largest power of two:
\begin
1 & + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \cdots \\ pt
\geq 1 & + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \cdots \\ pt \end
Grouping equal terms shows that the second series diverges (because every grouping of convergent series is only convergent):
\begin
& 1 + \left(\frac\right) + \left(\frac + \frac\right) + \left(\frac + \frac + \frac + \frac\right) + \left(\frac + \cdots + \frac\right) + \cdots \\ pt = & 1 + \frac + \frac + \frac + \frac + \cdots.
\end
Because each term of the harmonic series is greater than or equal to the corresponding term of the second series (and the terms are all positive), it follows (by the comparison test) that the harmonic series diverges as well. The same argument proves more strongly that, for every positive
$\sum_^ \frac \geq 1 + \frac$
This is the original proof given by Nicole Oresme in around 1350. The Cauchy condensation test is a generalization of this argument.

Integral test

It is possible to prove that the harmonic series diverges by comparing its sum with an improper integral. Specifically, consider the arrangement of rectangles shown in the figure to the right. Each rectangle is 1 unit wide and $\tfrac1n$ units high, so if the harmonic series converged then the total area of the rectangles would be the sum of the harmonic series. The curve $y=\tfrac1x$ stays entirely below the upper boundary of the rectangles, so the area under the curve (in the range of $x$ from one to infinity that is covered by rectangles) would be less than the area of the union of the rectangles. However, the area under the curve is given by a divergent improper integral,
$\int_1^\infty\frac\,dx = \infty.$
Because this integral does not converge, the sum cannot converge either.

Replacing each rectangle by the next one in the sequence would produce a sequence of rectangles whose boundary lies below the curve rather than above it.
This shows that the partial sums of the harmonic series differ from the integral by an amount that is bounded above and below by the unit area of the first rectangle:
$\int_1^\frac1x\,dx<\sum_^N\frac1i<\int_1^\frac1x\,dx+1.$
Generalizing this argument, any infinite sum of values of a monotone decreasing positive function (like the harmonic series) has partial sums that are within a bounded distance of the values of the corresponding integrals. Therefore, the sum converges if and only if the integral over the same range of the same function converges. When this equivalence is used to check the convergence of a sum by replacing it with an easier integral, it is known as the integral test for convergence.

Partial sums

Adding the first $n$ terms of the harmonic series produces a partial sum, called a harmonic number and
$H_n = \sum_^n \frac.$

Growth rate

These numbers grow very slowly, with logarithmic growth, as can be seen from the integral test. More precisely, by the Euler–Maclaurin formula,
$H_n = \ln n + \gamma + \frac - \varepsilon_n$
where $\gamma\approx 0.5772$ is the Euler–Mascheroni constant and $0\le\varepsilon_n\le 1/8n^2$ which approaches 0 as $n$ goes to infinity.

Divisibility

No harmonic numbers are integers, except for One way to prove that $H_n$ is not an integer is to consider the highest power of two $2^k$ in the range from If $M$ is the least common multiple of the numbers from then
$H_k$ can be rewritten as a sum of fractions with equal denominators $H_n=\sum_^n \tfrac$
in which only one of the numerators, is odd and the rest are even, and $M$ is itself even. Therefore, the result is a fraction with an odd numerator and an even denominator, which cannot be an integer. More strongly, any sequence of consecutive integers has a unique member divisible by a greater power of two than all the other sequence members, from which it follows by the same argument that no two harmonic numbers differ by an integer.

Another proof that the harmonic numbers are not integers observes that the denominator of $H_n$ must be divisible by
all prime numbers greater than $n/2$, and uses Bertrand's postulate to prove that this set of primes is non-empty. The same argument implies more strongly that, except for $H_1=1$, $H_2=1.5$, and $H_6=2.45$, no harmonic number can have a terminating decimal representation. It has been conjectured that every prime number divides the numerators of only a finite subset of the harmonic numbers, but this remains unproven.

Interpolation

The digamma function is defined as the logarithmic derivative of the gamma function
$\psi(x)=\frac\ln\big(\Gamma(x)\big)=\frac.$
Just as the gamma function provides a continuous interpolation of the factorials, the digamma function provides a continuous interpolation of the harmonic numbers, in the sense that
This equation can be used to extend the definition to harmonic numbers with rational indices.

Applications

Many well-known mathematical problems have solutions involving the harmonic series and its partial sums.

Crossing a desert

The jeep problem or desert-crossing problem is included in a 9th-century problem collection by Alcuin, ''Propositiones ad Acuendos Juvenes

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases