How to prove $(n+1)! = O(2^{(2^n)})$

Question

I am trying to prove $(n+1)! = O(2^{(2^n)})$. I am trying to use L'Hospital rule but I am stuck with infinite derivatives.

Can anyone tell me how i can prove this?

Answer 1

You can compare ratios of adjacent values: $(n+1)!/n! = n+1$ versus $2^{2^n}/2^{2^{n-1}} = 2^{2^{n-1}}$. Since $n+1\leq 2^{2^{n-1}}$ for $n \geq 1$, you can prove using mathematical induction that $(n+1)! \leq 2^{2^n}$.

Answer 2

Well, since this upper bound is not nearly tight, you can just use basic transformations to get

$$(n+1)!< (n+1)^{n}=2^{\log (n+1)^{n}}= 2^{n\log (n+1)}=O(2^{n\log n})\subset O(2^{(2^n)}). $$

Answer 3

Using de l'Hôpital's rule on discrete functions is meaningless; you would have to use continuous extension. For factorials, that would be the Gamma function. For discrete functions, there is Stolz–Cesàro.

In either case, considering difference or differential quotients does not make sense for (super)exponential functions: since growth is at least of the same order as the function value itself, application of such rules does not simplify the situation.

In order to deal with factorials in asymtotics, Stirling's approximation is often helpful:

$\qquad \displaystyle n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$

Therefore, $n! \in o(n^n)$. Furthermore, since

$\qquad\displaystyle \frac{n \log n}{2^n \log 2} \xrightarrow{n \to \infty} 0$

and $e^x$ is a non-decreasing and convex function¹, we have

$\qquad \displaystyle \lim_{n \to \infty} \frac{n^n}{2^{2^n}} = \lim_{n \to \infty} \frac{e^{n \log n}}{e^{2^n \log 2}} = \lim_{n \to \infty} \frac{n \log n}{2^n \log 2} = 0$.

Therefore, $n^n \in o(2^{2^n})$. Together (since $o$ is transitive) we get the desired result.

For more general advice for comparing functions, see here.

---

1. There seems to be some folklore around this technique; statements like "apply a monotone function to numerator and denominator, the limit stays the same" are not valid in general.