Movatterモバイル変換

[0]ホーム

Jump to content

Harmonic series (mathematics)

Edit links

This is a good article. Click here for more information.

From Wikipedia, the free encyclopedia

(Redirected fromAlternating harmonic series)

Divergent sum of positive unit fractions

Part of a series of articles about

Calculus

\int _{a}^{b}f'(t)\,dt=f(b)-f(a)

Fundamental theorem

Differential

Definitions
Derivative (generalizations) Differential infinitesimal of a function total
Concepts
Differentiation notation Second derivative Implicit differentiation Logarithmic differentiation Related rates Taylor's theorem
Rules and identities
Sum Product Chain Power Quotient L'Hôpital's rule Inverse General Leibniz Faà di Bruno's formula Reynolds

Integral

Definitions
Lists of integrals Integral transform Leibniz integral rule
Antiderivative Integral (improper) Riemann integral Lebesgue integration Contour integration Integral of inverse functions
Integration by
Parts Discs Cylindrical shells Substitution (trigonometric,tangent half-angle,Euler) Euler's formula Partial fractions (Heaviside's method) Changing order Reduction formulae Differentiating under the integral sign Risch algorithm

Series

Convergence tests
Geometric (arithmetico-geometric) Harmonic Alternating Power Binomial Taylor
Summand limit (term test) Ratio Root Integral Direct comparison Limit comparison Alternating series Cauchy condensation Dirichlet Abel

Vector

Theorems
Gradient Divergence Curl Laplacian Directional derivative Identities
Gradient Green's Stokes' Divergence Generalized Stokes Helmholtz decomposition

Multivariable

Formalisms
Matrix Tensor Exterior Geometric
Definitions
Partial derivative Multiple integral Line integral Surface integral Volume integral Jacobian Hessian

Advanced

Specialized

Miscellanea

Inmathematics, theharmonic series is theinfinite series formed by summing all positiveunit fractions: $\sum _{n=1}^{\infty }{\frac {1}{n}}=1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{5}}+\cdots .$

The first $n {\displaystyle n}$ terms of the series sum to approximately $\ln n+\gamma$ , where $\ln$ is thenatural logarithm and $\gamma \approx 0.577$ is theEuler–Mascheroni constant. Because the logarithm has arbitrarily large values, the harmonic series does not have a finite limit: it is adivergent series. Its divergence was proven in the 14th century byNicole Oresme using a precursor to theCauchy condensation test for the convergence of infinite series. It can also be proven to diverge by comparing the sum to anintegral, according to theintegral test for convergence.

Applications of the harmonic series and its partial sums includeEuler's proof that there are infinitely many prime numbers, the analysis of thecoupon collector's problem on how many random trials are needed to provide a complete range of responses, theconnected components ofrandom graphs, theblock-stacking problem on how far over the edge of a table a stack of blocks can becantilevered, and theaverage case analysis of thequicksort algorithm.

History

[edit]

A wave and its harmonics, with wavelengths $1,{\tfrac {1}{2}},{\tfrac {1}{3}},\dots$ where the amplitude is inversely proportional to the frequency.

{\displaystyle 1,{\tfrac {1}{2}},{\tfrac {1}{3}},\dots } — A wave and its harmonics, with wavelengths $1,{\tfrac {1}{2}},{\tfrac {1}{3}},\dots$ where the amplitude is inversely proportional to the frequency.

The name of the harmonic series derives from the concept ofovertones or harmonicsin music: thewavelengths of the overtones of a vibrating string are ${\tfrac {1}{2}}$ , ${\tfrac {1}{3}}$ , ${\tfrac {1}{4}}$ , etc., of the string'sfundamental wavelength.^[1]^[2] Every term of the harmonic series after the first is theharmonic mean of the neighboring terms, so the terms form aharmonic progression; the phrasesharmonic mean andharmonic progression likewise derive from music.^[2]Beyond music, harmonic sequences have also had a certain popularity with architects. This was so particularly in theBaroque period, when architects used them to establish theproportions offloor plans, ofelevations, 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 byNicole Oresme.^[2]^[4] Oresme's work, and the contemporaneous work ofRichard Swineshead on a different series, marked the first appearance of infinite series other than thegeometric series in mathematics.^[5] However, this achievement fell into obscurity.^[6] Additional proofs were published in the 17th century byPietro Mengoli^[2]^[7] and byJacob Bernoulli.^[8]^[9]^[10] Bernoulli credited his brotherJohann 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 namedharmonic numbers, and given their usual notation $H_{n}$ , in 1968 byDonald Knuth.^[12]

Definition and divergence

[edit]

The harmonic series is the infinite series $\sum _{n=1}^{\infty }{\frac {1}{n}}=1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{5}}+\cdots$ in which the terms are all of the positiveunit fractions. It is adivergent series: as more terms of the series are included inpartial 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.^[13]Two of the best-known^[1]^[13] are listed below.

Comparison test

[edit]

There are infinite blue rectangles each with area 1/2, yet their total area is exceeded by that of the grey bars denoting the harmonic series

One way to prove divergence is to compare the harmonic series with another divergent series, where each denominator is replaced with the next-largestpower of two: ${\begin{alignedat}{8}1&+{\frac {1}{2}}&&+{\frac {1}{3}}&&+{\frac {1}{4}}&&+{\frac {1}{5}}&&+{\frac {1}{6}}&&+{\frac {1}{7}}&&+{\frac {1}{8}}&&+{\frac {1}{9}}&&+\cdots \\[5pt]{}\geq 1&+{\frac {1}{2}}&&+{\frac {1}{\color {red}{\mathbf {4} }}}&&+{\frac {1}{4}}&&+{\frac {1}{\color {red}{\mathbf {8} }}}&&+{\frac {1}{\color {red}{\mathbf {8} }}}&&+{\frac {1}{\color {red}{\mathbf {8} }}}&&+{\frac {1}{8}}&&+{\frac {1}{\color {red}{\mathbf {16} }}}&&+\cdots \\[5pt]\end{alignedat}}$ Grouping equal terms shows that the second series diverges (because every grouping of convergent series is only convergent): ${\begin{aligned}&1+\left({\frac {1}{2}}\right)+\left({\frac {1}{4}}+{\frac {1}{4}}\right)+\left({\frac {1}{8}}+{\frac {1}{8}}+{\frac {1}{8}}+{\frac {1}{8}}\right)+\left({\frac {1}{16}}+\cdots +{\frac {1}{16}}\right)+\cdots \\[5pt]{}={}&1+{\frac {1}{2}}+{\frac {1}{2}}+{\frac {1}{2}}+{\frac {1}{2}}+\cdots .\end{aligned}}$ 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), and since the second series diverges, it follows (by thecomparison test) that the harmonic series diverges as well. The same argument proves more strongly that, for everypositiveinteger $k {\displaystyle k}$ , $\sum _{n=1}^{2^{k}}{\frac {1}{n}}\geq 1+{\frac {k}{2}}$ This is the original proof given byNicole Oresme in around 1350.^[13] TheCauchy condensation test is a generalization of this argument.^[14]

Integral test

[edit]

Rectangles with area given by the harmonic series, and the hyperbola $y=1/x$ through the upper left corners of these rectangles

{\displaystyle y=1/x} — Rectangles with area given by the harmonic series, and the hyperbola $y=1/x$ through the upper left corners of these rectangles

It is possible to prove that the harmonic series diverges by comparing its sum with animproper integral. Specifically, consider the arrangement of rectangles shown in the figure to the right. Each rectangle is 1 unit wide and ${\tfrac {1}{n}}$ 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={\tfrac {1}{x}}$ stays entirely below the upper boundary of the rectangles, so the area under the curve (in the range of $x {\displaystyle 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 divergentimproper integral, $\int _{1}^{\infty }{\frac {1}{x}}\,dx=\infty .$ Because this integral does not converge, the sum cannot converge either.^[13]

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: $\int _{1}^{N+1}{\frac {1}{x}}\,dx<\sum _{i=1}^{N}{\frac {1}{i}}<\int _{1}^{N}{\frac {1}{x}}\,dx+1.$ Generalizing this argument, any infinite sum of values of a monotone decreasing positive functionof $n {\displaystyle n}$ (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 theintegral test for convergence.^[15]

Partial sums

[edit]

Main article:Harmonic number

$n {\displaystyle n}$	Partial sum of the harmonic series, $H_{n}$
$n {\displaystyle n}$	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 $n {\displaystyle n}$ terms of the harmonic series produces apartial sum, called aharmonic number anddenoted $H_{n}$ :^[12] $H_{n}=\sum _{k=1}^{n}{\frac {1}{k}}.$

Growth rate

[edit]

These numbers grow very slowly, withlogarithmic growth, as can be seen from the integral test.^[15] More precisely, by theEuler–Maclaurin formula, $H_{n}=\ln n+\gamma +{\frac {1}{2n}}-\varepsilon _{n}$ where $\gamma \approx 0.5772$ is theEuler–Mascheroni constant and $0\leq \varepsilon _{n}\leq 1/(8n^{2})$ which approaches 0 as $n {\displaystyle n}$ goes to infinity.^[16]

Divisibility

[edit]

No harmonic numbers are integers except for $H_{1}=1$ .^[17]^[18] One way to prove that $H_{n}$ is not an integer is to consider the highestpower of two $2^{k}$ in the range from1 to $n {\displaystyle n}$ . If $M {\displaystyle M}$ is theleast common multiple of the numbers from1 to $n {\displaystyle n}$ , then $H_{k}$ can be rewritten as a sum of fractions with equal denominators $H_{n}=\sum _{i=1}^{n}{\tfrac {M/i}{M}}$ in which only one of the numerators, $M/2^{k}$ , is odd and the rest are even, and(when $n>1$ ) $M {\displaystyle M}$ is itself even. Therefore, the result is a fraction with an odd numerator and an even denominator, which cannot be an integer.^[17] More generally, 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.^[18]

Another proof that the harmonic numbers are not integers observes that the denominator of $H_{n}$ must be divisible by allprime numbers greater than $n/2$ and less than or equal to $n {\displaystyle n}$ , and usesBertrand'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 aterminating 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]

Interpolation

[edit]

Thedigamma function on the complex numbers

Thedigamma function is defined as thelogarithmic derivative of thegamma function $\psi (x)={\frac {d}{dx}}\ln {\big (}\Gamma (x){\big )}={\frac {\Gamma '(x)}{\Gamma (x)}}.$ Just as the gamma function provides a continuousinterpolation of thefactorials, the digamma function provides a continuous interpolation of the harmonic numbers, in the sense that $\psi (n)=H_{n-1}-\gamma$ .^[20]This equation can be used to extend the definition to harmonic numbers with rational indices.^[21]

Applications

[edit]

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

Crossing a desert

[edit]

Main article:Jeep problem

Solution to the jeep problem for $n=3$ , showing the amount of fuel in each depot and in the jeep at each step

{\displaystyle n=3} — Solution to the jeep problem for $n=3$ , showing the amount of fuel in each depot and in the jeep at each step

Thejeep problem or desert-crossing problem is included in a 9th-century problem collection byAlcuin,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 $n {\displaystyle n}$ 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 ${\tfrac {r}{2n}},{\tfrac {r}{2(n-1)}},{\tfrac {r}{2(n-2)}},\dots$ from the starting point and each other, where $r {\displaystyle r}$ 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 $n {\displaystyle n}$ th trip is ${\frac {r}{2n}}+{\frac {r}{2(n-1)}}+{\frac {r}{2(n-2)}}+\cdots ={\frac {r}{2}}H_{n},$ where $H_{n}$ is the $n {\displaystyle n}$ th harmonic number. The divergence of the harmonic series implies that crossings of any length are possible with enough fuel.^[23]

For instance, for Alcuin's version of the problem, $r=30$ : 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 $n=3$ : 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 ${\tfrac {30}{2}}{\bigl (}{\tfrac {1}{3}}+{\tfrac {1}{2}}+{\tfrac {1}{1}})=27.5$ 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]

Stacking blocks

[edit]

Main article:Block-stacking problem

Theblock-stacking problem: blocks aligned according to the harmonic series can overhang the edge of a table by the harmonic numbers

In theblock-stacking problem, one must place a pile of $n {\displaystyle n}$ 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 ${\tfrac {1}{2}}$ 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 ${\tfrac {1}{2}}\cdot {\tfrac {1}{2}}$ of its length extending beyond the next lower block, so that thecenter of mass of the top two blocks is supported and they do not topple. The third block needs to be placed with at most ${\tfrac {1}{2}}\cdot {\tfrac {1}{3}}$ of its length extending beyond the next lower block, so that the center of mass of the top three blocks is supported and they do not topple, and so on. In this way, it is possible to place the $n {\displaystyle n}$ blocks in such a way that they extend ${\tfrac {1}{2}}H_{n}$ lengths beyond the table, where $H_{n}$ is the $n {\displaystyle n}$ 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]

Counting primes and divisors

[edit]

Main article:Divergence of the sum of the reciprocals of the primes

In 1737,Leonhard Euler observed that, as aformal sum, the harmonic series is equal to anEuler product in which each term comes from aprime number: $\sum _{i=1}^{\infty }{\frac {1}{i}}=\prod _{p\in \mathbb {P} }\left(1+{\frac {1}{p}}+{\frac {1}{p^{2}}}+\cdots \right)=\prod _{p\in \mathbb {P} }{\frac {1}{1-1/p}},$ where $\mathbb {P}$ denotes the set of prime numbers. The left equality comes from applying thedistributive law to the product and recognizing the resulting terms as theprime factorizations of the terms in the harmonic series, and the right equality uses the standard formula for ageometric series. The product is divergent, just like the sum, but if it converged one could take logarithms and obtain $\ln \prod _{p\in \mathbb {P} }{\frac {1}{1-1/p}}=\sum _{p\in \mathbb {P} }\ln {\frac {1}{1-1/p}}=\sum _{p\in \mathbb {P} }\left({\frac {1}{p}}+{\frac {1}{2p^{2}}}+{\frac {1}{3p^{3}}}+\cdots \right)=\sum _{p\in \mathbb {P} }{\frac {1}{p}}+K.$ Here, each logarithm is replaced by itsTaylor series, and the constant $K {\displaystyle K}$ on the right is the evaluation of the convergent series of terms with exponent greater than one. It follows from these manipulations that the sum of reciprocals of primes, on the right hand of this equality, must diverge, for if it converged these steps could be reversed to show that the harmonic series also converges, which it does not. An immediate corollary is thatthere are infinitely many prime numbers, because a finite sum cannot diverge.^[27] Although Euler's work is not considered adequately rigorous by the standards of modern mathematics, it can be made rigorous by taking more care with limits and error bounds.^[28] Euler's conclusion that the partial sums of reciprocals of primes grow as adouble logarithm of the number of terms has been confirmed by later mathematicians as one ofMertens' theorems,^[29] and can be seen as a precursor to theprime number theorem.^[28]

Another problem innumber theory closely related to the harmonic series concerns the average number ofdivisors of the numbers in a range from 1 to $n {\displaystyle n}$ , formalized as theaverage order of thedivisor function, ${\frac {1}{n}}\sum _{i=1}^{n}\left\lfloor {\frac {n}{i}}\right\rfloor \leq {\frac {1}{n}}\sum _{i=1}^{n}{\frac {n}{i}}=H_{n}.$ The operation of rounding each term in the harmonic series to the next smaller integer multiple of ${\tfrac {1}{n}}$ causes this average to differ from the harmonic numbers by a small constant, andPeter Gustav Lejeune Dirichlet showed more precisely that the average number of divisors is $\ln n+2\gamma -1+O(1/{\sqrt {n}})$ (expressed inbig O notation). Bounding the final error term more precisely remains an open problem, known asDirichlet's divisor problem.^[30]

Collecting coupons

[edit]

Main article:Coupon collector's problem

Graph of number of items versus the expected number of trials needed to collect all items

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 oftrading cards^[31]^[32] and the completion ofparkrun 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 itsquality control,^[34] and theconnectivity ofrandom graphs.^[35] In situations of this form, once there are $k {\displaystyle k}$ items remaining to be collected out of a total of $n {\displaystyle n}$ equally-likely items, the probability of collecting a new item in a single random choice is $k/n$ and the expected number of random choices needed until a new item is collectedis $n/k$ . Summing over all values of $k {\displaystyle k}$ from $n {\displaystyle n}$ down to 1 shows that the total expected number of random choices needed to collect all itemsis $nH_{n}$ , where $H_{n}$ is the $n {\displaystyle n}$ th harmonic number.^[36]

Analyzing algorithms

[edit]

Main article:Quicksort

Thequicksort 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 itsaverage-case complexity (with the assumption that all input permutations are equally likely) or in itsexpected 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 $x {\displaystyle x}$ and $y {\displaystyle y}$ are separated by $k {\displaystyle k}$ other items, then the algorithm will make a comparison between $x {\displaystyle x}$ and $y {\displaystyle y}$ only when, as the recursion progresses, it picks $x {\displaystyle x}$ or $y {\displaystyle y}$ as a pivot before picking any of the other $k {\displaystyle k}$ items between them. Because each of these $k+2$ items is equally likely to be chosen first, this happens with probability ${\tfrac {2}{k+2}}$ . 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] $\sum _{i=2}^{n}\sum _{k=0}^{i-2}{\frac {2}{k+2}}=\sum _{i=1}^{n-1}2H_{i}=O(n\log n).$ The divergence of the harmonic series corresponds in this application to the fact that, in thecomparison model of sorting used for quicksort, it is not possible to sort inlinear time.^[38]

Related series

[edit]

{\begin{aligned}g(x)&={\frac {1}{\pi }}\int _{0}^{\infty }\cos(xt)\prod _{n=0}^{\infty }{\frac {\sin(2t/(2n+1))}{2t/(2n+1)}}dt\\&={\frac {1}{\pi }}\int _{0}^{\infty }\cos(xt)\prod _{n=1}^{\infty }\cos(t/n)dt.\end{aligned}}

This function isclose to ${\tfrac {1}{4}}$ for values between $-1$ and $1 {\displaystyle 1}$ , with the $g(0)\approx 0.2499943958$ to ten decimal places. It decreases asymptotically like anormal distribution for values greaterthan $3 {\displaystyle 3}$ or lessthan $-3$ . Intermediate between these ranges, at thevalues $\pm 2$ , the probability density is ${\tfrac {1}{8}}-\varepsilon$ for a nonzero but very small value $\varepsilon <10^{-42}$ .^[42]^[43]

Depleted harmonic series

[edit]

Main article:Kempner series

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 value22.92067661926415034816....^[44] In fact, when all the terms containing any particular string of digits (in anybase) are removed, the series converges.^[45]

References

[edit]

^^a ^bRice, Adrian (2011). "The harmonic series: A primer". In Jardine, Dick;Shell-Gellasch, Amy (eds.).Mathematical Time Capsules: Historical Modules for the Mathematics Classroom. MAA Notes. Vol. 77. Washington, DC: Mathematical Association of America. pp. 269–276.ISBN 978-0-88385-984-1.
^^a ^b ^c ^dKullman, David E. (May 2001). "What's harmonic about the harmonic series?".The College Mathematics Journal.32 (3):201–203.doi:10.2307/2687471.JSTOR 2687471.
^Hersey, George L. (2001).Architecture and Geometry in the Age of the Baroque. University of Chicago Press. pp. 11–12,37–51.ISBN 978-0-226-32783-9.
^Oresme, Nicole (c. 1360).Quaestiones super Geometriam Euclidis [Questions concerning Euclid's Geometry] (in Latin).
^Stillwell, John (2010).Mathematics and its History. Undergraduate Texts in Mathematics (3rd ed.). New York: Springer. p. 182.doi:10.1007/978-1-4419-6053-5.ISBN 978-1-4419-6052-8.MR 2667826.
^Derbyshire, John (2003).Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. Washington, DC: Joseph Henry Press. p. 10.ISBN 0-309-08549-7.MR 1968857.
^Mengoli, Pietro (1650)."Praefatio [Preface]".Novae quadraturae arithmeticae, seu De additione fractionum [New arithmetic quadrature (i.e., integration), or On the addition of fractions] (in Latin). Bologna: Giacomo Monti.Mengoli's proof is by contradiction: Let $S {\displaystyle S}$ denote the sum of the series. Group the terms of the series in triplets: $S=1+({\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{4}})+({\tfrac {1}{5}}+{\tfrac {1}{6}}+{\tfrac {1}{7}})+\cdots$ . Since for $x>1$ , ${\tfrac {1}{x-1}}+{\tfrac {1}{x}}+{\tfrac {1}{x+1}}>{\tfrac {3}{x}}$ , then $S>1+{\tfrac {3}{3}}+{\tfrac {3}{6}}+{\tfrac {3}{9}}+\cdots =1+1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\cdots =1+S$ , which is impossible for any finite $S {\displaystyle S}$ . Therefore, the series diverges.
^Bernoulli, Jacob (1689).Propositiones arithmeticae de seriebus infinitis earumque summa finita [Arithmetical propositions about infinite series and their finite sums]. Basel: J. Conrad.
^Bernoulli, Jacob (1713).Ars conjectandi, opus posthumum. Accedit Tractatus de seriebus infinitis [Theory of inference, posthumous work. With the Treatise on infinite series…]. Basel: Thurneysen. pp. 250–251.
From p. 250, prop. 16:
"XVI. Summa serei infinita harmonicè progressionalium, ${\tfrac {1}{1}}+{\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{4}}+{\tfrac {1}{5}}$ &c. est infinita. Id primus deprehendit Frater:…"
[16. The sum of an infinite series of harmonic progression, ${\tfrac {1}{1}}+{\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{4}}+{\tfrac {1}{5}}+\cdots$ , is infinite. My brother first discovered this…]
^^a ^bDunham, William (January 1987). "The Bernoullis and the harmonic series".The College Mathematics Journal.18 (1):18–23.doi:10.1080/07468342.1987.11973001.JSTOR 2686312.
^Bernoulli, Johann (1742)."Corollary III ofDe seriebus varia".Opera Omnia. Lausanne & Basel: Marc-Michel Bousquet & Co. vol. 4, p. 8.Johann Bernoulli's proof is also by contradiction. It uses a telescopic sum to represent each term ${\tfrac {1}{n}}$ as ${\frac {1}{n}}={\Big (}{\frac {1}{n}}-{\frac {1}{n+1}}{\Big )}+{\Big (}{\frac {1}{n+1}}-{\frac {1}{n+2}}{\Big )}+{\Big (}{\frac {1}{n+2}}-{\frac {1}{n+3}}{\Big )}\cdots$ $={\frac {1}{n(n+1)}}+{\frac {1}{(n+1)(n+2)}}+{\frac {1}{(n+2)(n+3)}}\cdots$ Changing the order of summation in the corresponding double series gives, in modern notation $S=\sum _{n=1}^{\infty }{\frac {1}{n}}=\sum _{n=1}^{\infty }\sum _{k=n}^{\infty }{\frac {1}{k(k+1)}}=\sum _{k=1}^{\infty }\sum _{n=1}^{k}{\frac {1}{k(k+1)}}$ $=\sum _{k=1}^{\infty }{\frac {k}{k(k+1)}}=\sum _{k=1}^{\infty }{\frac {1}{k+1}}=S-1$ .
^^a ^bKnuth, Donald E. (1968). "1.2.7 Harmonic numbers".The Art of Computer Programming, Volume I: Fundamental Algorithms (1st ed.). Addison-Wesley. pp. 73–78. Knuth writes, of the partial sums of the harmonic series "This sum does not occur very frequently in classical mathematics, and there is no standard notation for it; but in the analysis of algorithms it pops up nearly every time we turn around, and we will consistently use the symbol $H_{n}$ ... The letter $H {\displaystyle H}$ stands for "harmonic", and we call $H_{n}$ a "harmonic number" because [the infinite series] is customarily called the harmonic series."
^^a ^b ^c ^dKifowit, Steven J.; Stamps, Terra A. (Spring 2006)."The harmonic series diverges again and again"(PDF).AMATYC Review.27 (2). American Mathematical Association of Two-Year Colleges:31–43. See also unpublished addendum, "More proofs of divergence of the harmonic series" by Kifowit.
^Roy, Ranjan (December 2007). "Review ofA Radical Approach to Real Analysis by David M. Bressoud".SIAM Review.49 (4):717–719.JSTOR 20454048.One might point out that Cauchy's condensation test is merely the extension of Oresme's argument for the divergence of the harmonic series
^^a ^bBressoud, David M. (2007).A Radical Approach to Real Analysis. Classroom Resource Materials Series (2nd ed.). Washington, DC: Mathematical Association of America. pp. 137–138.ISBN 978-0-88385-747-2.MR 2284828.
^Boas, R. P. Jr.;Wrench, J. W. Jr. (1971). "Partial sums of the harmonic series".The American Mathematical Monthly.78 (8):864–870.doi:10.1080/00029890.1971.11992881.JSTOR 2316476.MR 0289994.
^^a ^b ^cHavil, Julian (2003)."Chapter 2: The harmonic series".Gamma: Exploring Euler's Constant. Princeton University Press. pp. 21–25.ISBN 978-0-691-14133-6.
^^a ^bOsler, Thomas J. (November 2012). "96.53 Partial sums of series that cannot be an integer".The Mathematical Gazette.96 (537):515–519.doi:10.1017/S0025557200005167.JSTOR 24496876.S2CID 124359670. See in particular Theorem 1, p. 516.
^Sanna, Carlo (2016). "On the $p {\displaystyle p}$ -adic valuation of harmonic numbers".Journal of Number Theory.166:41–46.doi:10.1016/j.jnt.2016.02.020.hdl:2318/1622121.MR 3486261.
^Ross, Bertram (1978). "The psi function".Mathematics Magazine.51 (3):176–179.doi:10.1080/0025570X.1978.11976704.JSTOR 2689999.MR 1572267.
^Sofo, Anthony; Srivastava, H. M. (2015). "A family of shifted harmonic sums".The Ramanujan Journal.37:89–108.doi:10.1007/s11139-014-9600-9.S2CID 254990799.
^^a ^bHadley, John;Singmaster, David (March 1992). "Problems to sharpen the young: An annotated translation ofPropositiones ad acuendos juvenes".The Mathematical Gazette.76 (475):102–126.doi:10.2307/3620384.JSTOR 3620384.S2CID 125835186. See problem 52: De homine patrefamilias – A lord of the manor, pp. 124–125.
^Gale, David (May 1970). "The jeep once more or jeeper by the dozen".The American Mathematical Monthly.77 (5):493–501.doi:10.1080/00029890.1970.11992525.JSTOR 2317382.
^Graham, Ronald;Knuth, Donald E.;Patashnik, Oren (1989). "6.3 Harmonic numbers".Concrete Mathematics (2e ed.).Addison-Wesley. pp. 272–278.ISBN 978-0-201-55802-9.
^^a ^bSharp, R. T. (1954)."Problem 52: Overhanging dominoes"(PDF).Pi Mu Epsilon Journal.1 (10):411–412.
^Paterson, Mike;Peres, Yuval;Thorup, Mikkel;Winkler, Peter;Zwick, Uri (2009). "Maximum overhang".The American Mathematical Monthly.116 (9):763–787.doi:10.4169/000298909X474855.MR 2572086.S2CID 1713091.
^Euler, Leonhard (1737)."Variae observationes circa series infinitas" [Various observations concerning infinite series].Commentarii Academiae Scientiarum Petropolitanae (in Latin).9:160–188.
^^a ^bRubinstein-Salzedo, Simon (2017). "Could Euler have conjectured the prime number theorem?".Mathematics Magazine.90 (5):355–359.arXiv:1701.04718.doi:10.4169/math.mag.90.5.355.JSTOR 10.4169/math.mag.90.5.355.MR 3738242.S2CID 119165483.
^Pollack, Paul (2015). "Euler and the partial sums of the prime harmonic series".Elemente der Mathematik.70 (1):13–20.doi:10.4171/EM/268.MR 3300350.
^Tsang, Kai-Man (2010). "Recent progress on the Dirichlet divisor problem and the mean square of the Riemann zeta-function".Science China.53 (9):2561–2572.Bibcode:2010ScChA..53.2561T.doi:10.1007/s11425-010-4068-6.hdl:10722/129254.MR 2718848.S2CID 6168120.
^Maunsell, F. G. (October 1938). "A problem in cartophily".The Mathematical Gazette.22 (251):328–331.doi:10.2307/3607889.JSTOR 3607889.S2CID 126381029.
^Gerke, Oke (April 2013). "How much is it going to cost me to complete a collection of football trading cards?".Teaching Statistics.35 (2):89–93.doi:10.1111/test.12005.S2CID 119887116.
^Parker, Matt (February 12, 2022)."The coupon collector's problem (with Geoff Marshall)".Stand-up maths. YouTube.
^Luko, Stephen N. (March 2009). "The "coupon collector's problem" and quality control".Quality Engineering.21 (2):168–181.doi:10.1080/08982110802642555.S2CID 109194745.
^Frieze, Alan; Karoński, Michał (2016). "4.1 Connectivity".Introduction to Random Graphs. Cambridge University Press, Cambridge. pp. 64–68.doi:10.1017/CBO9781316339831.ISBN 978-1-107-11850-8.MR 3675279.
^Isaac, Richard (1995). "8.4 The coupon collector's problem solved".The Pleasures of Probability. Undergraduate Texts in Mathematics. New York: Springer-Verlag. pp. 80–82.doi:10.1007/978-1-4612-0819-8.ISBN 0-387-94415-X.MR 1329545.
^Cormen, Thomas H.;Leiserson, Charles E.;Rivest, Ronald L.;Stein, Clifford (2009) [1990]. "Chapter 7: Quicksort".Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 170–190.ISBN 0-262-03384-4.
^Cormen et al. (2009), Section 8.1, "Lower bounds for sorting", pp. 191–193.
^Freniche, Francisco J. (2010)."On Riemann's rearrangement theorem for the alternating harmonic series"(PDF).The American Mathematical Monthly.117 (5):442–448.doi:10.4169/000298910X485969.JSTOR 10.4169/000298910x485969.MR 2663251.S2CID 20575373.
^Soddy, F. (1943)."The three infinite harmonic series and their sums (with topical reference to the Newton and Leibniz series for $\pi$ )".Proceedings of the Royal Society.182 (989):113–129.Bibcode:1943RSPSA.182..113S.doi:10.1098/rspa.1943.0026.MR 0009207.S2CID 202575422.
^Bombieri, E. (2010). "The classical theory of zeta and $L {\displaystyle L}$ -functions".Milan Journal of Mathematics.78 (1):11–59.doi:10.1007/s00032-010-0121-8.MR 2684771.S2CID 120058240.
^Schmuland, Byron (May 2003)."Random harmonic series"(PDF).The American Mathematical Monthly.110 (5):407–416.doi:10.2307/3647827.JSTOR 3647827. Archived fromthe original(PDF) on 2011-06-08. Retrieved2006-08-07.
^Bettin, Sandro; Molteni, Giuseppe; Sanna, Carlo (2018). "Small values of signed harmonic sums".Comptes Rendus Mathématique.356 (11–12):1062–1074.arXiv:1806.05402.Bibcode:2018CRMat.356.1062B.doi:10.1016/j.crma.2018.11.007.hdl:2434/634047.MR 3907571.S2CID 119160796.
^Baillie, Robert (May 1979). "Sums of reciprocals of integers missing a given digit".The American Mathematical Monthly.86 (5):372–374.doi:10.1080/00029890.1979.11994810.JSTOR 2321096.
^Schmelzer, Thomas; Baillie, Robert (June 2008). "Summing a curious, slowly convergent series".The American Mathematical Monthly.115 (6):525–540.doi:10.1080/00029890.2008.11920559.JSTOR 27642532.S2CID 11461182.

External links

[edit]

Wikimedia Commons has media related toHarmonic series (mathematics).

Weisstein, Eric W."Harmonic Series".MathWorld.

Sequences andseries

List of mathematical series

Integer sequences

Basic	Arithmetic progression Geometric progression Harmonic progression Square number Cubic number Factorial Powers of two Powers of three Powers of 10
Advanced(list)	Complete sequence Fibonacci sequence Figurate number Heptagonal number Hexagonal number Lucas number Pell number Pentagonal number Polygonal number Triangular number array

Fibonacci spiral with square sizes up to 34.

Properties of sequences

Properties of series

Series	Alternating Convergent Divergent Telescoping
Convergence	Absolute Conditional Uniform

Explicit series

Convergent	1/2 − 1/4 + 1/8 − 1/16 + ⋯ 1/2 + 1/4 + 1/8 + 1/16 + ⋯ 1/4 + 1/16 + 1/64 + 1/256 + ⋯ 1 + 1/2^s + 1/3^s + ... (Riemann zeta function)
Divergent	1 + 1 + 1 + 1 + ⋯ 1 − 1 + 1 − 1 + ⋯ (Grandi's series) 1 + 2 + 3 + 4 + ⋯ 1 − 2 + 3 − 4 + ⋯ 1 + 2 + 4 + 8 + ⋯ 1 − 2 + 4 − 8 + ⋯ Infinite arithmetic series 1 − 1 + 2 − 6 + 24 − 120 + ⋯ (alternating factorials) 1 + 1/2 + 1/3 + 1/4 + ⋯ (harmonic series) 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ⋯ (inverses of primes)