Seja P(n) uma sentença aberta sobre N, e seja a in N. Suponha que:
i. P(a) é verdadeira, e
ii. qualquer que seja n in N, com n >= a, sempre que P(n) for verdadeira, segue-se que P(n+1) é verdadeira.
Então, P(n) é verdadeira para todo número natural n >= a.

Passo 1

Beleza, o enunciado diz o seguinte: temos uma propriedade aberta para e um número fixo . Sabemos duas coisas:
  1. é verdadeira (caso base).
  2. Para todo , se é verdadeira então também é (passo indutivo).
Conteúdo: estamos mostrando o Princípio da Indução Matemática usando o Princípio da Boa Ordem de . Vamos precisar entender bem a ideia de “menor elemento” em um conjunto não-vazio de naturais e usar isso pra montar uma contradição.

Passo 2

A ideia é provar por contradição. Suponha que não seja verdade que C ;=;,ninNcolon n>= a e P(n) é falsa valha para todo . Então existe pelo menos um natural tal que é falsa. Definimos o conjunto dos “contraexemplos” assim:
é
Pelo Princípio da Boa Ordem, se não é vazio, então ele tem um menor elemento; seja . Agora olhe esses dois casos:
  • Se , aí já bate de frente com a hipótese do caso base, porque sabíamos que era verdadeira. Contradição.
  • Se , então e, como é o menor contraexemplo, é verdadeira. Mas aí, pelo passo indutivo, . Logo teria de ser verdadeira. Contradição de novo.

Passo 3

Como em ambos os cenários chegamos a contradição, nossa hipótese de que não é vazio cai por terra. Logo é vazio, ou seja, não existe nenhum que seja contraexemplo.

Resposta

é verdadeira para todo número natural .

Exercícios relacionados