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

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?

• For $n\ge 1$, $(n+1)!\le (n+1)^{n+1} \le (2n)^{n+1} = 2^{(n+1)(1+\log_2 n)}$. Jun 24, 2013 at 9:03

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

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

• The third term is at least confusing if not wrong, depending on how you put parenthesis. The last equality is not true; $2^{(n+1)\log(n+1)} = 2^{n\log(n+1)} \cdot (n+1) \in \omega(2^{n \log n})$.
– Raphael
Mar 15, 2013 at 7:26
• You can fix this by starting with $(n+1)!<(n+1)^n$ instead. Mar 15, 2013 at 8:00

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.
• can we replace n with log n in stirlings equation and say that $(\log n)! = O((\log n)^{\log n})$
– Sid
Oct 15, 2012 at 8:36
• It's an increasing, continuous function, so I don't see why not.
– Raphael
Oct 15, 2012 at 8:42