Problem 1. Estimate $\displaystyle \sum_{i=1}^n \frac{\ln i}{\sqrt{i}}$ with an absolute error $O(1)$.

Problem 2. Estimate: $$\left|\left\{ \langle a,b,c \rangle\in \mathbb{N}_+^3 : abc\le n \right\}\right|$$ where $\mathbb{N}_+=\mathbb{N}\setminus \left\{0\right\}$, with relative error $o(1)$.

For 1. I was taught that integrals are sufficient when we want to estimate some easy sum accurate to some constant. So let $f(x)=\frac{\ln x}{\sqrt{x}}$, then $\int f(x) \mbox{d}x=2\sqrt{x}(\ln x - 2) +C$, and it's easy to check that $f'(x)>0$ for $x>e^2$. So $\int_{i-1}^{i}f(x)\le f(i)\le \int_i^{i+1}f(x)$ and we have $\int_{8}^n f(x)\le \sum_{i=9}^n f(i)\le \int_9^{n+1}f(x)$, because $\sum_{i=1}^nf(i)=\sum_{i=9}^nf(i)+O(1)$ it can be ok, but I don't know what to do next. I have lower and upper bound for this sum but how do I know that these bounds differ in only constant? Because if I knew that I think I could write that $\sum_{i=1}^n f(i)=2\sqrt{n}(\ln n -2)+O(1)$. Is it a good approach?

For 2. no ideas. I would have problems even with any estimate, so I don't know how to do it with such small error like $o(1)$. Maybe it will be a good idea to solve it firstly in $\mathbb{N}_+^2$? But I don't know how to approach this version either.


Problem 1: Yes, your approach is a good idea. To show the two bounds differ by at most a constant, it suffices to show that $\displaystyle \int^{n+1}_n \frac{ \log x}{ \sqrt{x}} dx \to 0$ as $n\to\infty.$ Try to do that.

Problem 2: Thinking about lower dimensional cases is often a good idea. In two dimensions, it asks for an estimate of the number pairs of natural numbers whose product is less than a certain constant. This is the number of lattice points under the graph of $xy=n$, and the number of lattice points is asymptotic to the area, so...

  • $\begingroup$ Ok, I've done the first one, thank you! But in second I have serious problems. I don't know exactly spcific argument for that the number of lattice points is asymptotic to the area. But if it is so, then it will be about $n\log n$ points but I'm not so sure which notation I can use. Also this doesn't tell me anything about an error. In this task I have to be very precise, $o(1)$ relative error is very small I think, and I don't even know how to aim it. $\endgroup$ – ray Aug 25 '12 at 16:06
  • $\begingroup$ @ray Here is some info on how to make the asymptotic argument rigorous. It appears hopeless to me to think we can get an error that tends to $0.$ The 2 dimensional version of your problem is known as Dirichlet's Divisor Problem and the best known estimate for that has error $\mathcal{O}(n^{131/416}).$ $\endgroup$ – Ragib Zaman Aug 25 '12 at 16:30
  • $\begingroup$ To get a relative error in the class $o(1)$ seems to be the same as getting an equivalent. $\endgroup$ – Did Aug 25 '12 at 21:24
  • $\begingroup$ As I recall, for the two-dimensional case, the result was gotten by considering $x \le \sqrt n$ and $x > \sqrt n$. For the three-dimensional case, you might look at cube root. $\endgroup$ – marty cohen Nov 3 '12 at 6:07

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.