# Why is $\sum_{k = n}^{\infty} (\log k)^2/k^2 = O \left((\log n)^2/n \right)$?

The question comes from a statement in Concrete Mathematics by Graham, Knuth, and Patashnik on page 465.

$$\sum_{k \geq n} \frac{(\log k)^2}{k^2} = O \left(\frac{(\log n)^2}{n} \right).$$

How is this calculated?

-
I removed the $O(...)$ from the left side, I think this is the right notation. – leonbloy Jul 19 '11 at 19:50
A standard thing to try here is summation by parts: en.wikipedia.org/wiki/Summation_by_parts – Qiaochu Yuan Jul 19 '11 at 19:52
You can guess the result replacing the sum by an integral, integrating by parts. – leonbloy Jul 19 '11 at 20:01

Here's a pretty straightforward solution. The idea is to split the sum up into a main part and an error term, and generalizes to many sums where the integral test won't work because the corresponding integral is difficult.

First recall that we have $\sum_{k \ge n} \frac{1}{k^s} = O \left( \frac{1}{n^{s-1}} \right)$ (for example by the integral test, although for integer $s$ there is a more elementary way to see this). Split the sum as

$$\sum_{k=n}^{n^2} \frac{(\log k)^2}{k^2} + \sum_{k \ge n^2+1} \frac{(\log k)^2}{k^2}.$$

Since $(\log k)^2$ is eventually bounded by $k^{\epsilon}$ for all $\epsilon > 0$, the second term is $O \left( \frac{1}{n^{4-2\epsilon}} \right)$ for all $\epsilon > 0$. On the other hand, the first term is at most

$$\sum_{k=n}^{n^2} \frac{(\log n^2)^2}{k^2} \le 4 (\log n)^2 \sum_{k=n}^{\infty} \frac{1}{k^2} = O \left( \frac{(\log n)^2}{n} \right).$$

(Note that unlike the argument using the integral test, this argument doesn't optimize the constant as it stands. But one can actually replace $n^2$ with $n^{1+\epsilon}$ for any $\epsilon > 0$ and the argument carries through, and taking the limit as $\epsilon \to 0$ gives the correct constant.)

For a fun exercise in splitting sums, try getting an optimal bound for the sum described in this blog post.

-
+1, I don't fully understand why this is the least voted answer. The other solutions are ad hoc, and only work in this particular case. – Eric Naslund Jul 19 '11 at 21:21
+1: Nicely done. – mixedmath Jul 20 '11 at 1:58
Thanks for pointing me to that problem, Qiaochu. I was able to show that the bound is $O(1/\sqrt{n})$. Here's my write-up. – Antonio Vargas Jul 26 '11 at 6:20
@Antonio: very nice! – Qiaochu Yuan Jul 26 '11 at 13:11

I think the easiest way here is to simply find $\displaystyle \int_k ^{\infty} \frac {(\log x)^2}{x^2}dx$. After some work, it turns out to be $\dfrac{\log k(\log k + 2) + 2}{k}$. Oh - but I'm also somewhat confident that Qiaochu's suggestion to Sum by Parts would work as well (and give almost the same answer).

-
Will a sum always have the asymptotic properties of its integral? – Antonio Vargas Jul 19 '11 at 20:26
@acetv: for non-negative monotonically decreasing functions, yes. See en.wikipedia.org/wiki/Integral_test_for_convergence . – Qiaochu Yuan Jul 19 '11 at 20:36

Note that the function $f$ defined by $$f(x) = \frac{{(\log x)^2 }}{{x^2 }}$$ is decreasing for $x > x_0$ (for some $x_0 > 0$), and that $$\frac{{\frac{d}{{dx}}\int_x^\infty {\frac{{(\log t)^2 }}{{t^2 }}dt} }}{{\frac{d}{{dx}}\frac{{(\log x)^2 }}{x}}} = \frac{{ - \frac{{(\log x)^2 }}{{x^2 }}}}{{\frac{{2\log x - (\log x)^2 }}{{x^2 }}}} = \frac{{ - \log x}}{{2 - \log x}} \to 1 \;\; {\rm as} \;\; x \to \infty ,$$ hence also $$\frac{{\int_x^\infty {\frac{{(\log t)^2 }}{{t^2 }}dt} }}{{\frac{{(\log x)^2 }}{x}}} \to 1 \;\; {\rm as} \;\; x \to \infty.$$

EDIT (elaborating; what follows also completes mixedmath's answer):

With $f$ as above, $$f'(x) = \frac{{2\log x(1 - \log x)}}{{x^3 }},$$ implying that $f$ is decreasing on $[e,\infty)$. It follows that for any $n \geq 3$, $$\int_n^\infty {f(x)\,dx} \leq \sum\limits_{k = n}^\infty {f(k)} \leq f(n) + \int_n^\infty {f(x)\,dx} .$$ Hence $$\frac{{\int_n^\infty {f(x)\,dx} }}{{\frac{{(\log n)^2 }}{n}}} \le \frac{{\sum\nolimits_{k = n}^\infty {f(k)} }}{{\frac{{(\log n)^2 }}{n}}} \le \frac{{f(n)}}{{\frac{{(\log n)^2 }}{n}}} + \frac{{\int_n^\infty {f(x)\,dx} }}{{\frac{{(\log n)^2 }}{n}}}.$$ So from $$\frac{{f(n)}}{{\frac{{(\log n)^2 }}{n}}} = \frac{1}{n} \to 0$$ and $$\frac{{\int_n^\infty {\frac{{(\log x)^2 }}{{x^2 }}\,dx} }}{{\frac{{(\log n)^2 }}{n}}} \to 1$$ as $n \to \infty$, it follows that $$\frac{{\sum\nolimits_{k = n}^\infty {f(k)} }}{{\frac{{(\log n)^2 }}{n}}} \to 1.$$

-
That's pretty cool. I like that. – mixedmath Jul 19 '11 at 20:15