Reference for proof of harmonic number asymptotic expansion

Question

Can anyone show me where I can find a proof of the following? $$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$$

Answer 1

You can probably get what you need from Donald E. Knuth's "The Art of Computer Programming," Volume 1 (Fundamental Algorithms), Addison Wesley. In my (Second) Edition the relevant section is 1.2.11.2 (page 108).

I used this back in the mid-1970's to prove that the average rounding error when using computer arithmetic (discarding the reminder) for integer division is (3-2C)/4 +O(1/sqrt(N)) where C is Euler's constant and N is the maximum size of the integer in the computer.

Answer 2

As Steven Stadnicki points out in the comments, this is just an application of Euler–Maclaurin formula.

---

Abel's partial summation technique: \begin{align*} \sum_{n=1}^{N} a(n) f(n) & = \sum_{n=1}^{N} f(n) (A(n)- A(n-1)) = \sum_{n=1}^{N} A(n) f(n) - \sum_{n=1}^{N} A(n-1) f(n)\\ & = \sum_{n=1}^{N} A(n)f(n) - \sum_{n=0}^{N-1} A(n) f(n+1)\\ & = A(N)f(N) - A(0) f(1) - \sum_{n=1}^{N-1} A(n) (f(n+1)-f(n)) \end{align*} (The above is nothing but the discrete version of integration by parts).

$$\sum_{n=1}^{N} a(n) f(n) = \int_{1^-}^{N^+} f(t) d(A(t)) = f(t) A(t) \rvert_{1^-}^{N^+} - \int_{1^-}^{N^+} A(t) f'(t) dt$$ (The second integral can be interpreted as a Riemann-Stieltjes integral.)

For instance, consider the sum $\displaystyle \sum_{n \leq N} \frac1n$. Choose $a(n) = 1$ and $f(n) = \frac1n$. Note that we have $A(t) = \lfloor t \rfloor = t - \{t\}$. Hence, we get that \begin{align*} \sum_{n \leq N} \frac1n & = \left. \frac{t-\{t\}}t \right \rvert_{1^-}^{N^+} + \int_{1^-}^{N^+} \frac{(t-\{t\})}{t^2} dt\\ & = 1 + \int_{1^-}^{N^+} \frac{dt}t - \int_{1^-}^{N^+} \frac{\{t\}}{t^2} dt\\ & = 1 + \log (N) - \int_{1^-}^{\infty} \frac{\{t\}}{t^2} dt + \int_{N^+}^{\infty} \frac{\{t\}}{t^2} dt\\ & = \left(1 - \int_{1^-}^{\infty} \frac{\{t\}}{t^2} dt \right) + \log(N) + \int_{N^+}^{\infty} \frac{\{t\}}{t^2} dt \end{align*} Note that $\displaystyle \int_{N^+}^{\infty} \frac{\{t\}}{t^2} dt \leq \int_{N^+}^{\infty} \frac{1}{t^2} dt = \frac1N$.

Also note that by the same argument, we also have that $\displaystyle 0 < \int_{N^+}^{\infty} \frac{\{t\}}{t^2} dt < 1$ and hence $\displaystyle 0 < \left(1 - \int_{1^-}^{\infty} \frac{\{t\}}{t^2} dt \right) < 1$. Denoting $\displaystyle \left(1 - \int_{1^-}^{\infty} \frac{\{t\}}{t^2} dt \right) = \gamma$, we get the following proposition. $$ \sum_{n \leq N} \frac1n = \gamma + \log(N) + \mathcal{O} \left(\frac1N \right) $$

$\gamma \approx 0.5772\ldots$ and is called the Euler-Mascheroni constant.

We will now get a better approximation for the harmonic series by including the $\mathcal{O} \left(1/N \right)$ term. To do this, we need to refine our evaluation of $\displaystyle \int_{N^+}^{\infty} \frac{\{t\}}{t^2} dt$. Note that the average value of $\{t\}$ on any unit interval is $\frac12$. Hence, we would expect, $\displaystyle \int_{N^+}^{\infty} \frac{\{t\}}{t^2} dt = \int_{N^+}^{\infty} \frac{1}{2t^2} dt + $ lower order terms.

We have $\displaystyle \int_{N^+}^{\infty} \frac{\{t\}}{t^2} dt = \int_{N^+}^{\infty} \frac{\{t\} - 1/2}{t^2} dt + \int_{N^+}^{\infty} \frac{1}{2t^2} dt = \frac1{2N} + \int_{N^+}^{\infty} \frac{\{t\} - 1/2}{t^2} dt$. We now need the asymptotics for $\displaystyle \int_{N^+}^{\infty} \frac{\{t\} - 1/2}{t^2} dt$.

Let $\displaystyle B(y) = \{y\} - \frac12$ and let $B_1(t) = \displaystyle \int_0^t B(y) dy$. Note that $\displaystyle \int_x^{x+1} B(y) dy = 0$. Hence, $\displaystyle B_1(t) = \int_{\lfloor t \rfloor}^{t} B(y) dy = \int_{0}^{t} B(y) dy = \int_{0}^{t} (y - 1/2) dy = \frac{\{t\}^2 - \{t\}}{2}$. We then have \begin{align} \displaystyle \int_{N^+}^{\infty} \frac{B(t)}{t^2} dt & = \left. \frac{B_1(t)}{t^2} \right|_{N^+}^{\infty} + 2 \int_{N^+}^{\infty} \frac{B_1(t)}{t^3} dt\\ & = -\frac{B_1(N)}{N^2} + 2 \int_{N^+}^{\infty} \frac{B_1(t)}{t^3} dt = 2 \int_{N^+}^{\infty} \frac{B_1(t)}{t^3} dt \end{align}

As before, note that the average value of $B_1(t)$ is given by $\displaystyle \int_0^1 \frac{y^2-y}{2} dy = \frac16 - \frac14 = -\frac1{12}$. Hence, we have that $$\displaystyle \int_{N^+}^{\infty} \frac{B_1(t)}{t^3} dt = -\frac1{12} \int_{N^+}^{\infty} \frac{1}{t^3} dt + \int_{N^+}^{\infty} \frac{B_1(t) + \frac1{12}}{t^3} dt = -\frac1{24N^2} + \int_{N^+}^{\infty} \frac{B_1(t) + \frac1{12}}{t^3} dt.$$ Let $B_2(t) = \displaystyle \int_0^t \left( B_1(y) + \frac1{12} \right) dy = \int_0^{\{t\}} \left( B_1(y) + \frac1{12} \right) dy$.

Hence, we now have that \begin{align*} \sum_{n \leq N} \frac1n & = \gamma + \log(N) + \frac1{2N} + \int_{N^+}^{\infty} \frac{B(t)}{t^2} dt\\ & = \gamma + \log(N) + \frac1{2N} + 2 \int_{N^+}^{\infty} \frac{B_1(t)}{t^3} dt\\ & = \gamma + \log(N) + \frac1{2N} + 2 \left( -\frac1{24N^2} + \int_{N^+}^{\infty} \frac{B_1(t) + \frac1{12}}{t^3} dt \right)\\ & = \gamma + \log(N) + \frac1{2N} -\frac1{12N^2}+ \int_{N^+}^{\infty} \frac{2B_1(t) + \frac1{6}}{t^3} dt\\ & = \gamma + \log(N) + \frac1{2N} -\frac1{12N^2}+ \int_{N^+}^{\infty} \frac{dB_2(t)}{t^3}\\ & = \gamma + \log(N) + \frac1{2N} -\frac1{12N^2}+ \left. \frac{B_2(t)}{t^3} \right|_{N^+}^{\infty} + 3 \int_{N^+}^{\infty} \frac{B_2(t)}{t^4} dt\\ & = \gamma + \log(N) + \frac1{2N} -\frac1{12N^2} + 3 \int_{N^+}^{\infty} \frac{B_2(t)}{t^4} dt \end{align*}

Now proceed like this to get the higher order terms.