# Trouble understanding how a big-o bound proves a limit

I’m trying to understand the answer to exercise 4.5.2-10(c) in Knuth’s The Art of Computer Programming. Let $$q_n$$ denote the number of ordered pairs of integers $$(u,v)$$ in the range $$1\leq u,v \leq n$$ such that $$u$$ and $$v$$ are relatively prime. We’re trying to prove that

$$\lim_{n\rightarrow\infty} \frac{q_n}{n^2} = \sum_{k\geq 1} \frac{\mu (k)}{k^2}$$

where $$\mu$$ denotes the Möbius function. We already showed in part (b) that $$q_n = \sum_{k\geq 1} \mu (k)\lfloor n/k \rfloor ^2$$.

$$q_n - \sum_{k\geq 1} \mu (k) (n/k)^2 = O(n H_n) - O(n).$$
I have convinced myself on paper that this is true, but I’m having trouble understanding how this proves the limit. Since $$nH_n$$ increases as a function of $$n$$, it seems to me that this should imply the two functions only get further apart as $$n$$ increases. Any insight would be much appreciated :)
• $H_n = o(n)$, so $O(nH_n) = o(n^2)$; also $O(n) = o(n^2)$. Then you get the claim dividing both sides of the last equality by $n^2$. – zhoraster Jul 24 '19 at 7:34
• @zhoraster Thanks for your help! I just need another nudge for the VERY last step. The equality can be manipulated to become $q_n/n^2 - \sum_{k\geq 1} \mu(k) / k^2 = o(1)$, which implies that the the difference $\leq c$ for some positive real $c$. Now given an $\epsilon > 0$ how do I use this to get $q_n/n^2$ within $\epsilon$ of $\sum_{k\geq 1}\mu(k) / k^2$? Thanks and sorry if I'm not catching something that is entirely obvious! – marcelgoh Jul 24 '19 at 10:14
• Sorry about my last comment, I mixed up my definitions of big-o and little-o. Little-o means that for any choice of $c$ the inequality holds, i.e. for all $\epsilon > 0$ we have the difference $\leq \epsilon$, which proves the limit. Edit: @zhoraster Would you be able to post the comment as an answer so I can accept it? (I think this is how it works -- I'm new to the site.) – marcelgoh Jul 24 '19 at 10:24
$$H_n=o(n)$$, so $$O(nH_n)=o(n^2)$$; also $$O(n)=o(n^2)$$. Then you get the claim dividing both sides of the last equality by $$n^2$$.