for a big enough n, How to detrmine which is bigger?

$2^{n^{1.001}}$ or $n!$

I have tried to make a series: $a_n = \frac{2^{n^{1.001}}}{n!}$

and then try finding the limit of $\frac{a_{n+1}}{a_n}$ and see if its bigger or smaller then one, also tried to use induction but didnt really got my anywhere

btw I know the answer is that $2^{n^{1.001}}$ is bigger


Why didn't it lead you anywhere?

\begin{aligned} \frac{a_{n+1}}{a_n} &= \frac{\frac{2^{(n+1)^{1.001}}}{(n+1)!}}{\frac{2^{n^{1.001}}}{n!}} \\ &= \frac{2^{(n+1)^{1.001}}}{(n+1)2^{n^{1.001}}} \end{aligned}

Take the log of both sides.

\begin{aligned} \log\left(\frac{a_{n+1}}{a_n}\right) &= \log\left(\frac{2^{(n+1)^{1.001}}}{(n+1)2^{n^{1.001}}}\right) \\ &= \log\left(2^{(n+1)^{1.001}}\right) -\log\left(2^{n^{1.001}}\right) - \log\left(n+1\right) \\ &= (n+1)^{1.001}\log\left(2\right) - n^{1.001}\log\left(2\right) - \log(n + 1) \end{aligned}

Divide both sides by $\log(2)$.

\begin{aligned} \log_2\left(\frac{a_{n+1}}{a_n}\right) &= (n+1)^{1.001} - n^{1.001} - \log_2(n + 1) \end{aligned}

Now, we have a new function $f(n)$ for which the following is true:

$$ f(n) = (n+1)^{1.001} - n^{1.001} - \log_2(n + 1) $$

$$ \lim_{n \to \infty}f(n) > 0 \implies 2^{n^{1.001}} > n!\\ \lim_{n \to \infty}f(n) < 0 \implies 2^{n^{1.001}} < n! $$

Let's break up this function into two parts:

$$ f(n) = (n+1)^{1.001} - \left(n^{1.001} + \log_2(n + 1)\right) $$

Now, let's repeat the process:

$$ \lim_{n \to \infty} \frac{(n+1)^{1.001}}{\left(n^{1.001} + \log_2(n + 1)\right)} > 1 \implies \lim_{n \to \infty}f(n) > 0 $$

Here, we can simply say that the highest degree term of the numerator is larger than that of the denominator, so the limit goes to $\infty$. Therefore, following the chain of implications back up, we end up with $2^{n^{1.001}} > n!$. If you followed that train of thought, you could indeed come to the answer.


Hint: $$n!\le n^n=2^{n\log_2 n}$$ Spoiler:

$2^{n\log_2 n}<2^{n^{1.001}}\iff n\log_2 n<n^{1.001}\iff \log_2n<n^{0.001}$, which is true eventually as $\log_2 n$ grows slower than any $n^\alpha$ with $\alpha>0$. (e.g. by L'Hôpital's rule on $n^{\alpha}/\log_2 n$)


Hint: Compare $$ n^{1.001}\log(2) $$ and the log of Stirling's Formula $$ n\log(n)-n+\frac12\log(2\pi n) $$

Note that since $x\gt\log(x)$ for all $x\gt0$, we have $$ \begin{align} n^{0.001} &=\color{#C00000}{n^{0.0005}}n^{0.0005}\\ &\ge\color{#C00000}{0.0005\log(n)}n^{0.0005} \end{align} $$ Therefore, for $n\gt1$, $$ \begin{align} \frac{n^{0.001}}{\log(n)} &\stackrel{\hphantom{n\to\infty}}{\ge}0.0005n^{0.0005}\\ &\stackrel{n\to\infty}{\to}\infty \end{align} $$


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.