5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ For $n\ge 1$, $(n+1)!\le (n+1)^{n+1} \le (2n)^{n+1} = 2^{(n+1)(1+\log_2 n)}$. $\endgroup$ – András Salamon Jun 24 '13 at 9:03
10
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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})$. $\endgroup$ – Raphael Mar 15 '13 at 7:26
  • 1
    $\begingroup$ You can fix this by starting with $(n+1)!<(n+1)^n$ instead. $\endgroup$ – Shitikanth Mar 15 '13 at 8:00
9
$\begingroup$

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

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.