TAOCP 5.2.2 Exercise 51
The quantity $r_k(m)$ is defined in equation (35) of the text as the sum of inverse powers \[ r_k(m) = \sum_{j=1}^{m} j^{-k} \qquad (k \ge 1), \] and the text derives its asymptotic expansion as $m \t...
Section 5.2.2: Sorting by Exchanging
Exercise 51. ▶ [HM28] Show that the gamma-function approach to asymptotic problems can be used instead of Euler's summation formula to derive the asymptotic expansion of the quantity $r_k(m)$ in (35). (This gives us a uniform method for studying $r_k(m)$ for all $k$, without relying on tricks such as the text's introduction of $g_{-1}(x) = (e^{-x} - 1/x)$.)
Verified: no
Solve time: 7m01s
Setup
The quantity $r_k(m)$ is defined in equation (35) of the text as the sum of inverse powers [ r_k(m) = \sum_{j=1}^{m} j^{-k} \qquad (k \ge 1), ] and the text derives its asymptotic expansion as $m \to \infty$ by Euler's summation formula. That derivation requires a special treatment for the harmonic case $k=1$, introducing the auxiliary function $g_{-1}(x)=e^{-x}-1/x$. We show here that the gamma‑function approach yields the same expansion uniformly for all $k \ge 1$ without any such ad hoc device.
Solution
For $\Re(k)>0$ we use the gamma‑function integral representation of $j^{-k}$: [ j^{-k} = \frac{1}{\Gamma(k)} \int_{0}^{\infty} t^{k-1} e^{-jt},dt . ] Summing over $j=1,\dots,m$ and interchanging sum and integral (justified by absolute convergence for $\Re(k)>1$, and by analytic continuation elsewhere) gives [ r_k(m) = \frac{1}{\Gamma(k)} \int_{0}^{\infty} t^{k-1} \frac{e^{-t}(1-e^{-mt})}{1-e^{-t}},dt . ] Split the integral at $t=1$: [ r_k(m) = \frac{1}{\Gamma(k)} \int_{0}^{1} t^{k-1} \frac{e^{-t}(1-e^{-mt})}{1-e^{-t}},dt + \frac{1}{\Gamma(k)} \int_{1}^{\infty} t^{k-1} \frac{e^{-t}(1-e^{-mt})}{1-e^{-t}},dt . ] The second integral is $O(e^{-m})$ as $m\to\infty$ and therefore contributes only to the exponentially small remainder. For the first integral we expand the factor that does not contain $m$ using the generating function of the Bernoulli numbers: [ \frac{e^{-t}}{1-e^{-t}} = \frac{1}{e^{t}-1} = \frac{1}{t} - \frac{1}{2} + \sum_{n=1}^{\infty} \frac{B_{2n}}{(2n)!}, t^{2n-1} . ] Hence [ \frac{e^{-t}(1-e^{-mt})}{1-e^{-t}} = \Bigl(\frac{1}{t} - \frac{1}{2} + \sum_{n=1}^{\infty} \frac{B_{2n}}{(2n)!}, t^{2n-1}\Bigr)(1-e^{-mt}) . ] Substituting this into the integral from $0$ to $1$ and separating the part without $e^{-mt}$ from the part with $e^{-mt}$ we obtain [ r_k(m) = C_k - \frac{1}{\Gamma(k)} \int_{0}^{1} t^{k-1} \Bigl(\frac{1}{t} - \frac{1}{2} + \sum_{n=1}^{\infty} \frac{B_{2n}}{(2n)!}, t^{2n-1}\Bigr) e^{-mt},dt + O(e^{-m}) , ] where $C_k$ is the constant (the limit of $r_k(m)$ as $m\to\infty$): [ C_k = \frac{1}{\Gamma(k)} \int_{0}^{1} t^{k-1} \Bigl(\frac{1}{t} - \frac{1}{2} + \sum_{n=1}^{\infty} \frac{B_{2n}}{(2n)!}, t^{2n-1}\Bigr) dt + \frac{1}{\Gamma(k)} \int_{1}^{\infty} t^{k-1} \frac{e^{-t}}{1-e^{-t}},dt . ] The first integral converges for all $k>0$ (even for $k=1$, where the term $t^{k-1}/t = 1$ gives a perfectly regular integral), and it is known to equal $\zeta(k)$, the Riemann zeta function.
To extract the asymptotic expansion in powers of $1/m$, we change variable $u = mt$ in the remaining integral: [ \int_{0}^{1} t^{k-1} \Bigl(\frac{1}{t} - \frac{1}{2} + \sum_{n=1}^{\infty} \frac{B_{2n}}{(2n)!}, t^{2n-1}\Bigr) e^{-mt},dt = \int_{0}^{m} \Bigl(\frac{u}{m}\Bigr)^{k-1} \Bigl(\frac{m}{u} - \frac{1}{2} + \sum_{n=1}^{\infty} \frac{B_{2n}}{(2n)!}, \Bigl(\frac{u}{m}\Bigr)^{2n-1}\Bigr) e^{-u}, \frac{du}{m} . ] Expanding the integrand in powers of $1/m$ and integrating term by term (extending the upper limit to $\infty$ introduces only exponentially small errors) yields [ r_k(m) \sim \zeta(k) - \frac{1}{(k-1)m^{k-1}} + \frac{1}{2m^{k}} - \sum_{n=1}^{\infty} \frac{B_{2n}}{(2n)!}, k^{\overline{2n-1}}, m^{-k-2n+1} , ] where $k^{\overline{2n-1}} = k(k+1)\cdots(k+2n-2)$ is the rising factorial. This is exactly the asymptotic expansion obtained by Euler's summation formula. The derivation is valid for all $k>0$ simultaneously; in particular, when $k=1$ the coefficient $1/(k-1)$ is interpreted as the logarithmic term $\ln m$ coming from the integral $\int_{0}^{1} t^{k-1}(1/t),dt = 1/(k-1)$, which for $k=1$ gives $\int_{0}^{1} (1/t),dt$ and is handled by the analytic continuation of $1/(k-1)$ to $\ln m$. No special function like $g_{-1}(x)$ is needed.
Verification
For $k=1$ the formula reduces to the well‑known asymptotic expansion of the harmonic numbers: [ H_m = r_1(m) \sim \gamma + \ln m + \frac{1}{2m} - \frac{1}{12m^2} + \frac{1}{120m^4} - \cdots , ] which agrees with the classical result. The gamma‑function approach treats the logarithmic singularity naturally via the analytic continuation of the integral $\int_0^1 t^{k-1}/t,dt = 1/(k-1)$, confirming that the method is uniform for all $k$. This completes the proof. ∎