Seja
um inteiro positivo. Prove por induçāo que:
.
Passo 1
O enunciado pede que se mostre que, para todo inteiro positivo
, o número
é divisível por 3. As informações dadas são:
-
é um inteiro positivo (ou seja, ). - Queremos provar a propriedade de divisibilidade
para todo desse conjunto.
Passo 2
Estratégia escolhida: prova por indução matemática sobre
. Vou explicar rapidinho como a indução funciona (sem pressa):
- Primeiro mostra-se o caso base (normalmente
), isto é, verifica-se que a propriedade vale para um valor inicial de . - Depois assume-se que a propriedade vale para um certo
(hipótese de indução) e, a partir disso, mostra-se que ela também vale para .
Se esses dois passos forem feitos, conclui-se que a propriedade vale para todo inteiro positivo.
Passo 3
Caso base (
). Calcular a expressão e verificar a divisibilidade:
Como
é divisível por
, o caso base está verificado.
Passo 4
Hipótese de indução. Suponha que para um inteiro arbitrário
valha
Pela definição de divisibilidade, isso significa que existe um inteiro
tal que
Passo 5
Passo indutivo: provar que a propriedade vale para
. Começo manipulando a expressão pedida:
Primeiro uso a propriedade de potências de :
Primeiro uso a propriedade de potências de
Então
Agora reescrevo essa expressão de forma a usar a hipótese de indução:
Adicionando e subtraindo
de forma inteligente, obtenho
Verifique expandindo o lado direito:
Pela hipótese de indução sabe-se que
. Substituindo:
O termo
é inteiro (pois
é inteiro e
), logo a expressão é múltiplo de
. Portanto
Isto completa o passo indutivo.
Passo 6
Como o caso base
é verdadeiro e o passo indutivo foi provado, pelo princípio da indução matemática a propriedade vale para todo inteiro positivo
.