Can factorial be bounded by the double exponential function?

Question

I suspect this is the case, unlike the single-exponential case, but can you give a proof for:

$$ n! < 2^{2^n} $$ ?

Answer 1

One can easily see your statement holds for $n=0$ and $n=1$. Moreover, the quotients are $$\frac{(n+1)!}{n!}=n+1, \quad \frac{2^{2^{n+1}}}{2^{2^n}}=2^{2^n}. $$ This shows that the factorial grows at a slower rate, proving the inequality (formally, you need to make this into a proof by induction).

Answer 2

Yes, by induction if we use the fact that $2^{2^n} > n+1$

$$1 = 1! < 2^{2^n} = 2^2 = 4$$

Now we have if $n! < 2^{2^n}$ that

$$2^{2^{n+1}} = 2^{2^n + 2^n} = 2^{2^n}2^{2^n} > 2^{2^n} n! > (n+1)n!$$

Then by induction the result follows.

The fact that $2^{2^n}>n$ also follows from induction since. $2^{2^1} = 4 > 2$ and if $2^{2^n} > n$ we have

$$2^{2^{n+1}} = 2^{2^n + 2^n} = 2^{2^n}2^{2^n} > 2^{2^n}(n+1) > 4(n+1) > n+2$$