Se
, define-se sucessor de
por
. Prove que (
sempre):
.
Passo 1
O enunciado pede para mostrar que, para todo
, seu sucessor
é sempre diferente de
.
O tema é indução em e usaremos também a lei de cancelamento da soma:
O tema é indução em
Passo 2
Base da indução (
):
e como
em
, temos
Passo 3
Passo indutivo: suponha que, para algum
, vale
Precisamos mostrar que
isto é,
Suponha, por absurdo, que
. Então, aplicando cancelamento de
em ambos os lados, vem
o que é exatamente a negação da hipótese indutiva. Logo chegamos a contradição, e portanto
ou seja
.
Passo 4
Pelos passos 2 e 3, concluímos por indução que, para todo
,
Resposta
Para todo
vale
.