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 n\ge2 (em centavos) pode ser escrita como soma de selos de 2 e 3 centavos. Em termos formais, definimos a proposição
P(n):\quad\text{“\(n\) pode ser obtido usando apenas selos de 2 e 3 centavos.”}
e vamos mostrar que P(n) é verdadeira para todo inteiro n\ge2.

Passo 2

Base da indução: verificamos P(2) e P(3).
  • P(2): 2=2, ou seja, basta um selo de 2 centavos.
  • P(3): 3=3, ou seja, basta um selo de 3 centavos.
    Portanto, P(2) e P(3) são verdadeiras.

Passo 3

Passo indutivo forte: suponha que, para algum inteiro n\ge3, a proposição P(k) seja verdadeira para todo k tal que 2\le k\le n. Ou seja, qualquer quantia entre 2 e n centavos é obtida usando apenas selos de 2 e 3 centavos.

Passo 4

Queremos provar P(n+1), isto é, que n+1 centavos também se obtém com selos de 2 e 3 centavos.
Observe que, como n\ge3, temos
n+1 \;\ge\; 4 \quad\Longrightarrow\quad (n+1)-2 \;\ge\; 2.
Pela hipótese de indução forte, a quantia (n+1)-2 (que é \ge2 e \le n) pode ser formada por selos de 2 e 3 centavos. Basta, então, acrescentar mais um selo de 2 centavos para chegar a n+1. Logo, P(n+1) vale.

Resposta

Por indução forte, concluímos que P(n) é verdadeira para todo inteiro n\ge2. Dessa forma, qualquer quantia maior ou igual a 2 centavos pode ser obtida usando-se apenas selos de 2 e de 3 centavos.

Exercícios relacionados