Harmonic series (mathematics)

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:

$${\displaystyle {\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):

$${\displaystyle {\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), it follows (by the comparison test) that the harmonic series diverges as well. The same argument proves more strongly that, for every positive integer ${\displaystyle k}$,

$${\displaystyle \sum _{n=1}^{2^{k}}{\frac {1}{n}}\geq 1+{\frac {k}{2}}}$$

This is the original proof given by Nicole Oresme in around 1350.[13] The Cauchy condensation test is a generalization of this argument.[14]

Rectangles with area given by the harmonic series, and the hyperbola ${\displaystyle 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 an improper integral. Specifically, consider the arrangement of rectangles shown in the figure to the right. Each rectangle is 1 unit wide and ${\displaystyle {\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 ${\displaystyle y={\tfrac {1}{x}}}$ stays entirely below the upper boundary of the rectangles, so the area under the curve (in the range of ${\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 divergent improper integral,

$${\displaystyle \int _{1}^{\infty }{\frac {1}{x}}\,dx=\infty .}$$

Because this integral does not converge, the sum cannot converge either.[13]

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:

$${\displaystyle \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 function of ${\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 the integral test for convergence.[15]

These numbers grow very slowly, with logarithmic growth, as can be seen from the integral test.[15] More precisely,

$${\displaystyle H_{n}=\ln n+\gamma +{\frac {1}{2n}}-\varepsilon _{n}}$$

where ${\displaystyle \gamma \approx 0.5772}$ is the Euler–Mascheroni constant and ${\displaystyle 0\leq \varepsilon _{n}\leq 1/8n^{2}}$ which approaches 0 as ${\displaystyle n}$ goes to infinity.[16]

No harmonic numbers are integers, except for ${\displaystyle H_{1}=1}$.[17][18] One way to prove that ${\displaystyle H_{n}}$ is not an integer is to consider the highest power of two ${\displaystyle 2^{k}}$ in the range from 1 to ${\displaystyle n}$. If ${\displaystyle M}$ is the least common multiple of the numbers from 1 to ${\displaystyle n}$, then

${\displaystyle H_{k}}$ can be rewritten as a sum of fractions with equal denominators

$${\displaystyle H_{n}=\sum _{i=1}^{n}{\tfrac {M/i}{M}}}$$

in which only one of the numerators, ${\displaystyle M/2^{k}}$, is odd and the rest are even, and (when ${\displaystyle n>1}$) ${\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 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.[18]

Another proof that the harmonic numbers are not integers observes that the denominator of ${\displaystyle H_{n}}$ must be divisible by all prime numbers greater than ${\displaystyle 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 ${\displaystyle H_{1}=1}$, ${\displaystyle H_{2}=1.5}$, and ${\displaystyle H_{6}=2.45}$, 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 on the complex numbers

The digamma function is defined as the logarithmic derivative of the gamma function

$${\displaystyle \psi (x)={\frac {d}{dx}}\ln {\big (}\Gamma (x){\big )}={\frac {\Gamma '(x)}{\Gamma (x)}}.}$$

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 ${\displaystyle \psi (n)=H_{n-1}-\gamma }$.[20] This equation can be used to extend the definition to harmonic numbers with rational indices.[21]

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

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 ${\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 ${\displaystyle {\tfrac {r}{2n}},{\tfrac {r}{2(n-1)}},{\tfrac {r}{2(n-2)}},\dots }$ from the starting point and each other, where ${\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 ${\displaystyle n}$th trip is

$${\displaystyle {\frac {r}{2n}}+{\frac {r}{2(n-1)}}+{\frac {r}{2(n-2)}}+\cdots ={\frac {r}{2}}H_{n},}$$

where ${\displaystyle H_{n}}$ is the ${\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, ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle {\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]

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

In the block-stacking problem, one must place a pile of ${\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 ${\displaystyle {\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 ${\displaystyle {\tfrac {1}{2}}\cdot {\tfrac {1}{2}}}$ 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 ${\displaystyle {\tfrac {1}{2}}\cdot {\tfrac {1}{3}}}$ of its length extending beyond the next lower block, and so on. In this way, it is possible to place the ${\displaystyle n}$ blocks in such a way that they extend ${\displaystyle {\tfrac {1}{2}}H_{n}}$ lengths beyond the table, where ${\displaystyle H_{n}}$ is the ${\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]

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:

$${\displaystyle \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 ${\displaystyle \mathbb {P} }$ denotes the set of prime numbers. 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

$${\displaystyle \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 its Taylor series, and the constant ${\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 that there 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 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.[28]

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 ${\displaystyle n}$, formalized as the average order of the divisor function,

$${\displaystyle {\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 ${\displaystyle {\tfrac {1}{n}}}$ causes this average to differ from the harmonic numbers by a small constant, and Peter Gustav Lejeune Dirichlet showed more precisely that the average number of divisors is ${\displaystyle \ln n+2\gamma -1+O(1/{\sqrt {n}})}$ (expressed in big O notation). Bounding the final error term more precisely remains an open problem, known as Dirichlet's divisor problem.[30]

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 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 ${\displaystyle k}$ items remaining to be collected out of a total of ${\displaystyle n}$ equally-likely items, the probability of collecting a new item in a single random choice is ${\displaystyle k/n}$ and the expected number of random choices needed until a new item is collected is ${\displaystyle n/k}$. Summing over all values of ${\displaystyle k}$ from ${\displaystyle n}$ down to 1 shows that the total expected number of random choices needed to collect all items is ${\displaystyle nH_{n}}$, where ${\displaystyle H_{n}}$ is the ${\displaystyle n}$th harmonic number.[36]

Animation of the average-case version of quicksort, with recursive subproblems indicated by shaded arrows and with pivots (red items and blue lines) chosen as the last item in each subproblem

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 ${\displaystyle x}$ and ${\displaystyle y}$ are separated by ${\displaystyle k}$ other items, then the algorithm will make a comparison between ${\displaystyle x}$ and ${\displaystyle y}$ only when, as the recursion progresses, it picks ${\displaystyle x}$ or ${\displaystyle y}$ as a pivot before picking any of the other ${\displaystyle k}$ items between them. Because each of these ${\displaystyle k+2}$ items is equally likely to be chosen first, this happens with probability ${\displaystyle {\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]

$${\displaystyle \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 the comparison model of sorting used for quicksort, it is not possible to sort in linear time.[38]

The first fourteen partial sums of the alternating harmonic series (black line segments) shown converging to the natural logarithm of 2 (red line).

The series

$${\displaystyle \sum _{n=1}^{\infty }{\frac {(-1)^{n+1}}{n}}=1-{\frac {1}{2}}+{\frac {1}{3}}-{\frac {1}{4}}+{\frac {1}{5}}-\cdots }$$

is known as the alternating harmonic series. It is conditionally convergent by the alternating series test, but not absolutely convergent. Its sum is the natural logarithm of 2.[39]

Using alternating signs with only odd unit fractions produces a related series, the Leibniz formula for π[40]

$${\displaystyle \sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}=1-{\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+\cdots ={\frac {\pi }{4}}.}$$

The Riemann zeta function is defined for real ${\displaystyle x>1}$ by the convergent series

$${\displaystyle \zeta (x)=\sum _{n=1}^{\infty }{\frac {1}{n^{x}}}={\frac {1}{1^{x}}}+{\frac {1}{2^{x}}}+{\frac {1}{3^{x}}}+\cdots ,}$$

which for ${\displaystyle x=1}$ would be the harmonic series. It can be extended by analytic continuation to a holomorphic function on all complex numbers except ${\displaystyle x=1}$, where the extended function has a simple pole. Other important values of the zeta function include ${\displaystyle \zeta (2)=\pi ^{2}/6}$, the solution to the Basel problem, Apéry's constant ${\displaystyle \zeta (3)}$, proved by Roger Apéry to be an irrational number, and the "critical line" of complex numbers with real part ${\displaystyle {\tfrac {1}{2}}}$, conjectured by the Riemann hypothesis to be the only values other than negative integers where the function can be zero.[41]

The random harmonic series is

$${\displaystyle \sum _{n=1}^{\infty }{\frac {s_{n}}{n}},}$$

where the values ${\displaystyle s_{n}}$ are independent and identically distributed random variables that take the two values ${\displaystyle +1}$ and ${\displaystyle -1}$ with equal probability ${\displaystyle {\tfrac {1}{2}}}$. It converges with probability 1, as can be seen by using the Kolmogorov three-series theorem or of the closely related Kolmogorov maximal inequality. The sum of the series is a random variable whose probability density function is close to ${\displaystyle {\tfrac {1}{4}}}$ for values between ${\displaystyle -1}$ and ${\displaystyle 1}$, and decreases to near-zero for values greater than ${\displaystyle 3}$ or less than ${\displaystyle -3}$. Intermediate between these ranges, at the values ${\displaystyle \pm 2}$, the probability density is ${\displaystyle {\tfrac {1}{8}}-\varepsilon }$ for a nonzero but very small value ${\displaystyle \varepsilon <10^{-42}}$.[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.[45]