3
$\begingroup$

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.

1 Answers 1

1

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...

  • 0
    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.2012-11-03