# Proving $n^\epsilon > \log(n)$ for sufficiently large $n$

I'd like to show that for all $\epsilon > 0$, there exists an $N$ such that for all $n \geq N$ the following holds: $n^\epsilon > \log(n)$. I'm having trouble justifying this.

My intuition says this should hold. Writing $n = 2^k$ gives an inequality of the form $(2^\epsilon)^k > k$. This should hold for sufficiently large $k$ (and therefore $n$) because $2^\epsilon > 1$, so the function $(2^\epsilon)^k$ grows much faster than $k$. (This is also the approach described in this question.)

However, I was wondering if there is a more "rigorous" way to justify this inequality.

• If the limit of $\frac{n^\epsilon}{\log n}$ is $<1$ then for sufficiently large $n$ we have the inequality by the definition of the limit.Though I guess it's a bit trivial. – kingW3 Apr 19 '17 at 16:29
• I'd use $(1+x)^k\geqslant \binom{k}{2}x^2\geqslant k$ for $k\geqslant$ whatever, and then tidy it up. (Here $1+x=2^\epsilon$.) – ancientmathematician Apr 19 '17 at 16:33

Provided you have proved L'Hôpital's rule (as you should have in a real analysis course), this is pretty straightforward.

Fix $\epsilon>0$, we have $$\lim_{n\rightarrow \infty}\frac{\log n}{n^\epsilon}\stackrel{\text{L'Hôpital's rule}}{=} \lim_{n\rightarrow \infty}\frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}}=0<1$$ Proving that for sufficiently large $n$, $\log n<n^\epsilon$

If you are willing to define the logarithm of $n$ by $$\int_1^n \frac 1t \, dt$$ this follows from the fact that $t^\epsilon \to \infty$ as $t \to \infty$.

There is an index $N_1$ with the property that $t \ge N_1$ implies $t^\epsilon > \dfrac 2 \epsilon$. Thus if $n \ge N_1$ you get $$\log n - \log(N_1) = \int_{N_1}^{n} \frac 1t \, dt < \frac \epsilon 2\int_{N_1}^n t^{\epsilon - 1} \, dt < \frac \epsilon 2\int_0^n t^{\epsilon - 1} = \frac 12 n^\epsilon.$$

There is also an index $N_2$ with the property that $t \ge N_2$ implies $\log(N_1) < \dfrac 12 t^\epsilon$. Thus if $N = \max \{N_1,N_2\}$ then $$n \ge N \implies \log n < n^\epsilon.$$

This is a consequence of the inequality $\log x \leq x - 1$ for all positive $x$ with equality holding only when $x=1$. Given any $\epsilon>0$ choose a $\delta$ such that $0<\delta<\epsilon$. Then we have $$\delta\log x=\log x^{\delta} <x^{\delta} - 1$$ or $$\log x<\frac{x^{\delta}} {\delta}$$ and this is clearly less than $x^{\epsilon}$ if $x^{\epsilon-\delta} >1/\delta$. This happens for all large values of $x$ because $\epsilon>\delta$.


$\ds{\mrm{e}n^{\epsilon - 1} > 1 \implies n^{\epsilon - 1} > {1 \over \mrm{e}}\implies \bbx{\ds{n > {1 \over \mrm{e}^{1/\pars{\epsilon - 1}}}}}}$. The "$\ds{\epsilon = 1}$ case" is trivial.