Usando indução matemática, mostre que é possível obter qualquer valor igual ou superior a 20 cêntimos usando apenas selos de 5 ou 6 cêntimos.
Passo 1
O enunciado pede para provar, por indução matemática, que para qualquer inteiro n ≥ 20 existe uma combinação de selos de 5 cêntimos e 6 cêntimos que soma n. O conteúdo principal é indução (forte), e vamos precisar usar a hipótese para vários casos anteriores.
Passo 2
Vamos fazer o caso base verificando explicitamente n = 20, 21, 22, 23 e 24:
Para n = 20:
Para n = 21:
Para n = 22:
Para n = 23:
Para n = 24:
Assim, todos os inteiros de 20 a 24 podem ser obtidos.
Passo 3
Suponha agora, como hipótese de indução forte, que para todo inteiro m com 20 ≤ m ≤ k (k ≥ 24) existe combinação de selos de 5 e 6 que soma m.
Passo 4
Queremos mostrar que k+1 também pode ser obtido. Observe que k ≥ 24 implica k + 1 − 5 ≥ 20. Pela hipótese de indução forte, existe combinação de selos que soma k + 1 − 5. Basta então adicionar mais um selo de 5 cêntimos para obter k+1:
Passo 5
Pela base e pelo passo indutivo, pelo princípio da indução forte concluímos que todo inteiro n ≥ 20 pode ser escrito como combinação de 5 e 6 cêntimos.
Resposta
Por indução, fica provado que para todo inteiro n ≥ 20 existem inteiros não negativos a e b tais que n = 5a + 6b, ou seja, qualquer valor igual ou superior a 20 cêntimos pode ser obtido usando apenas selos de 5 ou 6 cêntimos.