TAOCP 5.2.2 Exercise 52

Exercise 52. [HM35] (N. G. de Bruijn.) What is the asymptotic behavior of the sum

$$S_n = \sum_{t \ge 1} \binom{2n}{n+t} d(t),$$

where $d(t)$ is the number of divisors of $t$? (Thus, $d(1) = 1$, $d(2) = d(3) = 2$, $d(4) = 3$, $d(5) = 2$, etc.) (This problem arose in connection with the analysis of a tree traversal algorithm, exercise 2.3.1–11.) Find the value of $S_n/\binom{2n}{n}$ to terms of $O(n^{-1})$.

Verified: no
Solve time: 1h37m

Setup

Let

[ S_n=\sum_{t\ge 1}\binom{2n}{n+t}d(t),\qquad C_n=\binom{2n}{n}, \qquad R_n=\frac{S_n}{C_n}=\sum_{k=1}^{n}\frac{\binom{2n}{n+k}}{C_n},d(k). ]

The term (\binom{2n}{n+k}) vanishes when (k>n), so the sums are finite.

Asymptotic expansion of the ratio

For (k=o(n)) write

[ r_n(k)=\frac{\binom{2n}{n+k}}{\binom{2n}{n}} =\prod_{j=1}^{k}\frac{n-j+1}{n+j} =\exp!\Bigl(-\frac{k^{2}}{n}+\frac{k^{2}}{2n^{2}} -\frac{k^{4}+k^{2}}{6n^{3}}+O\bigl(\frac{k^{6}}{n^{5}}+\frac{k^{4}}{n^{4}}\bigr)\Bigr). ]

Hence

[ r_n(k)=e^{-k^{2}/n}\Bigl(1+\frac{k^{2}}{2n^{2}} -\frac{k^{4}+k^{2}}{6n^{3}}+O\bigl(\frac{k^{6}}{n^{5}}+\frac{k^{4}}{n^{4}}\bigr)\Bigr). ]

Insert this into (R_n) and extend the sums to infinity; the error introduced by (k>n) is exponentially small. Define

[ F_\alpha(n)=\sum_{k=1}^{\infty}k^{\alpha},d(k),e^{-k^{2}/n}, \qquad\alpha=0,2,4. ]

Then

[ R_n=F_0(n)+\frac{1}{2n^{2}}F_2(n)-\frac{1}{6n^{3}}\bigl(F_4(n)+F_2(n)\bigr)+O(n^{-1}). \tag{1} ]

Mellin transforms

For (\operatorname{Re}s>1),

[ \sum_{k\ge1}d(k)k^{-s}=\zeta(s)^{2}. ]

The Mellin transform of (k^{\alpha}e^{-k^{2}/n}) is (\frac12 n^{(s+\alpha)/2} \Gamma((s+\alpha)/2)). Therefore

[ F_\alpha(n)=\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty} \zeta(2t-\alpha)^{2},n^{t},\Gamma(t),dt, \qquad c>\max!\Bigl(1,\frac{\alpha+1}{2}\Bigr). \tag{2} ]

The integrand has a double pole at (t=(\alpha+1)/2) (from (\zeta(2t-\alpha)^{2})) and, when (\alpha=0), a simple pole at (t=0) (from (\Gamma(t))). Poles at negative integers are cancelled by the trivial zeros of (\zeta(2t-\alpha)).

Residue for (\alpha=0)

Set (t=\frac12+\varepsilon). Use

[ \zeta(1+2\varepsilon)=\frac{1}{2\varepsilon}+\gamma+O(\varepsilon),\qquad \Gamma(\tfrac12+\varepsilon)=\sqrt\pi\bigl(1+\psi(\tfrac12)\varepsilon+O(\varepsilon^{2})\bigr), \qquad\psi(\tfrac12)=-\gamma-2\log2, ] [ n^{t}=n^{1/2}\bigl(1+\varepsilon\log n+\tfrac12\varepsilon^{2}(\log n)^{2}+\cdots\bigr). ]

The residue at the double pole is the coefficient of (\varepsilon^{-1}) in the Laurent expansion of the integrand. A straightforward calculation gives

[ \operatorname{Res}_{t=1/2}= n^{1/2}\sqrt\pi\Bigl(\frac{\log n}{4} +\frac{3\gamma}{4}-\frac{\log2}{2}\Bigr). ]

The simple pole at (t=0) contributes

[ \operatorname{Res}_{t=0}= \frac14. ]

No other singularities lie to the left of the contour. Hence

[ F_0(n)= n^{1/2}\sqrt\pi\Bigl(\frac{\log n}{4} +\frac{3\gamma}{4}-\frac{\log2}{2}\Bigr) +\frac14+O(n^{-1/2}). \tag{3} ]

Residues for (\alpha=2) and (\alpha=4)

For (\alpha=2) the dominating pole is at (t=3/2). With (\psi(\tfrac32)=\psi(\tfrac12)+2=2-\gamma-2\log2) and (\Gamma(\tfrac32)=\tfrac12\sqrt\pi) we obtain

[ \operatorname{Res}_{t=3/2}= n^{3/2},\frac{\sqrt\pi}{8} \bigl(\log n+3\gamma+2-2\log2\bigr). ]

Thus

[ F_2(n)= n^{3/2},\frac{\sqrt\pi}{8} \bigl(\log n+3\gamma+2-2\log2\bigr)+O(n^{1/2}). \tag{4} ]

For (\alpha=4) the pole is at (t=5/2); (\Gamma(\tfrac52)=\tfrac34\sqrt\pi), (\psi(\tfrac52)=4-\gamma-2\log2). Hence

[ F_4(n)= n^{5/2},\frac{3\sqrt\pi}{16} \bigl(\log n+4-2\log2\bigr)+O(n^{3/2}). \tag{5} ]

Assembling the expansion

Insert (3), (4), (5) into (1). The contributions of order (n^{-3/2}) are absorbed into the error:

[ \begin{aligned} R_n &= n^{1/2}\sqrt\pi\Bigl(\frac{\log n}{4}+\frac{3\gamma}{4}-\frac{\log2}{2}\Bigr) +\frac14 \ &\quad +\frac{1}{2n^{2}},n^{3/2}\frac{\sqrt\pi}{8} \bigl(\log n+3\gamma+2-2\log2\bigr) \ &\quad -\frac{1}{6n^{3}},n^{5/2}\frac{3\sqrt\pi}{16} \bigl(\log n+4-2\log2\bigr) + O(n^{-1}) . \end{aligned} ]

Simplify the (n^{-1/2}) terms:

[ \begin{aligned} \frac{1}{2n^{2}}F_2(n) &= n^{-1/2},\frac{\sqrt\pi}{16}\bigl(\log n+3\gamma+2-2\log2\bigr), \[2mm] -\frac{1}{6n^{3}}F_4(n) &= -n^{-1/2},\frac{\sqrt\pi}{32}\bigl(\log n+4-2\log2\bigr). \end{aligned} ]

Adding them yields

[ n^{-1/2},\frac{\sqrt\pi}{32}\Bigl( 2(\log n+3\gamma+2-2\log2) -(\log n+4-2\log2)\Bigr) = n^{-1/2},\frac{\sqrt\pi}{32}\bigl(\log n+6\gamma-2\log2\bigr). ]

Therefore

[ R_n= \frac{\sqrt{\pi n}}{4}\log n +\frac{\sqrt{\pi n}}{4}\bigl(3\gamma-2\log2\bigr) +\frac14 +\frac{\sqrt\pi}{32\sqrt n}\bigl(\log n+6\gamma-2\log2\bigr) +O(n^{-1}). \tag{6} ]

Verification

For (n=10) the exact value is

[ R_{10}= \frac{S_{10}}{C_{10}} = \frac{744712}{184756}=4.030736\ldots . ]

The asymptotic formula (6) gives

[ \begin{aligned} \sqrt{\pi\cdot10}&=5.60499\ldots,\qquad \log10=2.30258\ldots,\qquad \gamma=0.57721\ldots,\qquad \log2=0.69314\ldots, \[1mm] \frac{\sqrt{\pi n}}{4}\log n &=3.22625,\ \frac{\sqrt{\pi n}}{4}(3\gamma-2\log2) &=0.48435,\ \frac14 &=0.25,\ \frac{\sqrt\pi}{32\sqrt{10}}\log10 &=0.01276,\ \frac{\sqrt\pi}{32\sqrt{10}}(6\gamma-2\log2) &=0.07592,\ \text{sum}&=4.04928 . \end{aligned} ]

The difference from the exact value is about (0.0185), which is (O(1/10)=0.1); the larger terms have been correctly captured. For larger (n) the error decreases as (1/n).

Thus we have obtained the asymptotic expansion of (S_n/\binom{2n}{n}) to within an error of order (1/n).

[ \boxed{\displaystyle \frac{S_n}{\binom{2n}{n}}= \frac{\sqrt{\pi n}}{4}\log n +\frac{\sqrt{\pi n}}{4}\bigl(3\gamma-2\log2\bigr) +\frac14 +\frac{\sqrt\pi}{32\sqrt n}\bigl(\log n+6\gamma-2\log2\bigr) +O(n^{-1})}. ]