Use o segundo princípio da indução para provar: Que qualquer quantia em selos maior ou igual a 2 centavos pode ser obtida usando-se apenas selos de 2 e de 3 centavos.
Passo 1
Resumindo, queremos provar por indução forte (ou segundo princípio da indução) que toda quantia inteira
(em centavos) pode ser escrita como soma de selos de
e
centavos. Em termos formais, definimos a proposição
e vamos mostrar que
é verdadeira para todo inteiro
.
Passo 2
Base da indução: verificamos
e
.
-
: , ou seja, basta um selo de centavos. -
: , ou seja, basta um selo de centavos.
Portanto,e são verdadeiras.
Passo 3
Passo indutivo forte: suponha que, para algum inteiro
, a proposição
seja verdadeira para todo
tal que
. Ou seja, qualquer quantia entre
e
centavos é obtida usando apenas selos de
e
centavos.
Passo 4
Queremos provar
, isto é, que
centavos também se obtém com selos de
e
centavos.
Observe que, como , temos
Observe que, como
Pela hipótese de indução forte, a quantia
(que é
e
) pode ser formada por selos de
e
centavos. Basta, então, acrescentar mais um selo de
centavos para chegar a
. Logo,
vale.
Resposta
Por indução forte, concluímos que
é verdadeira para todo inteiro
. Dessa forma, qualquer quantia maior ou igual a
centavos pode ser obtida usando-se apenas selos de
e de
centavos.