Prove que qualquer quantia em selos maior ou igual a 14 centavos pode ser obtida usando-se apenas selos de 3 e de 8 centavos.
Passo 1
O enunciado pede para mostrar que todo valor inteiro de centavos
pode ser escrito na forma
com
inteiros não negativos. O conteúdo usado aqui é forte indução sobre inteiros, aplicando o fato de que, se um valor é obtido, então somando um selo de 3 c dá outro valor também obtido.
Passo 2
Base da indução: verificamos diretamente para
:
Logo, os valores
são alcançáveis com selos de 3 e 8.
Passo 3
Passo indutivo (forte): suponha que todo inteiro
com
seja representável como
. Queremos mostrar que
também é representável.
Como já cobrimos a base até
, assumimos
. Então
o que garante que
entra na faixa da hipótese indutiva.
Passo 4
Pela hipótese indutiva, existe representação
com
. Então
ou seja,
também é combinação de 3 e 8 centavos.
Resposta
Portanto, por indução forte, todo inteiro
pode ser escrito como
com
inteiros não negativos.