Enuncie e demonstre a primeira e a segunda forma de indução.
Passo 1
O enunciado pede para enunciar e demonstrar as duas versões do princípio de indução em
: a forma simples (ou fraca) e a forma forte (ou completa). O conteúdo é teoria de prova por indução, e usaremos principalmente o Princípio da Boa Ordenação para as demonstrações.
Passo 2
Enunciado da primeira forma de indução (indução simples):
Suponha que seja uma propriedade definida para todo
. Se valem
.
(base de indução), e
. para todo
, de
segue
(passo indutivo),
então é verdadeira para todo
.
Suponha que
então
Passo 3
Demonstração da primeira forma usando Princípio da Boa Ordenação:
Suponha, por contradição, que o conjunto
Suponha, por contradição, que o conjunto
não seja vazio. Pelo Princípio da Boa Ordenação,
tem um menor elemento
. Como
é verdadeira,
. Logo
e
, de modo que
é verdadeira. Mas pelo passo indutivo isso implica
, ou seja,
é verdadeira, contradição com
. Portanto
é vazio e
vale para todo
.
Passo 4
Enunciado da segunda forma de indução (indução forte):
Suponha que seja uma propriedade para todo
. Se valem
.
, e
. para todo
, de
,
, ···,
segue
,
então é verdadeira para todo
.
Suponha que
então
Passo 5
Demonstração de que a segunda forma decorre da primeira:
Defina pela conjunção
Defina
Então
vale porque é
. Suponha
verdadeira, ou seja,
todas verdadeiras; pelo passo indutivo forte temos
, logo
vale. Assim pelos requisitos da primeira forma de indução,
vale para todo
, e em particular cada
vale.
Resposta
Enunciamos e demonstramos a primeira forma de indução usando o Princípio da Boa Ordenação e mostramos como a segunda forma se reduz à primeira via a conjunção das hipóteses anteriores.