Enuncie e demonstre a primeira e a segunda forma de indução.

Passo 1

O enunciado pede para enunciar e demonstrar as duas versões do princípio de indução em N: a forma simples (ou fraca) e a forma forte (ou completa). O conteúdo é teoria de prova por indução, e usaremos principalmente o Princípio da Boa Ordenação para as demonstrações.

Passo 2

Enunciado da primeira forma de indução (indução simples):
Suponha que P(n) seja uma propriedade definida para todo ninN. Se valem
1. P(1) (base de indução), e
2. para todo k>=1, de P(k) segue P(k+1) (passo indutivo),
então P(n) é verdadeira para todo ninN.

Passo 3

Demonstração da primeira forma usando Princípio da Boa Ordenação:
Suponha, por contradição, que o conjunto
S=ninNmid P(n) é falsa é
não seja vazio. Pelo Princípio da Boa Ordenação, S tem um menor elemento m. Como P(1) é verdadeira, m>1. Logo m-1inN e m-1notin S, de modo que P(m-1) é verdadeira. Mas pelo passo indutivo isso implica P((m-1)+1)=P(m), ou seja, P(m) é verdadeira, contradição com min S. Portanto S é vazio e P(n) vale para todo n.

Passo 4

Enunciado da segunda forma de indução (indução forte):
Suponha que Q(n) seja uma propriedade para todo ninN. Se valem
1. Q(1), e
2. para todo k>=1, de Q(1), Q(2), ···, Q(k) segue Q(k+1),
então Q(n) é verdadeira para todo ninN.

Passo 5

Demonstração de que a segunda forma decorre da primeira:
Defina P(n) pela conjunção
P(n)equiv Q(1)wed>= Q(2)wed>=cdotswed>= Q(n)
Então P(1) vale porque é Q(1). Suponha P(k) verdadeira, ou seja, Q(1),dots,Q(k) todas verdadeiras; pelo passo indutivo forte temos Q(k+1), logo P(k+1) vale. Assim pelos requisitos da primeira forma de indução, P(n) vale para todo n, e em particular cada Q(n) vale.

Resposta

Enunciamos e demonstramos a primeira forma de indução usando o Princípio da Boa Ordenação e mostramos como a segunda forma se reduz à primeira via a conjunção das hipóteses anteriores.

Exercícios relacionados