Seja a
e indiquemos por
uma propriedade (verdadeira ou falsa) associada a cada
. Suponhamos que: i)
é verdadeira; ii)
, se
é verdadeira, então
também o é. Prove que
é verdadeira para todo
.
Passo 1
No enunciado, temos um inteiro
e propriedades
definidas para todo
. As hipóteses são:
i) é verdadeira;
ii) , se
é verdadeira então
também o é.
Precisamos provar que é verdadeira para todo
. O conteúdo usado será a transformação da indução decrescente em indução usual em
.
i)
ii)
Precisamos provar que
Passo 2
Definimos
. Então
implica
e
. Introduzimos a propriedade
por
Assim, provar
para todo
equivale a provar
para todo
.
Passo 3
Verificamos a base de indução em
: para
temos
que é verdadeira por hipótese i).
Agora, suponha verdadeira, ou seja
verdadeira. Como
, aplicamos a hipótese ii) com
para obter
Agora, suponha
isto é
verdadeira, ou seja
Logo,
.
Passo 4
Pelo princípio da indução finita em
, concluímos que
é verdadeira para todo
.
Passo 5
Dado um
qualquer, basta escolher
. Como
é verdadeira, segue que
é verdadeira para todo
.