View source for Harmonic number

{{Use American English|date = March 2019}}
{{Short description|Sum of the first n whole number reciprocals; 1/1 + 1/2 + 1/3 + ... +  1/n}}
{{other uses}}

[[Image:HarmonicNumbers.svg|right|thumb|400px|The harmonic number <math>H_n</math> with <math>n=\lfloor x \rfloor</math> (red line) with its asymptotic limit <math>\gamma+\ln(x)</math> (blue line) where <math>\gamma</math> is the [[Euler–Mascheroni constant]].]]

In [[mathematics]], the {{mvar|n}}-th '''harmonic number''' is the sum of the [[Multiplicative inverse|reciprocals]] of the first {{mvar|n}} [[natural number]]s:

:<math>H_n= 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n} =\sum_{k=1}^n \frac{1}{k}.</math>

Harmonic numbers are related to the [[harmonic mean]] in that the {{mvar|n}}-th harmonic number is also {{mvar|n}} times the reciprocal of the harmonic mean of the first {{mvar|n}} positive integers.

Harmonic numbers have been studied since antiquity and are important in various branches of [[number theory]]. They are sometimes loosely termed [[harmonic series (mathematics)|harmonic series]], are closely related to the [[Riemann zeta function]], and appear in the expressions of various [[special function]]s.

The harmonic numbers roughly approximate the [[natural logarithm|natural logarithm function]]<ref name=ConwayGuy/>{{rp|143}} and thus the associated [[harmonic series (mathematics)|harmonic series]] grows without limit, albeit slowly. In 1737, [[Leonhard Euler]] used the [[Divergence of the sum of the reciprocals of the primes|divergence of the harmonic series]] to provide a new proof of the [[Euclid's theorem|infinity of prime numbers]]. His work was extended into the [[complex plane]] by [[Bernhard Riemann]] in 1859, leading directly to the celebrated [[Riemann hypothesis]] about the [[Prime number theorem|distribution of prime numbers]].

When the value of a large quantity of items has a [[Zipf's law]] distribution, the total value of the {{mvar|n}} most-valuable items is proportional to the {{mvar|n}}-th harmonic number. This leads to a variety of surprising conclusions regarding the [[long tail]] and [[Andrew Odlyzko#Network value|the theory of network value]].

[[Bertrand's postulate]] [[Logical consequence|entails]] that, except for the case {{math|1=''n'' = 1}}, the harmonic numbers are never integers.<ref name = 'ConcreteMath'>{{Cite book
| last1 = Ronald L. | first1 = Graham
| last2 = Donald E. | first2 = Knuth
| last3 = Oren | first3 = Patashnik
| title = Concrete Mathematics
| year = 1994
| publisher = Addison-Wesley
| title-link = Concrete Mathematics
}}</ref>
{| class="wikitable infobox collapsible collapsed" style="line-height:0.8;text-align:left;white-space:nowrap;"
|+ The first 40 harmonic numbers
! rowspan="2" style="padding-top:1em;"|''n'' !! colspan="4"|Harmonic number, ''H<sub>n</sub>''
|-
! colspan="2"|expressed as a fraction !! decimal !! relative size
|-
| style="text-align:right;"|1 || style="text-align:center;" colspan="2"|1 || {{bartable|1||20}}
|-

| style="text-align:right;"|2 || style="border-right:none;padding-right:0;text-align:right;"|3 || style="border-left:none;padding-left:0;"|/2 || {{bartable|1.5||20}}
|-
| style="text-align:right;"|3 || style="border-right:none;padding-right:0;text-align:right;"|11 || style="border-left:none;padding-left:0;"|/6 || ~{{bartable|1.83333||20}}
|-
| style="text-align:right;"|4 || style="border-right:none;padding-right:0;text-align:right;"|25 || style="border-left:none;padding-left:0;"|/12 || ~{{bartable|2.08333||20}}
|-
| style="text-align:right;"|5 || style="border-right:none;padding-right:0;text-align:right;"|137 || style="border-left:none;padding-left:0;"|/60 || ~{{bartable|2.28333||20}}
|-
| style="text-align:right;"|6 || style="border-right:none;padding-right:0;text-align:right;"|49 || style="border-left:none;padding-left:0;"|/20 || {{bartable|2.45||20}}
|-
| style="text-align:right;"|7 || style="border-right:none;padding-right:0;text-align:right;"|363 || style="border-left:none;padding-left:0;"|/140 || ~{{bartable|2.59286||20}}
|-
| style="text-align:right;"|8 || style="border-right:none;padding-right:0;text-align:right;"|761 || style="border-left:none;padding-left:0;"|/280 || ~{{bartable|2.71786||20}}
|-
| style="text-align:right;"|9 || style="border-right:none;padding-right:0;text-align:right;"|7&thinsp;129 || style="border-left:none;padding-left:0;"|/2&thinsp;520 || ~{{bartable|2.82897||20}}
|-
| style="text-align:right;"|10 || style="border-right:none;padding-right:0;text-align:right;"|7&thinsp;381 || style="border-left:none;padding-left:0;"|/2&thinsp;520 || ~{{bartable|2.92897||20}}
|-
| style="text-align:right;"|11 || style="border-right:none;padding-right:0;text-align:right;"|83&thinsp;711 || style="border-left:none;padding-left:0;"|/27&thinsp;720 || ~{{bartable|3.01988||20}}
|-
| style="text-align:right;"|12 || style="border-right:none;padding-right:0;text-align:right;"|86&thinsp;021 || style="border-left:none;padding-left:0;"|/27&thinsp;720 || ~{{bartable|3.10321||20}}
|-
| style="text-align:right;"|13 || style="border-right:none;padding-right:0;text-align:right;"|1&thinsp;145&thinsp;993 || style="border-left:none;padding-left:0;"|/360&thinsp;360 || ~{{bartable|3.18013||20}}
|-
| style="text-align:right;"|14 || style="border-right:none;padding-right:0;text-align:right;"|1&thinsp;171&thinsp;733 || style="border-left:none;padding-left:0;"|/360&thinsp;360 || ~{{bartable|3.25156||20}}
|-
| style="text-align:right;"|15 || style="border-right:none;padding-right:0;text-align:right;"|1&thinsp;195&thinsp;757 || style="border-left:none;padding-left:0;"|/360&thinsp;360 || ~{{bartable|3.31823||20}}
|-
| style="text-align:right;"|16 || style="border-right:none;padding-right:0;text-align:right;"|2&thinsp;436&thinsp;559 || style="border-left:none;padding-left:0;"|/720&thinsp;720 || ~{{bartable|3.38073||20}}
|-
| style="text-align:right;"|17 || style="border-right:none;padding-right:0;text-align:right;"|42&thinsp;142&thinsp;223 || style="border-left:none;padding-left:0;"|/12&thinsp;252&thinsp;240 || ~{{bartable|3.43955||20}}
|-
| style="text-align:right;"|18 || style="border-right:none;padding-right:0;text-align:right;"|14&thinsp;274&thinsp;301 || style="border-left:none;padding-left:0;"|/4&thinsp;084&thinsp;080 || ~{{bartable|3.49511||20}}
|-
| style="text-align:right;"|19 || style="border-right:none;padding-right:0;text-align:right;"|275&thinsp;295&thinsp;799 || style="border-left:none;padding-left:0;"|/77&thinsp;597&thinsp;520 || ~{{bartable|3.54774||20}}
|-
| style="text-align:right;"|20 || style="border-right:none;padding-right:0;text-align:right;"|55&thinsp;835&thinsp;135 || style="border-left:none;padding-left:0;"|/15&thinsp;519&thinsp;504 || ~{{bartable|3.59774||20}}
|-
| style="text-align:right;"|21 || style="border-right:none;padding-right:0;text-align:right;"|18&thinsp;858&thinsp;053 || style="border-left:none;padding-left:0;"|/5&thinsp;173&thinsp;168 || ~{{bartable|3.64536||20}}
|-
| style="text-align:right;"|22 || style="border-right:none;padding-right:0;text-align:right;"|19&thinsp;093&thinsp;197 || style="border-left:none;padding-left:0;"|/5&thinsp;173&thinsp;168 || ~{{bartable|3.69081||20}}
|-
| style="text-align:right;"|23 || style="border-right:none;padding-right:0;text-align:right;"|444&thinsp;316&thinsp;699 || style="border-left:none;padding-left:0;"|/118&thinsp;982&thinsp;864 || ~{{bartable|3.73429||20}}
|-
| style="text-align:right;"|24 || style="border-right:none;padding-right:0;text-align:right;font-size:96%;"|1&thinsp;347&thinsp;822&thinsp;955 || style="border-left:none;padding-left:0;font-size:96%;"|/356&thinsp;948&thinsp;592 || ~{{bartable|3.77596||20}}
|-
| style="text-align:right;"|25 || style="border-right:none;padding-right:0;text-align:right;font-size:87%;"|34&thinsp;052&thinsp;522&thinsp;467 || style="border-left:none;padding-left:0;font-size:87%;"|/8&thinsp;923&thinsp;714&thinsp;800 || ~{{bartable|3.81596||20}}
|-
| style="text-align:right;"|26 || style="border-right:none;padding-right:0;text-align:right;font-size:87%;"|34&thinsp;395&thinsp;742&thinsp;267 || style="border-left:none;padding-left:0;font-size:87%;"|/8&thinsp;923&thinsp;714&thinsp;800 || ~{{bartable|3.85442||20}}
|-
| style="text-align:right;"|27 || style="border-right:none;padding-right:0;text-align:right;font-size:80%;"|312&thinsp;536&thinsp;252&thinsp;003 || style="border-left:none;padding-left:0;font-size:80%;"|/80&thinsp;313&thinsp;433&thinsp;200 || ~{{bartable|3.89146||20}}
|-
| style="text-align:right;"|28 || style="border-right:none;padding-right:0;text-align:right;font-size:80%;"|315&thinsp;404&thinsp;588&thinsp;903 || style="border-left:none;padding-left:0;font-size:80%;"|/80&thinsp;313&thinsp;433&thinsp;200 || ~{{bartable|3.92717||20}}
|-
| style="text-align:right;"|29 || style="border-right:none;padding-right:0;text-align:right;font-size:73%;"|9&thinsp;227&thinsp;046&thinsp;511&thinsp;387 || style="border-left:none;padding-left:0;font-size:73%;"|/2&thinsp;329&thinsp;089&thinsp;562&thinsp;800 || ~{{bartable|3.96165||20}}
|-
| style="text-align:right;"|30 || style="border-right:none;padding-right:0;text-align:right;font-size:73%;"|9&thinsp;304&thinsp;682&thinsp;830&thinsp;147 || style="border-left:none;padding-left:0;font-size:73%;"|/2&thinsp;329&thinsp;089&thinsp;562&thinsp;800 || ~{{bartable|3.99499||20}}
|-
| style="text-align:right;"|31 || style="border-right:none;padding-right:0;text-align:right;font-size:64%;"|290&thinsp;774&thinsp;257&thinsp;297&thinsp;357 || style="border-left:none;padding-left:0;font-size:64%;"|/72&thinsp;201&thinsp;776&thinsp;446&thinsp;800 || ~{{bartable|4.02725||20}}
|-
| style="text-align:right;"|32 || style="border-right:none;padding-right:0;text-align:right;font-size:64%;"|586&thinsp;061&thinsp;125&thinsp;622&thinsp;639 || style="border-left:none;padding-left:0;font-size:64%;"|/144&thinsp;403&thinsp;552&thinsp;893&thinsp;600 || ~{{bartable|4.05850||20}}
|-
| style="text-align:right;"|33 || style="border-right:none;padding-right:0;text-align:right;font-size:68%;"|53&thinsp;676&thinsp;090&thinsp;078&thinsp;349 || style="border-left:none;padding-left:0;font-size:68%;"|/13&thinsp;127&thinsp;595&thinsp;717&thinsp;600 || ~{{bartable|4.08880||20}}
|-
| style="text-align:right;"|34 || style="border-right:none;padding-right:0;text-align:right;font-size:68%;"|54&thinsp;062&thinsp;195&thinsp;834&thinsp;749 || style="border-left:none;padding-left:0;font-size:68%;"|/13&thinsp;127&thinsp;595&thinsp;717&thinsp;600 || ~{{bartable|4.11821||20}}
|-
| style="text-align:right;"|35 || style="border-right:none;padding-right:0;text-align:right;font-size:68%;"|54&thinsp;437&thinsp;269&thinsp;998&thinsp;109 || style="border-left:none;padding-left:0;font-size:68%;"|/13&thinsp;127&thinsp;595&thinsp;717&thinsp;600 || ~{{bartable|4.14678||20}}
|-
| style="text-align:right;"|36 || style="border-right:none;padding-right:0;text-align:right;font-size:68%;"|54&thinsp;801&thinsp;925&thinsp;434&thinsp;709 || style="border-left:none;padding-left:0;font-size:68%;"|/13&thinsp;127&thinsp;595&thinsp;717&thinsp;600 || ~{{bartable|4.17456||20}}
|-
| style="text-align:right;"|37 || style="border-right:none;padding-right:0;text-align:right;font-size:60%;"|2&thinsp;040&thinsp;798&thinsp;836&thinsp;801&thinsp;833 || style="border-left:none;padding-left:0;font-size:60%;"|/485&thinsp;721&thinsp;041&thinsp;551&thinsp;200 || ~{{bartable|4.20159||20}}
|-
| style="text-align:right;"|38 || style="border-right:none;padding-right:0;text-align:right;font-size:60%;"|2&thinsp;053&thinsp;580&thinsp;969&thinsp;474&thinsp;233 || style="border-left:none;padding-left:0;font-size:60%;"|/485&thinsp;721&thinsp;041&thinsp;551&thinsp;200 || ~{{bartable|4.22790||20}}
|-
| style="text-align:right;"|39 || style="border-right:none;padding-right:0;text-align:right;font-size:60%;"|2&thinsp;066&thinsp;035&thinsp;355&thinsp;155&thinsp;033 || style="border-left:none;padding-left:0;font-size:60%;"|/485&thinsp;721&thinsp;041&thinsp;551&thinsp;200 || ~{{bartable|4.25354||20}}
|-
| style="text-align:right;"|40 || style="border-right:none;padding-right:0;text-align:right;font-size:60%;"|2&thinsp;078&thinsp;178&thinsp;381&thinsp;193&thinsp;813 || style="border-left:none;padding-left:0;font-size:60%;"|/485&thinsp;721&thinsp;041&thinsp;551&thinsp;200 || ~{{bartable|4.27854||20}}
|}
<!-- Python script to generate n from 2 to 40:
import fractions
numerator = 1; denominator = 1
for i in range(2, 40 + 1):
 numerator = numerator * i + denominator; denominator *= i; gcd = fractions.gcd(numerator, denominator); numerator /= gcd; denominator /= gcd
 decimal   = ('{}' if (i < 3 or i == 6) else '{:.5f}').format(float(numerator) / denominator); exact = '' if (i < 3 or i == 6) else '~'
 numerator_length = len(str(numerator)); size = '' if (numerator_length <= 9) else 'font-size:{:d}%;'.format(960 / numerator_length)
 print('|-\n| style="text-align:right;"|{} || style="border-right:none;padding-right:0;text-align:right;{}"|{:,} || style="border-left:none;padding-left:0;{}"|/{:,} || {}{{{{bartable|{}||20}}}}'.
       format(i, size, numerator, size, denominator, exact, decimal).replace(',', '&thinsp;'))
-->

==Identities involving harmonic numbers==
By definition, the harmonic numbers satisfy the [[recurrence relation]]
:<math>H_{n + 1} = H_{n} + \frac{1}{n + 1}.</math>

The harmonic numbers are connected to the [[Stirling numbers of the first kind]] by the relation
: <math> H_n = \frac{1}{n!}\left[{n+1 \atop 2}\right]. </math>

The functions
:<math>f_n(x)=\frac{x^n}{n!}(\log x-H_n)</math>
satisfy the property
:<math>f_n'(x)=f_{n-1}(x).</math>
In particular
:<math> f_1(x)=x(\log x-1)</math>
is an integral of the logarithmic function.{{cn|date=January 2019}}

The harmonic numbers satisfy the series identity
:<math>\sum_{k=1}^n H_k = (n+1)(H_{n+1} - 1).</math>

===Identities involving {{pi}}===

There are several infinite summations involving harmonic numbers and powers of [[π|{{pi}}]]:<ref>Sondow, Jonathan and Weisstein, Eric W. "Harmonic Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/HarmonicNumber.html</ref>

:<math>\sum_{n=1}^\infty \frac{H_n}{n\cdot 2^n}=\frac{1}{12}\pi ^2</math>

:<math>\sum_{n=1}^\infty \frac{H_n^2}{(n+1)^2}=\frac{11}{360}\pi^4</math>

:<math>\sum_{n=1}^\infty \frac{H_n^2}{n^2}=\frac{17}{360}\pi^4</math>

:<math>\sum_{n=1}^\infty \frac{H_n}{n^3}=\frac{1}{72}\pi^4</math>

==Calculation==
An integral representation given by [[Euler]]<ref>{{citation|title=How Euler Did It|series=MAA Spectrum|first=C. Edward|last=Sandifer|publisher=Mathematical Association of America|year=2007|isbn=9780883855638|page=206|url=https://books.google.com/books?id=sohHs7ExOsYC&pg=PA206}}.</ref> is

: <math> H_n = \int_0^1 \frac{1 - x^n}{1 - x}\,dx. </math>

The equality above is straightforward by the simple [[algebraic identity]]

:<math>\frac{1-x^n}{1-x}=1+x+\cdots +x^{n-1}.</math>

Using the substitution {{math|1=''x'' = 1 &minus; ''u''}}, another expression for {{math|''H''<sub>''n''</sub>}} is
:<math>\begin{align}
H_n &= \int_0^1 \frac{1 - x^n}{1 - x}\,dx = \int_0^1\frac{1-(1-u)^n}{u}\,du \\[6pt]
&= \int_0^1\left[-\sum_{k=1}^n(-1)^k \binom nk u^{k-1}\right]\,du 
= -\sum_{k=1}^n (-1)^k\binom nk \int_0^1u^{k-1}\,du \\[6pt]
&= -\sum_{k=1}^n(-1)^k\frac{1}{k}\binom nk .
\end{align}
</math>

A closed form expression for {{math|''H''<sub>''n''</sub>}} is

:<math> H_n = G_n-(n+1)\left\lfloor\frac{G_n}{n+1}\right\rfloor,</math>
where 
:<math>G_n = \frac{{n+(n+1)! \choose n}-1}{(n+1)!}.</math>

[[File:Integral Test.svg|thumb|Graph demonstrating a connection between harmonic numbers and the [[natural logarithm]]. The harmonic number {{math|''H''<sub>''n''</sub>}} can be interpreted as a [[Riemann sum]] of the integral: <math>\int_1^{n+1} \frac{dx}{x} = \ln(n+1).</math>]]
The {{mvar|n}}th harmonic number is about as large as the [[natural logarithm]] of {{mvar|n}}. The reason is that the sum is approximated by the [[integral]]

:<math>\int_1^n \frac{1}{x}\, dx,</math>

whose value is {{math|ln ''n''}}.

The values of the sequence {{math|''H''<sub>''n''</sub> − ln ''n''}} decrease monotonically towards the [[Limit of a sequence|limit]]

:<math> \lim_{n \to \infty} \left(H_n - \ln n\right) = \gamma,</math>

where {{math|''γ'' ≈ 0.5772156649}} is the [[Euler–Mascheroni constant]]. The corresponding [[asymptotic expansion]] is

:<math>\begin{align}
   H_n &\sim \ln{n}+\gamma+\frac{1}{2n}-\sum_{k=1}^\infty \frac{B_{2k}}{2k n^{2k}}\\
   &=\ln{n}+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\cdots,
 \end{align}</math>

where {{math|''B''<sub>''k''</sub>}} are the [[Bernoulli numbers]].

==Generating functions==
A [[generating function]] for the harmonic numbers is

:<math>\sum_{n=1}^\infty z^n H_n = \frac {-\ln(1-z)}{1-z},</math>

where ln(''z'') is the [[natural logarithm]]. An exponential generating function is

:<math>\sum_{n=1}^\infty \frac {z^n}{n!} H_n = -e^z \sum_{k=1}^\infty \frac{1}{k} \frac {(-z)^k}{k!} = e^z \operatorname{Ein}(z)</math>

where Ein(''z'') is the entire [[exponential integral]]. Note that

:<math>\operatorname{Ein}(z) = \mathrm{E}_1(z) + \gamma + \ln z = \Gamma (0,z) + \gamma + \ln z</math>

where Γ(0, ''z'') is the [[incomplete gamma function]].

== Arithmetic properties ==
The harmonic numbers have several interesting arithmetic properties. It is well-known that <math display="inline">H_n</math> is an integer [[if and only if]] <math display="inline">n=1</math>, a result often attributed to Taeisinger.<ref>{{Cite book|title=CRC Concise Encyclopedia of Mathematics|last=Weisstein|first=Eric W.|publisher=Chapman & Hall/CRC|year=2003|isbn=978-1-58488-347-0|location=Boca Raton, FL|pages=3115|quote=|via=}}</ref> Indeed, using [[P-adic order|2-adic valuation]], it is not difficult to prove that for <math display="inline">n \ge 2</math> the numerator of <math display="inline">H_n</math> is an odd number while the denominator of <math display="inline">H_n</math> is an even number. More precisely,

:<math>H_n=\frac{1}{2^{\lfloor\log_2(n)\rfloor}}\frac{a_n}{b_n}</math>

with some odd integers <math display="inline">a_n</math> and <math display="inline">b_n</math>.

As a consequence of [[Wolstenholme's theorem]], for any prime number <math>p \ge 5</math> the numerator of <math>H_{p-1}</math>is divisible by <math display="inline">p^2</math>. Furthermore, Eisenstein<ref>{{Cite journal|last=Eisenstein|first=Ferdinand Gotthold Max|year=1850|title=Eine neue Gattung zahlentheoretischer Funktionen, welche von zwei Elementen ahhängen und durch gewisse lineare Funktional-Gleichungen definirt werden|url=|journal=Berichte Königl. Preuβ. Akad. Wiss. Berlin|volume=15|pages=36–42|via=}}</ref> proved that for all odd prime number <math display="inline">p</math> it holds
:<math>H_{(p-1)/2} \equiv -2q_p(2) \pmod p</math>
where <math display="inline">q_p(2) = (2^{p-1}  -1)/p</math> is a [[Fermat quotient]], with the consequence that <math display="inline">p</math> divides the numerator of <math>H_{(p-1)/2}</math> if and only if <math display="inline">p</math> is a [[Wieferich prime]].

In 1991, Eswarathasan and Levine<ref>{{Cite journal|last=Eswarathasan|first=Arulappah|last2=Levine|first2=Eugene|year=1991|title=p-integral harmonic sums|url=|journal=Discrete Mathematics|volume=91|issue=3|pages=249–257|doi=10.1016/0012-365X(90)90234-9|via=}}</ref> defined <math>J_p</math> as the set of all positive integers <math>n</math> such that the numerator of <math>H_n</math> is divisible by a prime number <math>p.</math> They proved that
:<math>\{p-1,p^2-p,p^2-1\}\subseteq J_p</math>
for all prime numbers <math>p \ge 5,</math> and they defined ''harmonic primes'' to be the primes <math display="inline">p</math> such that <math>J(p)</math> has exactly 3 elements.

Eswarathasan and Levine also conjectured that <math>J_p</math> is a [[finite set]] for all primes <math>p,</math> and that there are infinitely many harmonic primes. Boyd<ref>{{Cite journal|last=Boyd|first=David W.|year=1994|title=A p-adic study of the partial sums of the harmonic series|url=http://projecteuclid.org/euclid.em/1048515811|journal=Experimental Mathematics|volume=3|issue=4|pages=287–302|via=|doi=10.1080/10586458.1994.10504298|citeseerx=10.1.1.56.7026}}</ref> verified that <math>J_p</math> is finite for all prime numbers up to <math>p = 547</math> except 83, 127, and 397; and he gave an heuristic suggesting that the [[Natural density|density]] of the harmonic primes in the set of all primes should be <math>1/e</math>. Sanna<ref>{{Cite journal|last=Sanna|first=Carlo|year=2016|title=On the p-adic valuation of harmonic numbers|journal=Journal of Number Theory|volume=166|pages=41–46|doi=10.1016/j.jnt.2016.02.020|hdl=2318/1622121|url=https://iris.unito.it/bitstream/2318/1622121/1/padicharm.pdf}}</ref> showed that <math>J_p</math> has zero [[Natural density|asymptotic density]], while Bing-Ling Wu and Yong-Gao Chen<ref>{{Cite journal|last=Chen|first=Yong-Gao|last2=Wu|first2=Bing-Ling|year=2017|title=On certain properties of harmonic numbers|journal=Journal of Number Theory|volume=175|pages=66–86|doi=10.1016/j.jnt.2016.11.027}}</ref> proved that the number of elements of <math>J_p</math> not exceeding <math>x</math> is at most <math>3x^{\frac{2}{3}+\frac1{25 \log p}}</math>, for all <math>x \geq 1</math>.

==Applications==
The harmonic numbers appear in several calculation formulas, such as the [[digamma function]]

:<math> \psi(n) = H_{n-1} - \gamma.</math>

This relation is also frequently used to define the extension of the harmonic numbers to non-integer ''n''. The harmonic numbers are also frequently used to define {{mvar|γ}} using the limit introduced earlier:

:<math> \gamma = \lim_{n \rightarrow \infty}{\left(H_n - \ln(n)\right)}, </math>

although

:<math> \gamma = \lim_{n \to \infty}{\left(H_n - \ln\left(n+\frac{1}{2}\right)\right)} </math>

converges more quickly.

In 2002, [[Jeffrey Lagarias]] proved<ref>{{cite journal |author=Jeffrey Lagarias |title=An Elementary Problem Equivalent to the Riemann Hypothesis |journal=Amer. Math. Monthly |volume=109 |issue=6 |year=2002 |pages=534–543 |arxiv=math.NT/0008177 |doi=10.2307/2695443|jstor=2695443 }}</ref> that the [[Riemann hypothesis]] is equivalent to the statement that

:<math> \sigma(n) \le H_n + (\log H_n)e^{H_n},</math>

is true for every [[integer]] {{math|''n'' ≥ 1}} with strict inequality if {{math|''n'' > 1}}; here {{math|''σ''(''n'')}} denotes the [[divisor function|sum of the divisors]] of {{mvar|n}}.

The eigenvalues of the nonlocal problem

:<math> \lambda \varphi(x) = \int_{-1}^{1} \frac{\varphi(x)-\varphi(y)}{|x-y|} \, dy </math>

are given by <math>\lambda = 2H_n</math>, where by convention, <math>H_0 = 0.</math>

==Generalizations==

===Generalized harmonic numbers===
The '''generalized harmonic number''' of order ''m'' of ''n'' is given by

:<math>H_{n,m}=\sum_{k=1}^n \frac{1}{k^m}.</math>

Other notations occasionally used include

:<math>H_{n,m}= H_n^{(m)} = H_m(n).</math>

The special case of ''m'' = 0 gives <math>H_{n,0}= n.</math>  The special case of ''m'' = 1 is simply called a harmonic number and is frequently written without the ''m'', as

:<math>H_n= \sum_{k=1}^n \frac{1}{k}.</math>

The limit as {{math|''n'' → ∞}} is finite if {{math|''m'' > 1}}, with the generalized harmonic number bounded by and converging to the [[Riemann zeta function]]

:<math>\lim_{n\rightarrow \infty} H_{n,m} = \zeta(m).</math>

The smallest natural number ''k'' such that ''k<sup>n</sup>'' does not divide the denominator of generalized harmonic number ''H''(''k'', ''n'') nor the denominator of alternating generalized harmonic number ''H′''(''k'', ''n'') is, for ''n''=1, 2, ... :
:77, 20, 94556602, 42, 444, 20, 104, 42, 76, 20, 77, 110, 3504, 20, 903, 42, 1107, 20, 104, 42, 77, 20, 2948, 110, 136, 20, 76, 42, 903, 20, 77, 42, 268, 20, 7004, 110, 1752, 20, 19203, 42, 77, 20, 104, 42, 76, 20, 370, 110, 1107, 20, ... {{OEIS|id=A128670}}

The related sum <math>\sum_{k=1}^n k^m</math> occurs in the study of [[Bernoulli number]]s; the harmonic numbers also appear in the study of [[Stirling number]]s.

Some integrals of generalized harmonic numbers are

:<math>\int_0^a H_{x,2} \, dx = a \frac {\pi^2}{6}-H_{a}</math>

and

:<math>\int_0^a H_{x,3} \, dx = a A - \frac {1}{2} H_{a,2},</math> where ''A'' is [[Apéry's constant]], i.e. ''ζ''(3).

and

:<math>\sum_{k=1}^n H_{k,m}=(n+1)H_{n,m}- H_{n,m-1} \text{ for } m \geq 0 </math>

Every generalized harmonic number of order m can be written as a function of harmonic of order m-1 using:

:<math>H_{n,m} = \sum_{k=1}^{n-1} \frac {H_{k,m-1}}{k(k+1)} + \frac {H_{n,m-1}}{n} </math> &nbsp; for example: <math>H_{4,3} = \frac {H_{1,2}}{1 \cdot 2} + \frac {H_{2,2}}{2 \cdot 3} + \frac {H_{3,2}}{3 \cdot 4} + \frac {H_{4,2}}{4} </math>

A [[generating function]] for the generalized harmonic numbers is

:<math>\sum_{n=1}^\infty z^n H_{n,m} = \frac {\operatorname{Li}_m(z)}{1-z},</math>

where <math>\operatorname{Li}_m(z)</math> is the [[polylogarithm]], and {{math|{{mabs|''z''}} < 1}}. The generating function given above for {{math|1=''m'' = 1}} is a special case of this formula.

A '''fractional argument for generalized harmonic numbers''' can be introduced as follows:

For every <math>p,q>0</math> integer, and <math>m>1</math> integer or not, we have from polygamma functions:
:<math>H_{q/p,m}=\zeta(m)-p^m\sum_{k=1}^\infty \frac{1}{(q+pk)^m}</math>

where <math>\zeta(m)</math> is the [[Riemann zeta function]]. The relevant recurrence relation is:
:<math>H_{a,m}=H_{a-1,m}+\frac{1}{a^m}</math>
Some special values are:
:<math>H_{\frac{1}{4},2}=16-8G-\tfrac{5}{6}\pi^2</math> where ''G'' is [[Catalan's constant]]
:<math>H_{\frac{1}{2},2}=4-\tfrac{\pi^2}{3}</math>
:<math>H_{\frac{3}{4},2}=8G+\tfrac{16}{9}-\tfrac{5}{6}\pi^2</math>
:<math>H_{\frac{1}{4},3}=64-27\zeta(3)-\pi^3</math>
:<math>H_{\frac{1}{2},3}=8-6\zeta(3)</math>
:<math>H_{\frac{3}{4},3}={(\tfrac{4}{3})}^3-27\zeta(3)+\pi^3</math>

In the special case that <math>p = 1</math>, we get

:<math>H_{n,m}=\zeta(m, 1) - \zeta(m, n)</math>, 

:where <math>\zeta(m, n)</math> is the [[Hurwitz zeta function]]. This relationship is used to calculate harmonic numbers numerically.

===Multiplication formulas===
The [[multiplication theorem]] applies to harmonic numbers. Using [[polygamma]] functions, we obtain

:<math>H_{2x}=\frac{1}{2}\left(H_x+H_{x-\frac{1}{2}}\right)+\ln 2</math>
:<math>H_{3x}=\frac{1}{3}\left(H_x+H_{x-\frac{1}{3}}+H_{x-\frac{2}{3}}\right)+\ln 3,</math>

or, more generally,

:<math>H_{nx}=\frac{1}{n}\left(H_x+H_{x-\frac{1}{n}}+H_{x-\frac{2}{n}}+\cdots +H_{x-\frac{n-1}{n}} \right) + \ln n.</math>

For generalized harmonic numbers, we have

:<math>H_{2x,2}=\frac{1}{2}\left(\zeta(2)+\frac{1}{2}\left(H_{x,2}+H_{x-\frac{1}{2},2}\right)\right)</math>
:<math>H_{3x,2}=\frac{1}{9}\left(6\zeta(2)+H_{x,2}+H_{x-\frac{1}{3},2}+H_{x-\frac{2}{3},2}\right),</math>

where <math>\zeta(n)</math> is the [[Riemann zeta function]].

===Hyperharmonic numbers===

The next generalization was discussed by [[John Horton Conway|J. H. Conway]] and [[Richard K. Guy|R. K. Guy]] in their 1995 book ''[[The Book of Numbers (maths)|The Book of Numbers]]''.<ref name=ConwayGuy/>{{rp|258}} Let

: <math> H_n^{(0)} = \frac1n. </math>

Then the nth [[hyperharmonic number]] of order ''r'' (''r>0'') is defined recursively as

: <math> H_n^{(r)} = \sum_{k=1}^n H_k^{(r-1)}. </math>

In particular, <math>H_n^{(1)}</math> is the ordinary harmonic number <math>H_n</math>.

==Harmonic numbers for real and complex values==
{{uncited section|date=May 2019}}
The formulae given above,
:<math>H_x = \int_0^1 \frac{1-t^x}{1-t} \, dt= -\sum_{k=1}^\infty {x \choose k} \frac{(-1)^k}{k}</math>
are an integral and a series representation for a function that interpolates the harmonic numbers and, via [[analytic continuation]], extends the definition to the complex plane other than the negative integers ''x''. The interpolating function is in fact closely related to the [[digamma function]]

:<math>H_x = \psi(x+1)+\gamma,</math>

where {{math|''ψ''(''x'')}} is the digamma, and {{math|''γ''}} is the Euler-Mascheroni constant. The integration process may be repeated to obtain

:<math>H_{x,2}=-\sum_{k=1}^\infty \frac {(-1)^k}{k} {x \choose k} H_k.</math>

The [[Taylor series]] for the harmonic numbers is
:<math>H_x=\sum_{k=2}^\infty (-1)^{k}\zeta (k)\;x^{k-1}\quad\text{ for } |x| < 1</math>
which comes from the Taylor series for the digamma function.

=== Alternative, asymptotic formulation ===
When seeking to approximate&nbsp;{{math|''H''{{sub|''x''}}}} for a complex number&nbsp;{{math|''x''}}, it is effective to first compute&nbsp;{{math|''H''{{sub|''m''}}}} for some large integer&nbsp;{{math|''m''}}.  Use that to approximate a value for&nbsp;{{math|''H''{{sub|''m''+''x''}}}} and then use the recursion relation {{math|1=''H''{{sub|''n''}} = ''H''{{sub|''n''−1}} + 1/''n''}} backwards&nbsp;{{math|''m''}} times, to unwind it to an approximation for&nbsp;{{math|''H''{{sub|''x''}}}}.  Furthermore, this approximation is exact in the limit as&nbsp;{{math|''m''}} goes to infinity.

Specifically, for a fixed integer&nbsp;{{math|''n''}}, it is the case that
:<math>\lim_{m \rightarrow \infty} \left[H_{m+n} - H_m\right] = 0 \,,</math>

If&nbsp;{{math|''n''}} is not an integer then it is not possible to say whether this equation is true because we have not yet (in this section) defined harmonic numbers for non-integers.  However, we do get a unique extension of the harmonic numbers to the non-integers by insisting that this equation continue to hold when the arbitrary integer&nbsp;{{math|''n''}} is replaced by an arbitrary complex number&nbsp;{{math|''x''}}.

:<math>\lim_{m \rightarrow \infty} \left[H_{m+x} - H_m\right] = 0 \,,</math>
Swapping the order of the two sides of this equation and then subtracting them from&nbsp;{{math|''H''<sub>''x''</sub>}} gives
:<math>
\begin{align}H_x &= \lim_{m \rightarrow \infty} \left[H_m - (H_{m+x}-H_x)\right] \\[6pt]
&= \lim_{m \rightarrow \infty} \left[\left(\sum_{k=1}^m \frac{1}{k}\right) - \left(\sum_{k=1}^m \frac{1}{x+k}\right) \right] \\[6pt]
&= \lim_{m \rightarrow \infty} \sum_{k=1}^m \left(\frac{1}{k} - \frac{1}{x+k}\right) = x \sum_{k=1}^{\infty} \frac{1}{k(x+k)}\, .
\end{align}
</math>

This [[infinite series]] converges for all complex numbers&nbsp;{{math|''x''}} except the negative integers, which fail because trying to use the recursion relation {{math|1=''H''{{sub|''n''}} = ''H''{{sub|''n''−1}} + 1/''n''}} backwards through the value&nbsp;{{math|1=''n'' = 0}} involves a division by zero.  By this construction, the function that defines the harmonic number for complex values is the unique function that simultaneously satisfies (1) {{math|1=''H''{{sub|0}} = 0}}, (2) {{math|1=''H''{{sub|''x''}} = ''H''{{sub|''x''−1}} + 1/''x''}} for all complex numbers&nbsp;{{math|''x''}} except the non-positive integers, and (3) {{math|1=lim<sub>''m''→+∞</sub> (''H''<sub>''m''+''x''</sub> − ''H''<sub>''m''</sub>) = 0}} for all complex values&nbsp;{{math|''x''}}.

Note that this last formula can be used to show that:
:<math> \int_0^1 H_x \, dx = \gamma\,, </math>
where&nbsp;{{math|''γ''}} is the [[Euler–Mascheroni constant]] or, more generally, for every&nbsp;{{math|''n''}} we have:
:<math> \int_0^nH_{x}\,dx = n\gamma+\ln{(n!)}\, .</math>

===Special values for fractional arguments===
There are the following special analytic values for fractional arguments between 0 and 1, given by the integral

:<math>H_\alpha = \int_0^1\frac{1-x^\alpha}{1-x}\,dx\, .</math>

More values may be generated from the recurrence relation

:<math> H_\alpha = H_{\alpha-1}+\frac{1}{\alpha}\,,</math>

or from the reflection relation

:<math> H_{1-\alpha}-H_\alpha = \pi\cot{(\pi\alpha)}-\frac{1}{\alpha}+\frac{1}{1-\alpha}\, .</math>

For example:

: <math> H_{\frac{1}{2}} = 2 -2\ln{2}</math>
: <math> H_{\frac{1}{3}} = 3-\tfrac{\pi}{2\sqrt{3}} -\tfrac{3}{2}\ln{3}</math>
: <math> H_{\frac{2}{3}} = \tfrac{3}{2}(1-\ln{3})+\sqrt{3}\tfrac{\pi}{6}</math>
: <math> H_{\frac{1}{4}} = 4-\tfrac{\pi}{2} - 3\ln{2}</math>
: <math> H_{\frac{3}{4}} = \tfrac{4}{3}-3\ln{2}+\tfrac{\pi}{2}</math>
: <math> H_{\frac{1}{6}} = 6-\tfrac{\pi}{2} \sqrt{3} -2\ln{2} -\tfrac{3}{2} \ln{3}</math>
: <math> H_{\frac{1}{8}} = 8-\tfrac{\pi}{2} - 4\ln{2} - \tfrac{1}{\sqrt{2}} \left\{\pi + \ln\left(2 + \sqrt{2}\right) - \ln\left(2 - \sqrt{2}\right)\right\}</math>
: <math> H_{\frac{1}{12}} = 12-3\left(\ln{2}+\tfrac{\ln{3}}{2}\right)-\pi\left(1+\tfrac{\sqrt{3}}{2}\right)+2\sqrt{3}\ln \left (\sqrt{2-\sqrt{3}} \right )</math>

For positive integers ''p'' and ''q'' with ''p'' < ''q'', we have:
: <math> H_{\frac{p}{q}} = \frac{q}{p} +2\sum_{k=1}^{\lfloor\frac{q-1}{2}\rfloor} \cos\left(\frac{2 \pi pk}{q}\right)\ln\left({\sin \left(\frac{\pi k}{q}\right)}\right)-\frac{\pi}{2}\cot\left(\frac{\pi p}{q}\right)-\ln\left(2q\right)</math>

===Relation to the Riemann zeta function===
Some derivatives of fractional harmonic numbers are given by:

:<math>
\begin{align}
\frac{d^n H_x}{dx^n} & = (-1)^{n+1}n!\left[\zeta(n+1)-H_{x,n+1}\right] \\[6pt]
\frac{d^n H_{x,2}}{dx^n} & = (-1)^{n+1}(n+1)!\left[\zeta(n+2)-H_{x,n+2}\right] \\[6pt]
\frac{d^n H_{x,3}}{dx^n} & = (-1)^{n+1}\frac{1}{2}(n+2)!\left[\zeta(n+3)-H_{x,n+3}\right].
\end{align}
</math>

And using [[Taylor series|Maclaurin series]], we have for ''x'' < 1:

:<math>
\begin{align}
H_x & = \sum_{n=1}^\infty (-1)^{n+1}x^n\zeta(n+1) \\[5pt]
H_{x,2} & = \sum_{n=1}^\infty (-1)^{n+1}(n+1)x^n\zeta(n+2) \\[5pt]
H_{x,3} & = \frac{1}{2}\sum_{n=1}^\infty (-1)^{n+1}(n+1)(n+2)x^n\zeta(n+3).
\end{align}
</math>

For fractional arguments between 0 and 1, and for ''a'' > 1:

:<math>
\begin{align}
H_{1/a} & = \frac{1}{a}\left(\zeta(2)-\frac{1}{a}\zeta(3)+\frac{1}{a^2}\zeta(4)-\frac{1}{a^3} \zeta(5) + \cdots\right) \\[6pt]
H_{1/a, \, 2} & = \frac{1}{a}\left(2\zeta(3)-\frac{3}{a}\zeta(4)+\frac{4}{a^2}\zeta(5)-\frac{5}{a^3} \zeta(6) + \cdots\right) \\[6pt]
H_{1/a, \, 3} & = \frac{1}{2a}\left(2\cdot3\zeta(4)-\frac{3\cdot4}{a}\zeta(5)+\frac{4\cdot5}{a^2}\zeta(6)-\frac{5\cdot6}{a^3}\zeta(7)+\cdots\right).
\end{align}
</math>

==See also==
* [[Watterson estimator]]
* [[Tajima's D]]
* [[Coupon collector's problem]]
* [[Jeep problem]]
* [[Riemann zeta function]]
* [[List of sums of reciprocals]]

==Notes==
{{reflist|refs=
<ref name=ConwayGuy>
{{Cite book
| last1 = John H. | first1 = Conway
| last2 = Richard K. | first2 = Guy
| title = The book of numbers
| year = 1995
| publisher = Copernicus
}}</ref>
}}

==References==
* {{cite journal |author1=Arthur T. Benjamin |author2=Gregory O. Preston |author3=Jennifer J. Quinn |url=http://www.math.hmc.edu/~benjamin/papers/harmonic.pdf |title=A Stirling Encounter with Harmonic Numbers |year=2002 |journal=[[Mathematics Magazine]] |volume=75 |issue=2 |pages=95–103 |doi=10.2307/3219141|jstor=3219141 |citeseerx=10.1.1.383.722 }}
* {{cite book |author=[[Donald Knuth]] |title=The Art of Computer Programming |volume=Volume 1: ''Fundamental Algorithms'' |edition=Third |publisher=Addison-Wesley |year=1997 |isbn=978-0-201-89683-1 |chapter=Section 1.2.7: Harmonic Numbers |pages=75–79}}
* Ed Sandifer, ''[http://www.maa.org/editorial/euler/How%20Euler%20Did%20It%2002%20Estimating%20the%20Basel%20Problem.pdf How Euler Did It — Estimating the Basel problem]'' (2003)
* {{cite journal
 | last1 = Paule | first1 = Peter | author1-link = Peter Paule
 | last2 = Schneider | first2 = Carsten
 | doi = 10.1016/s0196-8858(03)00016-2
 | issue = 2
 | journal = Adv. Appl. Math.
 | pages = 359–378
 | title = Computer Proofs of a New Family of Harmonic Number Identities
 | url = http://www.risc.uni-linz.ac.at/publications/download/risc_200/HarmonicNumberIds.pdf
 | volume = 31
 | year = 2003}}
* {{cite journal |author=Wenchang Chu |url=http://www.combinatorics.org/Volume_11/PDF/v11i1n15.pdf |title=A Binomial Coefficient Identity Associated with Beukers' Conjecture on Apery Numbers |year=2004 |journal=The Electronic Journal of Combinatorics |volume=11 |pages=N15}}
* {{cite journal |author1=Ayhan Dil |author2=István Mező |title=A Symmetric Algorithm for Hyperharmonic and Fibonacci Numbers |year=2008 |journal=Applied Mathematics and Computation |volume=206 |issue=2 |pages=942–951 |doi=10.1016/j.amc.2008.10.013|arxiv=0803.4388 }}

==External links==
* {{MathWorld|urlname=HarmonicNumber |title=Harmonic Number}}

{{PlanetMath attribution|id=3421|title=Harmonic number}}

{{DEFAULTSORT:Harmonic Number}}
[[Category:Number theory]]