Seja o conjunto
. Prove que
.
Passo 1
O enunciado define
e pede que provemos . Vamos usar o princípio da indução em
e a definição recursiva da adição em
:
e pede que provemos
Passo 2
(Base da indução)
Para devemos verificar que
. Mas pela primeira cláusula da definição recursiva,
Para
e também
. Logo
ou seja,
.
Passo 3
(Passo indutivo)
Suponha como hipótese de indução que algum satisfaz
Suponha como hipótese de indução que algum
Precisamos mostrar que
, ou seja,
Pela definição recursiva da adição no segundo termo, temos
Pela hipótese de indução
, então
Novamente pela definição recursiva, agora aplicada a
, obtemos
Portanto
mostrando que
.
Pelo princípio da indução em
, concluímos
.