Harmonic series (mathematics)
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.
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.
[6] Additional proofs were published in the 17th century by Pietro Mengoli[2][7] and by Jacob Bernoulli.
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.
[14] It is possible to prove that the harmonic series diverges by comparing its sum with an improper integral.
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:
Generalizing this argument, any infinite sum of values of a monotone decreasing positive function of
(like the harmonic series) has partial sums that are within a bounded distance of the values of the corresponding integrals.
[20] This equation can be used to extend the definition to harmonic numbers with rational indices.
[21] Many well-known mathematical problems have solutions involving the harmonic series and its partial sums.
[22] The problem asks how far into the desert a jeep can travel and return, starting from a base with
The optimal solution involves placing depots spaced at distances
However, Alcuin instead asks a slightly different question, how much grain can be transported a distance of 30 leucas without a final return trip, and either strands some camels in the desert or fails to account for the amount of grain consumed by a camel on its return trips.
identical rectangular blocks, one per layer, so that they hang as far as possible over the edge of a table without falling.
[24][25] The divergence of the harmonic series implies that there is no limit on how far beyond the table the block stack can extend.
The left equality comes from applying the distributive law to the product and recognizing the resulting terms as the prime factorizations of the terms in the harmonic series, and the right equality uses the standard formula for a geometric series.
The product is divergent, just like the sum, but if it converged one could take logarithms and obtain
An immediate corollary is that there are infinitely many prime numbers, because a finite sum cannot diverge.
[28] Euler's conclusion that the partial sums of reciprocals of primes grow as a double logarithm of the number of terms has been confirmed by later mathematicians as one of Mertens' theorems,[29] and can be seen as a precursor to the prime number theorem.
The operation of rounding each term in the harmonic series to the next smaller integer multiple of
[30] Several common games or recreations involve repeating a random selection from a set of items until all possible choices have been selected; these include the collection of trading cards[31][32] and the completion of parkrun bingo, in which the goal is to obtain all 60 possible numbers of seconds in the times from a sequence of running events.
[33] More serious applications of this problem include sampling all variations of a manufactured product for its quality control,[34] and the connectivity of random graphs.
down to 1 shows that the total expected number of random choices needed to collect all items is
[36] The quicksort algorithm for sorting a set of items can be analyzed using the harmonic numbers.
In either its average-case complexity (with the assumption that all input permutations are equally likely) or in its expected time analysis of worst-case inputs with a random choice of pivot, all of the items are equally likely to be chosen as the pivot.
Using alternating signs with only odd unit fractions produces a related series, the Leibniz formula for π[40]
It can be extended by analytic continuation to a holomorphic function on all complex numbers except
The sum of the series is a random variable whose probability density function is close to
[42][43] The depleted harmonic series where all of the terms in which the digit 9 appears anywhere in the denominator are removed can be shown to converge to the value 22.92067661926415034816....[44] In fact, when all the terms containing any particular string of digits (in any base) are removed, the series converges.
