Objetivo final: provar que \,2^{n}<n!\, vale para todo inteiro n\ge 4.
Passo 2
Vamos começar verificando a base do tipo de prova que vamos usar (não se preocupe: vou explicar a técnica à medida que a utilizo). Teste para n=4:
2^{4}=16 \qquad\text{e}\qquad 4!=24.
Como \,16<24, concluímos que p(4) é verdadeira. Este é o “passo inicial” que garante que a propriedade começa a valer a partir de n=4.
Passo 3
Agora enunciamos a hipótese de indução (vou explicar o que isso significa): suponha que para algum inteiro fixo k\ge 4 a propriedade seja verdadeira, isto é, suponha que
2^{k}<k!.
Isto é uma hipótese provisória — assumimos que vale para k e vamos mostrar que então ela também vale para k+1. Mostrar isto para um k arbitrário faz a máquina da indução “rodar” para todos os inteiros seguintes.
Passo 4
Preparando o que vamos comparar para passar de k para k+1. Observe as fórmulas:
A partir da hipótese de indução 2^{k}<k! podemos multiplicar ambos os lados por 2 (multiplicação por número positivo preserva desigualdade), obtendo
2^{k+1}=2\cdot 2^{k}<2\cdot k!.
Passo 5
Comparar agora 2\cdot k! com (k+1)\cdot k!. Como k! é positivo para todo k\ge 1, podemos dividir por k! ou simplesmente observar o fator comum. Para todo k\ge 4 temos k+1\ge 5, então em particular
2 < k+1.
Multiplicando essa desigualdade por k! (positivo) obtemos
2\cdot k! < (k+1)\cdot k! = (k+1)!.
Juntando com o que já tínhamos em
Passo 6
2^{k+1} < 2\cdot k! < (k+1)!.
Logo
2^{k+1} < (k+1)!,
ou seja, p(k+1) é verdadeira sempre que p(k) for verdadeira para algum k\ge 4.
Passo 7
Conclusão por indução matemática: como mostramos a base p(4) verdadeira (