Seja a in Z e indiquemos por P(0) uma propriedade (verdadeira ou falsa) associada a cada n <= a. Suponhamos que: i) P(a) é verdadeira; ii) forall n <= a, se P(n) é verdadeira, então P(n-1) também o é. Prove que P(n) é verdadeira para todo n <= a.

Passo 1

No enunciado, temos um inteiro a e propriedades P(n) definidas para todo n<= a. As hipóteses são:
i) P(a) é verdadeira;
ii) forall n<= a, se P(n) é verdadeira então P(n-1) também o é.
Precisamos provar que P(n) é verdadeira para todo n<= a. O conteúdo usado será a transformação da indução decrescente em indução usual em N.

Passo 2

Definimos m = a - n. Então n<= a implica m>=0 e minN. Introduzimos a propriedade Q(m) por
Q(m) := P(a - m)
Assim, provar P(n) para todo n<= a equivale a provar Q(m) para todo minN.

Passo 3

Verificamos a base de indução em N: para m=0 temos
Q(0) = P(a)
que é verdadeira por hipótese i).
Agora, suponha Q(m) verdadeira, ou seja P(a-m) verdadeira. Como a-m<= a, aplicamos a hipótese ii) com n=a-m para obter
P((a-m)-1)é verdadeira, é
isto é P(a - (m+1)) verdadeira, ou seja
Q(m+1)é verdadeira é
Logo, Q(m)Rightarrow Q(m+1).

Passo 4

Pelo princípio da indução finita em N, concluímos que Q(m) é verdadeira para todo minN.

Passo 5

Dado um n<= a qualquer, basta escolher m=a-n>=0. Como Q(m)=P(n) é verdadeira, segue que P(n) é verdadeira para todo n<= a.

Resposta

P(n) é verdadeira para todo n<= a.

Exercícios de Livros Relacionados