Prova indutiva: n! > $2^n$ para n $\geq$ 4

Provaremos agora a desigualdade n! > $2^n$ para n $\geq$ 4. Mostraremos que a função fatorial cresce mais rápido que a função exponencial.

A prova é por indução em n:

• Caso Base: Para n = 4, temos que $4! > 2^4$.
• Hipótese de Indução: Vamos supor que $(n-1)! > 2^{n-1}$.
• Caso Geral: Agora basta utilizar o resultado obtido na hipótese de indução e estender a solução para o caso geral, assim temos que

                               $2*(n-1)! > 2*2^{n-1}$

                       $2*(n-1)! > 2^n$  

         {como 2*(n-1)! é menor que n!, para n = 4, podemos substituí-lo por n! e mantemos a desigualdade}

                   $n! > 2^n$   C.Q.D.