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

Problem Detail: 

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?

Asked By : Sid

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6075