14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ To solve this problem they refer to exercise $23$ with $\displaystyle g_n:=\frac{c}{(n+1)(n+2)}+h_n$ . But sorry I don't know what they are aiming for. Maybe you will find it out. $\endgroup$ – user90369 Dec 19 '17 at 13:37
  • $\begingroup$ Actually, the solution to that exercise assumes $(9.62)$, or equivalently that $h_n=O(\log n / n^3)$. In fact, starting with that assumption one ultimately has to derive $\sum_{0<k<n} k h_k / (n-k) = O(n^{-1})$, which is as difficult as the estimate in question. But I've figured it out now. I'm going to give people chance to answer the question and claim the bounty, and if there's no answer after that, I'll just answer it myself. $\endgroup$ – Filip Nikšić Dec 19 '17 at 17:33
  • $\begingroup$ Would be nice to see what you've figured out. :-) $\endgroup$ – user90369 Dec 19 '17 at 17:45
  • $\begingroup$ Now that you've answered the question, let me make an additional comment about exercise 23. To successfully solve it, one needs to plug $h_n=O(\log n / n^3)$ into $\sum_{0<k<n} k h_k / (n-k)$, and this boils down to successfully dealing with the sum $O(\sum_{0<k<n} \log k/k^2)$. A mistake I made in my attempts was to immediately use $\log k=O(\log n)$, thus getting $O(\log n)$ for the sum. However, by noticing that the series $\sum_{k\geq 1} \log k / k^2$ converges, we get $O(1)$ for the sum! $\endgroup$ – Filip Nikšić Dec 20 '17 at 14:31
  • $\begingroup$ Thanks for your comment. --- I think now that using $h_n$ makes the solution more complicate and more mistakes are possible. --- As you've mentioned: It's only necessary to consider $g_n=O(n^{-2})$ . $\endgroup$ – user90369 Dec 20 '17 at 14:37
3
+100
$\begingroup$

We have $\enspace\displaystyle n g_n = \frac{1}{n}\sum\limits_{k\ge 0}g_k - \frac{1}{n}\sum\limits_{k\ge n}g_k + \frac{1}{n}\sum\limits_{0<k<n}\frac{k}{n-k}g_k $

with $\enspace\displaystyle g_n = \frac{G(1)}{n^2} + O\left(\frac{\ln n}{n}\right)^3 \enspace$ and $\enspace\displaystyle G(1)=e^{\zeta(2)}\,$ .

First part: $\enspace\displaystyle \sum\limits_{k\ge 0}g_k = G(1) $

With $\enspace\displaystyle O\left(\frac{G(1)}{n^2} + O\left(\frac{\ln n}{n}\right)^3\right)= O\left(\frac{1}{n^2}\right)\enspace$ we get

for the second part $\enspace\displaystyle \sum\limits_{k\ge n}g_k = O\left(\sum\limits_{k\ge n}\frac{1}{k^2}\right)=O\left(\frac{1}{n}\right)\,$ ,

where the last step comes from $\enspace\displaystyle \lim\limits_{n\to\infty}n^x\sum\limits_{k\ge n} \frac{1}{k^{1+x}}=\frac{1}{x}\enspace$ for $\enspace x>0\,$ .

The third part is $\enspace\displaystyle \sum\limits_{0<k<n}\frac{k}{n-k}g_k = O\left(\sum\limits_{0<k<n}\frac{1}{k(n-k)}\right)=O\left(\frac{\ln n}{n}\right) \,$ .

It follows: $\enspace\displaystyle g_n =\frac{1}{n}\left(\frac{G(1)}{n} - \frac{1}{n} O\left(\frac{1}{n}\right) + \frac{1}{n} O\left(\frac{\ln n}{n}\right)\right) = \frac{G(1)}{n^2} + O\left(\frac{\ln n}{n^3}\right)$

$\endgroup$
  • 1
    $\begingroup$ Exactly, the crucial thing to notice is that $(9.61)$ implies $g_n=O(n^{-2})$, an estimate that's much easier to work with in the next bootstrapping step. I knew it was something embarrassingly simple. :) $\endgroup$ – Filip Nikšić Dec 20 '17 at 14:15
  • $\begingroup$ @FilipNikšić : Yes, that was a bit irritating. The authors could have put it a little better. :-) $\endgroup$ – user90369 Dec 20 '17 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.