Prove, usando indução finita, que se
é um número ímpar e
então
.
Passo 1
Então, o que a gente precisa provar é: “Se
é um número ímpar e
, então
Isso é um problema de aritmética modular que a gente vai resolver por indução finita. Para isso, precisamos
- Entender o princípio da indução: mostrar o caso base (
- Saber manipular potências e congruências modulares.
- Usar a expansão binomial para o passo indutivo.
A partir do próximo passo, começamos a prova de verdade.
Passo 2
Precisamos mostrar que, para
, vale
Como
Repare que
é o produto de dois números consecutivos, logo um deles é par, então
é múltiplo de 2. Portanto
é múltiplo de
e podemos escrever
para algum inteiro
Logo o caso base está ok.
Passo 3
Suponha que, para um certo
, valha a hipótese de indução:
Isso quer dizer que existe um inteiro
Queremos mostrar que então
Começamos elevando
ao quadrado, porque
:
Agora usamos a expansão binomial:
Então
Repare que tanto o segundo termo
quanto o terceiro
são múltiplos de
. Logo podemos escrever
para algum inteiro
E isso é exatamente o que queríamos no passo indutivo.
Resposta
Por indução finita, mostramos que para todo inteiro
e todo
ímpar vale