Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

up vote 10 down vote accepted

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.

share|improve this answer
2  
+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
1  
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).

share|improve this 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. $$

share|improve this answer
    
That's pretty cool. I like that. –  mixedmath Jul 19 '11 at 20:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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