Why does this inequality stand?

Question

I stand that $\log n=O(n^{\epsilon})$ for any $\epsilon >0$.

At a previous example we have shown that $$e^{n^{\epsilon}} \geq \frac{n^{\epsilon d}}{d!}$$ where $d=\lfloor \frac{1}{\epsilon}\rfloor+1>\frac{1}{\epsilon}$, so $\epsilon d>1$ and we have $$e^{n^{\epsilon}} \geq \frac{n^{\epsilon d}}{d!} \geq n$$ for $n \geq n_0=\lfloor (d!)^{(1/(ed-1)}\rfloor$.

Taking logarithms we get the result.

Could you explain to me why the following stands??

$$e^{n^{\epsilon}} \geq \frac{n^{\epsilon d}}{d!} \geq n$$ for $n \geq n_0=\lfloor (d!)^{(1/(ed-1)}\rfloor$

Answer 1

Not answering the question. A total different approach can be this one:

$$\log x=\int_1^x \frac{dt}{t} \le \int_1^x \frac{dt}{t^\alpha}$$ for $\alpha < 1$. Hence: $$\log x \le \frac{1}{1-\alpha}x^{1-\alpha}$$ and $1-\alpha$ is any positive real here.

Answer 2

If I understand correctly, you've already understood why $e^{n^{\epsilon}} \ge \frac{n^{\epsilon d}}{d!}$, and you want to see why $$\frac{n^{\epsilon d}}{d!} \geq n$$ for sufficiently large $n$. Well, before going further, recall that $\epsilon$ and $d$ are fixed numbers such that $\alpha = \epsilon d > 1$; setting $M = d!$, we have an inequality of the form $$\frac{n^\alpha}{M} \geq n,$$ which clearly works for sufficiently large $n$ (because $\alpha > 1$).

Now into the specifics. First and foremost, consider the function $$f(x) = \frac{x^{\epsilon d}}{d!} - x,$$ and observe that $f'(x) = \frac{\epsilon x^{\epsilon d - 1}}{(d-1)!} - 1$, which is $\geq 0$ if $x \geq \left(\frac{(d-1)!}{\epsilon}\right)^{1/(\epsilon d - 1)}$ (i.e., $f$ is increasing from this point on).

Now, setting $x_0 = (d!)^{1/(\epsilon d - 1)}$ (notice that $d! > \frac{(d-1)!}{\epsilon}$ because $\epsilon d > 1$), we have $f'(x) \geq 0$ for every $x \geq x_0$, so all we need to prove is that $f(x_0) \geq 0$. Now this is straightforward, since $$\frac{x_0^{\epsilon d}}{d!} = \frac{x_0^{\epsilon d - 1} \cdot x_0}{d!} = \frac{d! \cdot x_0}{d!} = x_0, $$ so that $f(x_0) = 0$. Therefore, the inequality holds whenever $n \geq \lceil x_0 \rceil$.