Dê dois exemplos diferentes de demonstrações que usem a indução completa.

Passo 1

O enunciado pede dois exemplos distintos de demonstrações que usem a indução completa (também chamada de indução forte). Nesse tipo de prova, para mostrar que uma propriedade P(n) vale para todo inteiro a partir de uma base, assumimos que ela vale para todos os inteiros menores que n e, com isso, provamos que vale para n. Vamos dar dois exemplos clássicos e didáticos.

Passo 2

Exemplo 1: todo inteiro n\ge2 é primo ou produto de primos
Definimos a propriedade
P(n):\text{“ou \(n\) é primo, ou pode ser escrito como produto de números primos.”}éú
Base de indução:
P(2)\text{ e }P(3)
são verdadeiras porque 2 e 3 são primos.
Hipótese de indução completa: suponha que P(k) seja verdadeira para todo inteiro k com 2\le k<n.
Passo de indução: consideremos n.
  • Se n for primo, está tudo bem.
  • Se n for composto, existe decomposição n=a\cdot b com 2\le a\le b<n.
    Pelas hipóteses P(a) e P(b) (pois a,b<n), ambos são primos ou produtos de primos.
    Logo n=a\cdot b também é produto de primos.
Concluímos que P(n) vale para todo n\ge2.

Passo 3

Exemplo 2: todo inteiro n\ge12 pode ser escrito como 4a+5b com a,b\ge0
Definimos
Q(n):\text{“existe \(a,b\ge0\) inteiros tais que }n=4a+5b\text{.”}
Bases de indução (casos iniciais):
Q(12):12=3\cdot4+5\cdot0,\quad Q(13):13=2\cdot4+5\cdot1,
Q(14):14=1\cdot4+5\cdot2,\quad Q(15):15=0\cdot4+5\cdot3.
Hipótese de indução completa: suponha Q(k) verdadeira para todo inteiro k com 12\le k\le n.
Passo de indução: queremos Q(n+1).
  • Se n+1 estiver entre 12 e 15, já cobrimos no caso-base.
  • Se n+1\ge16, então (n+1)-4\ge12.
    Pela hipótese, existe representação \,(n+1)-4=4a+5b.
    Portanto
n+1 = 4(a+1) + 5b,
ou seja, Q(n+1) vale.
Assim Q(n) vale para todo n\ge12.

Resposta

(1) Demonstração de que todo inteiro \,n\ge2, é primo ou produto de primos.
(2) Demonstração de que todo inteiro \,n\ge12, pode ser escrito como 4a+5b com a,b\ge0.

Exercícios de Livros Relacionados