Exercício 6. Prove, utilizando o princípio da indução matemática, que para todo
:
ou seja,
é divisível por 9 .
Passo 1
O enunciado pede para mostrar que, para todo
,
Informações relevantes dadas pelo enunciado:
- A expressão envolvida é
. - A afirmação a provar é que essa expressão é divisível por
para todo inteiro . - O enunciado solicita usar o princípio da indução matemática (portanto a prova será por indução).
Passo 2
Lembrete didático: o que significa “
” e o que é prova por indução.
- Definição de divisibilidade: dizer que
significa que existe um inteiro tal que . Esse chamamos de quociente inteiro da divisão de por . - Princípio da indução matemática (resumo): para provar que uma propriedade
vale para todo , faz-se: - Caso base: prova-se que
é verdadeira. - Passo indutivo: assume-se que
é verdadeira para algum (hipótese de indução) e então prova-se que é verdadeira.
Se ambos os itens valem, entãovale para todo .
Vou aplicar exatamente esse esquema à propriedade “”.
- Caso base: prova-se que
Passo 3
Caso base
. Calcular a expressão e verificar divisibilidade:
Agora calcular passo a passo:
E
é múltiplo de
, pois
Portanto
. O caso base está verificado.
Passo 4
Hipótese de indução. Suponha que para algum
a propriedade seja verdadeira, isto é, suponha que existe um inteiro
tal que
Essa é a nossa hipótese de indução; vamos usá-la para provar o caso
.
Passo 5
Escrever a expressão para
e relacioná‑la com a expressão do caso
.
A expressão que queremos provar divisível por é
A expressão que queremos provar divisível por
Vamos introduzir uma notação curta: seja
Então a hipótese de indução é
para algum inteiro
. Agora expresse
em termos de
:
Observe que
. Então
Reescrevendo
multiplicado por
:
Agora faça a diferença
:
Simplificando termo a termo:
Portanto chegamos à relação útil
Passo 6
Usar a hipótese de indução e propriedades básicas de divisibilidade para concluir.
- Pela hipótese temos
para algum inteiro . Então
que é múltiplo de
(porque
e
é inteiro).
- Além disso
também é múltiplo de (produto de por um inteiro). - A soma de dois múltiplos de
é outro múltiplo de . Como por (Passo 5)
e os dois termos no lado direito são múltiplos de
, segue que
também é múltiplo de
. Ou seja, existe um inteiro (escrevendo explicitamente)
tal que
Isso completa o passo indutivo: a verdade para
implica a verdade para
.
Passo 7
Conclusão por indução. Como verificamos o caso base
(Passo 3) e mostramos que
implica
(Passos 4–6), pelo princípio da indução matemática deduzimos que, para todo inteiro
,
Parabéns — a propriedade está provada.
Passo 8
Comentário curto e útil (não obrigatório na prova): em linguagem de congruências, observa‑se que
, então
. Também
e
, daí
o que dá uma prova rápida alternativa de que a expressão é divisível por
.