Consideramos a afirmação:
: 3 divide
e
: 3 divide
em que n é um inteiro natural.
1 - Provar por recorrência que
é verdadeira para todo inteiro natural n .
1 - Provar por recorrência que
Passo 1
O enunciado dá a afirmação
: "3 divide
" onde
é um inteiro natural. A tarefa é provar, por indução (recorrência), que
é verdadeira para todo inteiro natural
. As informações relevantes são: o enunciado fornece a expressão
e promete que queremos mostrar que esse número é múltiplo de 3 para todo
. Não há outras condições escondidas.
Passo 2
Relembrando o que é prova por indução (do jeito bem prático): precisamos verificar dois pontos:
- base da indução: provar que
vale para um primeiro valor natural (normalmente ); - passo indutivo: assumir que
é verdadeira para um arbitrário e mostrar que então também é verdadeira. Se ambos os pontos forem feitos, concluímos que vale para todo .
Passo 3
Base da indução. Vamos checar
:
Como
é divisível por
(obviamente),
é verdadeira.
Passo 4
Preparando o passo indutivo: vamos usar duas propriedades simples de divisibilidade que são intuitivas e fáceis de justificar:
- Se
divide (escrevemos ), então divide para qualquer inteiro . Porque implica . - Se
divide e divide , então divide . Porque e implica .
Essas propriedades serão usadas na sequência.
Passo 5
Passo indutivo. Suponha que, para algum
, a hipótese de indução seja verdadeira, isto é:
Queremos mostrar que
.
Passo 6
Manipulamos
de forma a usar a hipótese de indução:
Agora escrevemos isso separando um múltiplo de
:
Observe que a decomposição acima está correta porque
.
Passo 7
Aplicando a hipótese e as propriedades de divisibilidade: pela hipótese temos
. Pela primeira propriedade, multiplicando por
ainda temos
. Também é claro que
. Pela segunda propriedade (soma de múltiplos de
é múltiplo de
), concluímos que
Como
, obtemos
. Ou seja,
.
Passo 8
Concluímos a indução: como verificamos a base
e mostramos o passo indutivo
, por princípio da indução matemática
é verdadeira para todo
.
Resposta
Para todo
,
.