Dê dois exemplos diferentes de demonstrações que usem a indução completa.
Passo 1
O enunciado pede dois exemplos distintos de demonstrações que usem a indução completa (também chamada de indução forte). Nesse tipo de prova, para mostrar que uma propriedade
vale para todo inteiro a partir de uma base, assumimos que ela vale para todos os inteiros menores que
e, com isso, provamos que vale para
. Vamos dar dois exemplos clássicos e didáticos.
Passo 2
Exemplo 1: todo inteiro
é primo ou produto de primos
Definimos a propriedade
Definimos a propriedade
Base de indução:
são verdadeiras porque
e
são primos.
Hipótese de indução completa: suponha que
seja verdadeira para todo inteiro
com
.
Passo de indução: consideremos
.
- Se
for primo, está tudo bem. - Se
for composto, existe decomposição com .
Pelas hipótesese (pois ), ambos são primos ou produtos de primos.
Logotambém é produto de primos.
Concluímos que
vale para todo
.
Passo 3
Exemplo 2: todo inteiro
pode ser escrito como
com
Definimos
Definimos
Bases de indução (casos iniciais):
Hipótese de indução completa: suponha
verdadeira para todo inteiro
com
.
Passo de indução: queremos
.
- Se
estiver entre 12 e 15, já cobrimos no caso-base. - Se
, então .
Pela hipótese, existe representação.
Portanto
ou seja,
vale.
Assim
vale para todo
.
Resposta
(1) Demonstração de que todo inteiro
, é primo ou produto de primos.
(2) Demonstração de que todo inteiro , pode ser escrito como
com
.
(2) Demonstração de que todo inteiro