I was reading Chapter 9: Asymptotics in Graham, Knuth, Patashnik: Concrete Mathematics, and I got stuck while deriving the following asymptotic estimate on page 466: $$ \begin{equation} g_n = \frac{e^{\pi^2/6}}{n^2} + O(\log n / n^3) \, , \quad \text{for } n > 1 \, . \tag{9.62} \end{equation} $$ The value $g_n$ is the coefficient of $z^n$ in the generating function $$ \begin{equation} G(z) = \exp\left(\sum_{k \geq 1} \frac{z^k}{k^2}\right) \, . \tag{9.57} \end{equation} $$
To derive the estimate, one starts by differentiating $(9.57)$: $$ G'(z) = \sum_{n \geq 0} n g_n z^{n-1} = \left( \sum_{k \geq 1} \frac{z^{k-1}}{k} \right) G(z) \, . $$ Equating coefficients of $z^{n-1}$ on both sides leads to the following recurrence for $g_n$: $$ \begin{equation} n g_n = \sum_{0 \leq k < n} \frac{g_k}{n-k} \, . \tag{9.58} \end{equation} $$ Next, one proceeds with the following bootstrapping trick. Start with a rough initial estimate $g_n = O(1)$, obtained by showing that $0 < g_n \leq 1$ for $n \geq 0$. Plug the initial estimate into the recurrence to get a better estimate $g_n = O(\log n / n)$. By repeatedly plugging new estimates back into the recurrence and massaging the recurrence when needed, one gets successively better estimates, leading up to the following one that is one step away from $(9.62)$ (note the differently placed exponent in the $O$ term): $$ \begin{equation} g_n = \frac{e^{\pi^2/6}}{n^2} + O(\log n / n)^3 \, , \quad \text{for } n > 1 \, . \tag{9.61} \end{equation} $$ Another bootstrapping step is supposed to give $(9.62)$. However, I fail to carry out the calculation.
Here are some of the attempts I made.
Attempt 1
Let me denote the constant $e^{\pi^2 / 6}$ by $c$. When I plug $(9.61)$ directly into $(9.58)$, I get the following: $$ \begin{align} n g_n = {} & \frac{1}{n} + \sum_{0 < k < n} \frac{c}{k^2 (n-k)} + \sum_{0 < k < n} \frac{O(\log n)^3}{k^3 (n-k)} \\ = {} & \frac{1}{n} + c \sum_{0 < k < n} \left( \frac{1}{n k^2} + \frac{1}{n^2 k} + \frac{1}{n^2(n-k)} \right) \\ & {} + O(\log n)^3 \sum_{0 < k < n} \left( \frac{1}{n k^3} + \frac{1}{n^2 k^2} + \frac{1}{n^3 k} + \frac{1}{n^3 (n-k)} \right) \\ = {} & \frac{1}{n} + c \left( \frac{1}{n} H^{(2)}_{n-1} + \frac{2}{n^2} H_{n-1} \right) + O(\log n)^3 \left( \frac{1}{n} H^{(3)}_{n-1} + \frac{1}{n^2} H^{(2)}_{n-1} + \frac{2}{n^3} H_{n-1} \right) \, . \end{align} $$ (In the last step, $H^{(i)}_{n-1}$ stands for generalized harmonic numbers, and $H_{n-1}=H^{(1)}_{n-1}$.) This seems to be worse than what I started with, since for example $$ \frac{1}{n} H^{(3)}_{n-1} O(\log n)^3 = O\left( \frac{(\log n)^3}{n} \right) \, , $$ so $O((\log n)^3 / n^2)$ appears in the final estimate for $g_n$.
Attempt 2
Another attempt involves the trick of "pulling out the largest part." This trick is used in Concrete Mathematics to derive $(9.61)$. We can massage the recurrence $(9.58)$ to obtain the following: $$ \begin{align} n g_n & = \sum_{0 \leq k < n} \frac{g_k}{n} + \sum_{0 \leq k < n} g_k \left( \frac{1}{n-k} - \frac{1}{n} \right) \\ & = \frac{1}{n} \sum_{k \geq 0} g_k - \frac{1}{n} \sum_{k \geq n} g_k + \frac{1}{n} \sum_{0 \leq k < n} \frac{k g_k}{n-k} \, . \end{align} $$ The first sum is $G(1)=c$. For the second sum, I have $$ \begin{align} \sum_{k \geq n} g_k & = \sum_{k \geq n} \frac{c}{k^2} + O\left( \sum_{k \geq n} \frac{(\log k)^3}{k^3} \right) \\ & = c \left( \frac{\pi^2}{6} - H^{(2)}_{n-1} \right) + O\left( \frac{(\log n)^3}{n^2} \right) \, . \end{align} $$ It doesn't look like I'm going to end up with anything as nice as $(9.62)$, but at least the final asymptotic error is still within $O(\log n / n^3)$. However, things fail again when I analyze the third sum: $$ \begin{align} \sum_{0 \leq k < n} \frac{k g_k}{n-k} & = \sum_{0 < k < n} \frac{c}{k (n-k)} + \sum_{0 < k < n} \frac{O(\log n)^3}{k^2 (n-k)} \\ & = \frac{c}{n} \sum_{0 < k < n} \left( \frac{1}{k} + \frac{1}{n-k} \right) + O(\log n)^3 \left( \frac{1}{n} H^{(2)}_{n-1} + \frac{2}{n^2} H_{n-1} \right) \\ & = \frac{2c}{n} H_{n-1} + O(\log n)^3 \left( \frac{1}{n} H^{(2)}_{n-1} + \frac{2}{n^2} H_{n-1} \right) \, . \end{align} $$ Similarly as in Attempt 1, there is a term $$ \frac{1}{n} H^{(2)}_{n-1} O(\log n)^3 = O\left( \frac{(\log n)^3}{n} \right) \, , $$ leading to $O(\log n / n)^3$ in the final estimate for $g_n$.
Attempt 3
After pulling out $1/n$ in Attempt 2, we see that the first sum gives us exactly the leading term in $(9.62)$, so that sum should stay as it is. The second and the third sum are problematic. Each on its own contributes too much, so I guess the trick is to somehow fuse them together. One idea is to try pulling out another $1/n$ from the third sum: $$ \sum_{0 \leq k < n} \frac{k g_k}{n - k} = \frac{1}{n} \sum_{0 \leq k < n} k g_k + \frac{1}{n} \sum_{0 \leq k < n} \frac{k^2 g_k}{n-k} \, . $$ Now the sum $\sum_{0 \leq k < n} k^2 g_k / (n-k)$ is fine: with the same kind of analysis as in previous attempts we conclude it is $O((\log n)^4 / n)$, so with all the pulled-out parts it contributes $O(\log n / n)^4$ in the final estimate.
What to do with $\sum_{0 \leq k < n} k g_k$? My idea was to decompose it as in Attempt 2: $$ \sum_{0 \leq k < n} k g_k = \sum_{k \geq 0} k g_k - \sum_{k \geq n} k g_k \, . $$ Unfortunately, this doesn't work, because now the first sum is $G'(1)$, and this doesn't converge.
What am I doing wrong? Do I need to massage the recurrence in some other way? There must be something obvious that I just don't see.
