I'm going through a few proofs to make sure I understand them and in two of the proofs, there is a step I don't understand.

1) In the first, we have that $f(x) = g(x) + ln\left(\frac{\lfloor x \rfloor}{x}\right)$. So, if $|g(x)| < \frac{2}{\lfloor x \rfloor}$, then $|f(x)| < \frac{2}{\lfloor x \rfloor} + \frac{1}{\lfloor x \rfloor}$. To me, this implies that $\left|ln\left(\frac{\lfloor x \rfloor}{x}\right)\right| < \frac{1}{\lfloor x \rfloor}$ and, unless I've gone wrong, this is not true?

2) In the second, we have that $\int_{1}^x \! \frac{ln(u)}{u} \, \mathrm{d}u = \frac{1}{2} \, ln^2(x)$. We use this on $\int_{1}^{\lfloor x \rfloor} \frac{ln(u)}{u} \, \mathrm{d}u$ and, somehow, get $\frac{1}{2} ln^2(x)$ and not $\frac{1}{2} ln^2(\lfloor x \rfloor)$. I assumed that this was because it was absorbed into O$\left(\frac{ln(x)}{x}\right)$, but I couldn't prove this.

Would anyone be able to help me here? It's to prove some asymptotic formulas for $\displaystyle\sum\limits_{n \leq x} \frac{1}{n}$ and $\displaystyle\sum\limits_{n \leq x} \frac{ln(n)}{n}$ and I'm following Shapiro's derivations.


If we write $x = k+h$ with $0 \leqslant h < 1$, then we have

$$\left\lvert \ln \frac{\lfloor x\rfloor}{x}\right\rvert = \ln \frac{k+h}{k} = \ln \left(1+\frac{h}{k}\right) \leqslant \frac{h}{k} < \frac{1}{k} = \frac{1}{\lfloor x\rfloor}.$$

In the second, we have

$$\ln x = \ln \left(\lfloor x\rfloor \frac{x}{\lfloor x\rfloor}\right) = \ln \lfloor x\rfloor + \ln \frac{x}{\lfloor x\rfloor},$$

and we saw above that the last terms is smaller than $1/\lfloor x\rfloor$, so

$$\ln^2 x < \ln^2 \lfloor x\rfloor + 2 \frac{\ln \lfloor x\rfloor}{\lfloor x\rfloor} + \frac{1}{\lfloor x\rfloor^2},$$

so the difference can be absorbed in an $O\left(\frac{\ln x}{x}\right)$ term.

  • $\begingroup$ Thank you very much. I'm a bit slow, so I'm just going to go through it now and make sure that I can understand it. So, give me a second. $\endgroup$ – user60126 Feb 28 '14 at 23:33
  • $\begingroup$ Sure, no problem. If something isn't clear, don't hesitate to ask. $\endgroup$ – Daniel Fischer Feb 28 '14 at 23:34
  • $\begingroup$ Ok, so I have two questions. I'll understand if you want to let me ponder over them and not answer them. :D The first is why is ln(1+h/k) < (h/k)? I came up with this possibility in my notes but couldn't think of why it would be true. The second is, if we have that f(x) $- ln^2(\lfloor x \rfloor) \in$ O(ln(x)\x), then we are allowed to add two terms, take something smaller and it is still in O(ln(x)\x)? If I can get the answer to those two questions, I understand the proofs. $\endgroup$ – user60126 Feb 28 '14 at 23:49
  • 1
    $\begingroup$ For the first, we have $\ln (1+x) < x$ for $x > 0$ (and since $h = 0$ is possible, that ought to have been a $\leqslant$ there). You can see that for example by the mean value theorem, $\ln (1+x) - \ln 1 = \ln'(1+\xi)\cdot x = \frac{1}{1+\xi}\cdot x$. $\endgroup$ – Daniel Fischer Feb 28 '14 at 23:54
  • 1
    $\begingroup$ It depends. If you know (can prove) that $f(x) - \ln^2 x$ is always non-negative, then we don't need it. Otherwise, we can have $$\left\lvert f(x) - \ln^2 x\right\rvert > \left\lvert f(x)-\ln^2 \lfloor x\rfloor\right\rvert,$$ and then we need an estimate to show that it still has the same $O(\cdot)$-bound. $\endgroup$ – Daniel Fischer Mar 1 '14 at 11:42

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.