Seja
um inteiro positivo. Prove por indução que:
.
Passo 1
O enunciado pede que se prove, para todo inteiro positivo
, que
divide
.
Informações relevantes dadas:
Informações relevantes dadas:
- A variável
é um inteiro positivo. - A afirmação a provar é
, isto é, é múltiplo de .
Passo 2
Explicação do método de prova por indução (passo-a-passo didático):
- A prova por indução tem duas etapas fundamentais:
- Caso base: verificar que a afirmação é verdadeira para o primeiro valor (aqui
). - Passo indutivo: assumir que a afirmação é verdadeira para um
arbitrário (hipótese de indução) e então mostrar que isso implica que a afirmação é verdadeira para .
- Caso base: verificar que a afirmação é verdadeira para o primeiro valor (aqui
- Razão prática: se o caso base é verdadeiro e de cada
verdadeiro segue verdadeiro, então todos os são verdadeiros (como uma fileira de dominós).
Vou aplicar exatamente essas duas etapas ao problema.
Passo 3
Caso base (
). Calcular explicitamente:
Como
é múltiplo de
, temos
. Portanto o caso base é verdadeiro.
Passo 4
Hipótese de indução. Suponha que para um certo inteiro
vale:
Isto significa que existe um inteiro
tal que
Passo 5
Passo indutivo: provar que a afirmação vale para
. Começamos manipulando
.
Observe que
Observe que
pois multiplicar por
aumenta o expoente em
e troca o sinal quando necessário. Então
Agora reescreve
como
e faça uma reorganização conveniente:
Adicione e subtraia
de modo a usar a hipótese de indução:
Verificação rápida desta identidade:
que é justamente
.
Agora use a hipótese de indução
. Substituindo:
O termo entre parênteses é inteiro, logo o lado direito é múltiplo de
. Assim concluímos que
divide
. Isso completa o passo indutivo.
Também é útil lembrar a propriedade usada: se
divide
e
divide
então
divide
; e se
divide
então
divide
. Essas propriedades justificam as manipulações acima.
Passo 6
Conclusão pela indução: como o caso base (
) é verdadeiro e provou-se que a verdade para
implica a verdade para
, segue por princípio da indução matemática que a propriedade é verdadeira para todo inteiro positivo
. Parabéns — problema provado!
Passo 7
Observação alternativa (intuição rápida, não substitui a prova por indução pedida): trabalhar em aritmética modular. Como
, elevando à potência
dá
. Portanto
o que mostra
. Isso é uma forma curta e elegante de ver o resultado.
Resposta
Para todo inteiro positivo
,
.