2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – kingW3 Apr 19 '17 at 16:29
  • $\begingroup$ 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$.) $\endgroup$ – ancientmathematician Apr 19 '17 at 16:33
1
$\begingroup$

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$

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} n^{\epsilon} = \expo{\ln\pars{n^{\epsilon}}} > 1 + \ln\pars{n^{\epsilon}} = \ln\pars{n} + \ln\pars{\mrm{e}n^{\epsilon - 1}} > \ln\pars{n} \quad\mbox{whenever}\quad\mrm{e}n^{\epsilon - 1} > 1 \end{align}

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

$\endgroup$

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.