- Harmonic number
:"The term "harmonic number" has multiple meanings. For other meanings, see
harmonic number (disambiguation) ".In
mathematics , the "n"-th harmonic number is the sum of the reciprocals of the first "n" natural numbers::H_n= 1+frac{1}{2}+frac{1}{3}+cdots+frac{1}{n}:sum_{k=1}^n frac{1}{k}.This also equals "n" times the inverse of the
harmonic mean of these natural numbers.Harmonic numbers were studied in antiquity and are important in various branches of
number theory . They are sometimes loosely termed harmonic series, are closely related to theRiemann zeta function , and appear in various expressions for variousspecial function s.Calculation
An integral representation is given by
Euler :: H_n = int_0^1 frac{1 - x^n}{1 - x},dx.
This representation can be easily shown to satisfy the recurrence relation by the formula
: int_0^1 x^n,dx = frac{1}{n + 1},
and then
: x^{n} + frac{1 - x^n}{1 - x} = frac{1 - x^{n+1{1 - x}
inside the integral.
"H""n" grows about as fast as the
natural logarithm of "n". The reason is that the sum is approximated by theintegral : int_1^n {1 over x}, dx
whose value is ln("n"). More precisely, we have the limit:
: lim_{n o infty} H_n - ln(n) = gamma
(where γ is the
Euler-Mascheroni constant 0.5772156649dots), and the corresponding asymptotic expansion::H_n = gamma + ln{n} + frac{1}{2}n^{-1} - frac{1}{12}n^{-2} + frac{1}{120}n^{-4} + mathcal{O}(n^{-6})
pecial values for fractional arguments
There are the following special analytic values for fractional arguments between 0 and 1, given by the integral:H_alpha = int_0^1frac{1-x^alpha}{1-x},dxMore may be generated from the recurrence relation H_alpha = H_{alpha-1}+frac{1}{alpha}.
: H_{1/2} = 2 -2ln{2},
: H_{1/3} = 3-frac{pi}{2sqrt{3 -frac{3}{2}ln{3}
: H_{1/4} = 4-frac{pi}{2} - 3ln{2}
: H_{1/6} = 6-frac{pi}{2}sqrt{3} -2ln{2} -frac{3}{2}ln(3)
: H_{1/8} = 8-frac{pi}{2} - 4ln{2} - frac{1}{sqrt{2 left{pi + ln(2 + sqrt{2}) - ln(2 - sqrt{2}) ight}
Generating functions
A
generating function for the harmonic numbers is:sum_{n=1}^infty z^n H_n = frac {-ln(1-z)}{1-z},
where ln(z) is the
natural logarithm . An exponential generating function is: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 mbox {Ein}(z)
where mbox{Ein}(z) is the entire
exponential integral . Note that:mbox {Ein}(z) = mbox{E}_1(z) + gamma + ln z = Gamma (0,z) + gamma + ln z,
where Gamma (0,z) is the
incomplete gamma function .Applications
The harmonic numbers appear in several calculation formulas, such as the
digamma function :: psi(n) = H_{n-1} - gamma.,
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 γ, using the limit introduced in the previous section, although
: gamma = lim_{n ightarrow infty}{left(H_n - lnleft(n+{1 over 2} ight) ight)}
converges more quickly.
In 2002
Jeffrey Lagarias proved that theRiemann hypothesis is equivalent to the statement that :sigma(n) le H_n + ln(H_n)e^{H_n},is true for everyinteger "n" ≥ 1 with strict inequality if "n" > 1; here σ("n") denotes the sum of the divisors of "n".See also
Watterson estimator ,Tajima's D ,coupon collector's problem .Generalization
Generalized harmonic numbers
The generalized harmonic number of order n of "m" is given by
:H_{n,m}=sum_{k=1}^n frac{1}{k^m}.
Note that the limit as "n" tends to infinity exists if m > 1.
Other notations occasionally used include
:H_{n,m}= H_n^{(m)} = H_m(n).
The special case of m=1 is simply called a harmonic number and is frequently written without the superscript, as
:H_n= sum_{k=1}^n frac{1}{k}.
In the limit of n ightarrow infty, the generalized harmonic number converges to the
Riemann zeta function :lim_{n ightarrow infty} H_{n,m} = zeta(m).
The related sum sum_{k=1}^n k^m occurs in the study of
Bernoulli number s; the harmonic numbers also appear in the study ofStirling number s.A
generating function for the generalized harmonic numbers is:sum_{n=1}^infty z^n H_{n,m} = frac {mbox{Li}_m(z)}{1-z},
where mbox{Li}_m(z) is the
polylogarithm , and z|<1. The generating function given above for m=1 is a special case of this formula.Generalization to the complex plane
Euler's integral formula for the harmonic numbers follows from the integral identity
:int_a^1 frac {1-x^s}{1-x} dx = - sum_{k=1}^infty frac {1}{k} {s choose k} (a-1)^k
which holds for general complex-valued "s", for the suitably extended
binomial coefficient s. By choosing "a"=0, this formula gives both an integral and a series representation for a function that interpolates the harmonic numbers and extends a definition to the complex plane. This integral relation is easily derived by manipulating theNewton series :sum_{k=0}^infty {s choose k} (-x)^k = (1-x)^s,
which is just the Newton's generalized
binomial theorem . The interpolating function is in fact just thedigamma function ::psi(s+1)+gamma = int_0^1 frac {1-x^s}{1-x} dx
where psi(x) is the digamma, and gamma is the Euler-Mascheroni constant. The integration process may be repeated to obtain
:H_{s,2}=-sum_{k=1}^infty frac {(-1)^k}{k} {s choose k} H_k.
References
* Arthur T. Benjamin, Gregory O. Preston, Jennifer J. Quinn, " [http://www.math.hmc.edu/~benjamin/papers/harmonic.pdf A Stirling Encounter with Harmonic Numbers] ", (2002) Mathematics Magazine, 75 (2) pp 95-103.
*Donald Knuth . "The Art of Computer Programming", Volume 1: "Fundamental Algorithms", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 1.2.7: Harmonic Numbers, pp.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)
*
* Peter Paule and Carsten Schneider, " [http://www.risc.uni-linz.ac.at/publications/download/risc_200/HarmonicNumberIds.pdf Computer Proofs of a New Family of Harmonic Number Identities] ", (2003) Adv. in Appl. Math. 31(2), pp. 359-378.
* Wenchang CHU, " [http://www.combinatorics.org/Volume_11/PDF/v11i1n15.pdf A Binomial Coefficient Identity Associated with Beukers' Conjecture on Apery Numbers] ", (2004) "The Electronic Journal of Combinatorics", 11, #N15.
Wikimedia Foundation. 2010.