Part of a series of articles about |
Calculus |
---|
In mathematics, the harmonic series is the infinite series formed by summing all positive unit fractions:
The first terms of the series sum to approximately , where is the natural logarithm and 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.
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. [1] [2] 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. [2] 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. [3]
The divergence of the harmonic series was first proven in 1350 by Nicole Oresme. [2] [4] 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. [5] However, this achievement fell into obscurity. [6] Additional proofs were published in the 17th century by Pietro Mengoli [2] [7] and by Jacob Bernoulli. [8] [9] [10] Bernoulli credited his brother Johann Bernoulli for finding the proof, [10] and it was later included in Johann Bernoulli's collected works. [11]
The partial sums of the harmonic series were named harmonic numbers, and given their usual notation , in 1968 by Donald Knuth. [12]
The harmonic series is the infinite series
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:
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 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 stays entirely below the upper boundary of the rectangles, so the area under the curve (in the range of 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,
In the figure to the right, shifting each rectangle to the left by 1 unit, 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:
Partial sum of the harmonic series, | ||||
---|---|---|---|---|
expressed as a fraction | decimal | relative size | ||
1 | 1 | 1 | ||
2 | 3 | /2 | 1.5 | |
3 | 11 | /6 | ~1.83333 | |
4 | 25 | /12 | ~2.08333 | |
5 | 137 | /60 | ~2.28333 | |
6 | 49 | /20 | 2.45 | |
7 | 363 | /140 | ~2.59286 | |
8 | 761 | /280 | ~2.71786 | |
9 | 7129 | /2520 | ~2.82897 | |
10 | 7381 | /2520 | ~2.92897 | |
11 | 83711 | /27720 | ~3.01988 | |
12 | 86021 | /27720 | ~3.10321 | |
13 | 1145993 | /360360 | ~3.18013 | |
14 | 1171733 | /360360 | ~3.25156 | |
15 | 1195757 | /360360 | ~3.31823 | |
16 | 2436559 | /720720 | ~3.38073 | |
17 | 42142223 | /12252240 | ~3.43955 | |
18 | 14274301 | /4084080 | ~3.49511 | |
19 | 275295799 | /77597520 | ~3.54774 | |
20 | 55835135 | /15519504 | ~3.59774 |
Adding the first terms of the harmonic series produces a partial sum, called a harmonic number and denoted : [12]
These numbers grow very slowly, with logarithmic growth, as can be seen from the integral test. [15] More precisely, by the Euler–Maclaurin formula,
No harmonic numbers are integers, except for . [17] [18] One way to prove that is not an integer is to consider the highest power of two in the range from 1 to . If is the least common multiple of the numbers from 1 to , then can be rewritten as a sum of fractions with equal denominators
Another proof that the harmonic numbers are not integers observes that the denominator of must be divisible by all prime numbers greater than , and uses Bertrand's postulate to prove that this set of primes is non-empty. The same argument implies more strongly that, except for , , and , no harmonic number can have a terminating decimal representation. [17] It has been conjectured that every prime number divides the numerators of only a finite subset of the harmonic numbers, but this remains unproven. [19]
The digamma function is defined as the logarithmic derivative of the gamma function
Many well-known mathematical problems have solutions involving the harmonic series and its partial sums.
The jeep problem or desert-crossing problem is included in a 9th-century problem collection by Alcuin, Propositiones ad Acuendos Juvenes (formulated in terms of camels rather than jeeps), but with an incorrect solution. [22] The problem asks how far into the desert a jeep can travel and return, starting from a base with loads of fuel, by carrying some of the fuel into the desert and leaving it in depots. The optimal solution involves placing depots spaced at distances from the starting point and each other, where is the range of distance that the jeep can travel with a single load of fuel. On each trip out and back from the base, the jeep places one more depot, refueling at the other depots along the way, and placing as much fuel as it can in the newly placed depot while still leaving enough for itself to return to the previous depots and the base. Therefore, the total distance reached on the th trip is
For instance, for Alcuin's version of the problem, : a camel can carry 30 measures of grain and can travel one leuca while eating a single measure, where a leuca is a unit of distance roughly equal to 2.3 kilometres (1.4 mi). The problem has : there are 90 measures of grain, enough to supply three trips. For the standard formulation of the desert-crossing problem, it would be possible for the camel to travel leucas and return, by placing a grain storage depot 5 leucas from the base on the first trip and 12.5 leucas from the base on the second trip. 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. [22]
In the block-stacking problem, one must place a pile of identical rectangular blocks, one per layer, so that they hang as far as possible over the edge of a table without falling. The top block can be placed with of its length extending beyond the next lower block. If it is placed in this way, the next block down needs to be placed with at most of its length extending beyond the next lower block, so that the center of mass of the top two block is supported and they do not topple. The third block needs to be placed with at most of its length extending beyond the next lower block, and so on. In this way, it is possible to place the blocks in such a way that they extend lengths beyond the table, where is the th harmonic number. [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. [25] For stacks with one block per layer, no better solution is possible, but significantly more overhang can be achieved using stacks with more than one block per layer. [26]
In 1737, Leonhard Euler observed that, as a formal sum, the harmonic series is equal to an Euler product in which each term comes from a prime number:
Another problem in number theory closely related to the harmonic series concerns the average number of divisors of the numbers in a range from 1 to , formalized as the average order of the divisor function,
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. [35] In situations of this form, once there are items remaining to be collected out of a total of equally-likely items, the probability of collecting a new item in a single random choice is and the expected number of random choices needed until a new item is collected is . Summing over all values of from down to 1 shows that the total expected number of random choices needed to collect all items is , where is the th harmonic number. [36]
The quicksort algorithm for sorting a set of items can be analyzed using the harmonic numbers. The algorithm operates by choosing one item as a "pivot", comparing it to all the others, and recursively sorting the two subsets of items whose comparison places them before the pivot and after the pivot. 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. For such cases, one can compute the probability that two items are ever compared with each other, throughout the recursion, as a function of the number of other items that separate them in the final sorted order. If items and are separated by other items, then the algorithm will make a comparison between and only when, as the recursion progresses, it picks or as a pivot before picking any of the other items between them. Because each of these items is equally likely to be chosen first, this happens with probability . The total expected number of comparisons, which controls the total running time of the algorithm, can then be calculated by summing these probabilities over all pairs, giving [37]
The series
Explicitly, the asymptotic expansion of the series is
Using alternating signs with only odd unit fractions produces a related series, the Leibniz formula for π [40]
The Riemann zeta function is defined for real by the convergent series
The random harmonic series is
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. [45]
One might point out that Cauchy's condensation test is merely the extension of Oresme's argument for the divergence of the harmonic series
Part of a series of articles about |
Calculus |
---|
In mathematics, the harmonic series is the infinite series formed by summing all positive unit fractions:
The first terms of the series sum to approximately , where is the natural logarithm and 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.
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. [1] [2] 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. [2] 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. [3]
The divergence of the harmonic series was first proven in 1350 by Nicole Oresme. [2] [4] 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. [5] However, this achievement fell into obscurity. [6] Additional proofs were published in the 17th century by Pietro Mengoli [2] [7] and by Jacob Bernoulli. [8] [9] [10] Bernoulli credited his brother Johann Bernoulli for finding the proof, [10] and it was later included in Johann Bernoulli's collected works. [11]
The partial sums of the harmonic series were named harmonic numbers, and given their usual notation , in 1968 by Donald Knuth. [12]
The harmonic series is the infinite series
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:
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 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 stays entirely below the upper boundary of the rectangles, so the area under the curve (in the range of 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,
In the figure to the right, shifting each rectangle to the left by 1 unit, 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:
Partial sum of the harmonic series, | ||||
---|---|---|---|---|
expressed as a fraction | decimal | relative size | ||
1 | 1 | 1 | ||
2 | 3 | /2 | 1.5 | |
3 | 11 | /6 | ~1.83333 | |
4 | 25 | /12 | ~2.08333 | |
5 | 137 | /60 | ~2.28333 | |
6 | 49 | /20 | 2.45 | |
7 | 363 | /140 | ~2.59286 | |
8 | 761 | /280 | ~2.71786 | |
9 | 7129 | /2520 | ~2.82897 | |
10 | 7381 | /2520 | ~2.92897 | |
11 | 83711 | /27720 | ~3.01988 | |
12 | 86021 | /27720 | ~3.10321 | |
13 | 1145993 | /360360 | ~3.18013 | |
14 | 1171733 | /360360 | ~3.25156 | |
15 | 1195757 | /360360 | ~3.31823 | |
16 | 2436559 | /720720 | ~3.38073 | |
17 | 42142223 | /12252240 | ~3.43955 | |
18 | 14274301 | /4084080 | ~3.49511 | |
19 | 275295799 | /77597520 | ~3.54774 | |
20 | 55835135 | /15519504 | ~3.59774 |
Adding the first terms of the harmonic series produces a partial sum, called a harmonic number and denoted : [12]
These numbers grow very slowly, with logarithmic growth, as can be seen from the integral test. [15] More precisely, by the Euler–Maclaurin formula,
No harmonic numbers are integers, except for . [17] [18] One way to prove that is not an integer is to consider the highest power of two in the range from 1 to . If is the least common multiple of the numbers from 1 to , then can be rewritten as a sum of fractions with equal denominators
Another proof that the harmonic numbers are not integers observes that the denominator of must be divisible by all prime numbers greater than , and uses Bertrand's postulate to prove that this set of primes is non-empty. The same argument implies more strongly that, except for , , and , no harmonic number can have a terminating decimal representation. [17] It has been conjectured that every prime number divides the numerators of only a finite subset of the harmonic numbers, but this remains unproven. [19]
The digamma function is defined as the logarithmic derivative of the gamma function
Many well-known mathematical problems have solutions involving the harmonic series and its partial sums.
The jeep problem or desert-crossing problem is included in a 9th-century problem collection by Alcuin, Propositiones ad Acuendos Juvenes (formulated in terms of camels rather than jeeps), but with an incorrect solution. [22] The problem asks how far into the desert a jeep can travel and return, starting from a base with loads of fuel, by carrying some of the fuel into the desert and leaving it in depots. The optimal solution involves placing depots spaced at distances from the starting point and each other, where is the range of distance that the jeep can travel with a single load of fuel. On each trip out and back from the base, the jeep places one more depot, refueling at the other depots along the way, and placing as much fuel as it can in the newly placed depot while still leaving enough for itself to return to the previous depots and the base. Therefore, the total distance reached on the th trip is
For instance, for Alcuin's version of the problem, : a camel can carry 30 measures of grain and can travel one leuca while eating a single measure, where a leuca is a unit of distance roughly equal to 2.3 kilometres (1.4 mi). The problem has : there are 90 measures of grain, enough to supply three trips. For the standard formulation of the desert-crossing problem, it would be possible for the camel to travel leucas and return, by placing a grain storage depot 5 leucas from the base on the first trip and 12.5 leucas from the base on the second trip. 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. [22]
In the block-stacking problem, one must place a pile of identical rectangular blocks, one per layer, so that they hang as far as possible over the edge of a table without falling. The top block can be placed with of its length extending beyond the next lower block. If it is placed in this way, the next block down needs to be placed with at most of its length extending beyond the next lower block, so that the center of mass of the top two block is supported and they do not topple. The third block needs to be placed with at most of its length extending beyond the next lower block, and so on. In this way, it is possible to place the blocks in such a way that they extend lengths beyond the table, where is the th harmonic number. [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. [25] For stacks with one block per layer, no better solution is possible, but significantly more overhang can be achieved using stacks with more than one block per layer. [26]
In 1737, Leonhard Euler observed that, as a formal sum, the harmonic series is equal to an Euler product in which each term comes from a prime number:
Another problem in number theory closely related to the harmonic series concerns the average number of divisors of the numbers in a range from 1 to , formalized as the average order of the divisor function,
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. [35] In situations of this form, once there are items remaining to be collected out of a total of equally-likely items, the probability of collecting a new item in a single random choice is and the expected number of random choices needed until a new item is collected is . Summing over all values of from down to 1 shows that the total expected number of random choices needed to collect all items is , where is the th harmonic number. [36]
The quicksort algorithm for sorting a set of items can be analyzed using the harmonic numbers. The algorithm operates by choosing one item as a "pivot", comparing it to all the others, and recursively sorting the two subsets of items whose comparison places them before the pivot and after the pivot. 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. For such cases, one can compute the probability that two items are ever compared with each other, throughout the recursion, as a function of the number of other items that separate them in the final sorted order. If items and are separated by other items, then the algorithm will make a comparison between and only when, as the recursion progresses, it picks or as a pivot before picking any of the other items between them. Because each of these items is equally likely to be chosen first, this happens with probability . The total expected number of comparisons, which controls the total running time of the algorithm, can then be calculated by summing these probabilities over all pairs, giving [37]
The series
Explicitly, the asymptotic expansion of the series is
Using alternating signs with only odd unit fractions produces a related series, the Leibniz formula for π [40]
The Riemann zeta function is defined for real by the convergent series
The random harmonic series is
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. [45]
One might point out that Cauchy's condensation test is merely the extension of Oresme's argument for the divergence of the harmonic series