Question

Utilize o segundo princıpio de induçao e prove que, qualquer valor postal maior ou igual a duas unidades monetarias pode ser obtido usando- se somente selos com valor de 2 e 3.

Answer 1

A seguinte fórmula pode ser deduzida a partir dos dados fornecidos na questão:

2n + 3n ≥ n, ∀ n ≥ 2  Utilizando o Segundo Princípio de Indução, temos que seguir três passos.  1 - CASO N = 2     Devemos provar que a fórmula é válida para o primeiro elemento. Logo,     2 × 2 + 3 × 2 = 4 + 6 = 10 ≥  2  2 - HIPÓTESE DE INDUÇÃO. PARA K ≥  2 SUPONHAMOS QUE:       2n + 3n ≥ n, ∀2 ≤ n ≤  k.  3 - DEVEMOS PROVAR O CASO K+1. OU SEJA, PROVEMOS QUE:      2(K+1) + 3(K+1) ≥ (K+1)    PROVA:                 [aplicando a distributiva na fórmula acima, temos]                 2k + 2 + 3k + 3 = 2k + 3k + 5                 [pelo passo 2, sabemos que  2k + 3k ≥ k. Logo,]                 ≥  k + 5                 [e como 5 é estritamente maior que 1, temos]                 > k +1     Logo, 2(k+1) + 3(k+1) ≥  k+1     Portanto está provado por indução.