indução forte e fraca

Prévia do material em texto

Indução Matemática
 Princípio da Indução Matemática:
• P(1) verdadeira
• (∀k)[P(k) verdadeira → P(k+1) verdadeira]
• ENTÃO P(n) verdadeira para todos os n inteiros positivos
 O Princípio da Indução Matemática é uma implicação, cuja tese 
é: “Uma sentença da forma P(n) é verdadeira para todos os 
inteiros n positivos”.
 Portanto, quando desejarmos demonstrar que alguma propriedade 
é válida para qualquer inteiro positivo n,podemos tentar usar 
a indução matemática como técnica de demonstração.
 Demonstração por indução:
• estabelecemos inicialmente a veracidade da sentença P(1), 
que é chamada BASE DA INDUÇÃO ou PASSO BÁSICO DA INDUÇÃO
• Estabelecer que P(k) → P(k+1), que é chamado PASSO 
INDUTIVO
• P(k) é chamada SUPOSIÇÃO INDUTIVA ou HIPÓTESE INDUTIVA 
quando assumimos que P(k) é verdadeira com o objetivo de 
demonstrar o passo indutivo
 A indução, apesar do nome, é uma técnica de demonstração 
dedutiva, isto é, uma forma de demonstrar uma conjectura que 
possivelmente foi formulada por um raciocínio indutivo.
 EXEMPLOS:
1. Prove que 1 + 3 + 5 + ... + (2n – 1) = n2     (1)
para qualquer inteiro positivo n
• A propriedade P(n) é a equação (1) acima (a soma de 
todos os inteiros positivos ímpares menores que n são 
igual ao quadrado de n)
• Podemos provar que a equação (1) é verdadeira para um 
determinado valor de n, pela substituição de n na 
equação. Contudo não poderemos substituir todos os 
valores inteiros positivos.
• Demonstração por indução matemática:
• Passo básico
P(1) (o valor da equação (1) quando n assume o 
valor  1)
1 = 12
• Hipótese de indução: assuma que P(k) é verdadeira para 
um inteiro positivo arbitrário k, que é o valor da 
equação (1) quando n vale k, ou seja
1 + 3 + 5 + ... + (2k ­ 1)= k2 (2)
• Usando a hipótese de indução, queremos mostrar que 
P(k+1), que é o valor da equação (1) quando n assume o 
valor de k+1, é igual (k+1)2  (3)
• A chave da demonstração por indução é encontrar um 
modo de relacionar o que se deseja mostrar P(k+1), 
equação(3), com o que hipótese de indução da P(k), da 
equação 2, que assumimos como verdadeira
• Reescrevendo P(k+1) usando a hipótese indutiva:
1 + 3 + 5 + ... + (2k – 1) + (2(k + 1) ­ 1) =
k2 + 2k + 2 ­ 1 =
k2 + 2k + 1 =
(k + 1)2 cqd
2. Prove que 1 + 2 + 22 + 23 + ... + 2n = 2n+1 ­ 1  (1)
para qualquer inteiro n ≥ 1
• Passo básico
P(1) (o valor da equação (1) quando n assume o 
valor  1)
1 + 2 = 2n+1 ­ 1 = 4 ­ 1 = 3 (verdadeira)
• Hipótese de indução: assuma que P(k) é verdadeira para 
um inteiro positivo arbitrário k, que é o valor da 
equação (1) quando n vale k, ou seja
1 + 2 + 22 + 23 + ... + 2k = 2k+1 ­ 1 (2)
• Usando a hipótese de indução, queremos mostrar que 
P(k+1), que é o valor da equação (1) quando n assume o 
valor de k+1, é igual 2k+1+1 ­ 1  (3)
• A chave da demonstração por indução é encontrar um 
modo de relacionar o que se deseja mostrar P(k+1), 
equação(3), com o que hipótese de indução da P(k), da 
equação 2, que assumimos como verdadeira
• Reescrevendo P(k+1) usando a hipótese indutiva:
1 + 2 + 22 + 23 + ... + 2k + 2k+1 =
2k+1 ­ 1 + 2k+1  =
2(2k+1) ­ 1 =
21(2k+1) ­ 1 =
2k+1+1 ­ 1  cqd
3. Prove que 1 + 2 + 3 + ... + n = n(n + 1)/2  (1)
para qualquer inteiro positivo n 
• Passo básico
P(1) (o valor da equação (1) quando n assume o 
valor  1)
1 = 1(1 + 1)/2 = 1 (verdadeira)
• Hipótese de indução: assuma que P(k) é verdadeira para 
um inteiro positivo arbitrário k, que é o valor da 
equação (1) quando n vale k, ou seja
1 + 2 + 3 + ... + k = k(k + 1)/2  (2)
• Usando a hipótese de indução, queremos mostrar que 
P(k+1), que é o valor da equação (1) quando n assume o 
valor de k+1, é igual (k + 1)[(k + 1) + 1]/2   
(3)
• A chave da demonstração por indução é encontrar um 
modo de relacionar o que se deseja mostrar P(k+1), 
equação(3), com o que hipótese de indução da P(k), da 
equação 2, que assumimos como verdadeira
• Reescrevendo P(k+1) usando a hipótese indutiva:
1 + 2 + 3 + ... + k + k + 1  =
k(k + 1)/2 + k + 1 =
(k2 + k)/2 + k + 1 =
[k2 + k + 2(k + 1)]/2 =
[k2 + k + (k + 1)+ (k + 1)]/2 =
[(k2 + 2k + 1)+ (k + 1)]/2 =
(k + 1)[(k + 1)+ 1]  cqd
4. Prove que 2n > n   (1)
para qualquer inteiro positivo n 
• Passo básico
P(1) (o valor da equação (1) quando n assume o 
valor  1)
21 > 1 (verdadeira)
• Hipótese de indução: assuma que P(k) é verdadeira para 
um inteiro positivo arbitrário k, que é o valor da 
equação (1) quando n vale k, ou seja
2k > k  (2)
• Usando a hipótese de indução, queremos mostrar que 
P(k+1), que é o valor da equação (1) quando n assume o 
valor de k+1, é igual 2k+1 > k+1  (3)
• A chave da demonstração por indução é encontrar um 
modo de relacionar o que se deseja mostrar P(k+1), 
equação(3), com o que hipótese de indução da P(k), da 
equação 2, que assumimos como verdadeira
• Reescrevendo P(k+1) usando a hipótese indutiva:
2k+1 = 2.2k 
2k > k
2.2k > 2.k = k + k ≥ K + 1, logo 
2k+1 > k+1cqd
5. Prove que o número 22n – 1    (1)
para qualquer inteiro positivo n é divisível por 3
• Passo básico
P(1) (o valor da equação (1) quando n assume o 
valor  1)
22.1 – 1 = 3 (verdadeira)
• Hipótese de indução: assuma que P(k) é verdadeira para 
um inteiro positivo arbitrário k, que é o valor da 
equação (1) quando n vale k, ou seja
22k – 1 = 3.m  22k = 3.m + 1 (2)
• Usando a hipótese de indução, queremos mostrar que 
P(k+1), que é o valor da equação (1) quando n assume o 
valor de k+1, é igual 22(k+1) = 3.n  (3)
• A chave da demonstração por indução é encontrar um 
modo de relacionar o que se deseja mostrar P(k+1), 
equação(3), com o que hipótese de indução da P(k), da 
equação 2, que assumimos como verdadeira
• Reescrevendo P(k+1) usando a hipótese indutiva:
22(k+1) – 1 = 22k+2 – 1 = 22k.22 – 1 = 4.22k – 1 =
4.(3m + 1) ­ 1 = 12m + 4 – 1 = 12m + 3 =
3(4m + 1) = 3n cqd 
INDUÇÃO COMPLETA  OU INDUÇÃO FORTE
 Princípio da Indução Matemática (INDUÇÃO FRACA):
• P(1) verdadeira
• (∀k)[P(k) verdadeira → P(k+1) verdadeira]
• ENTÃO P(n) verdadeira para todos os n inteiros positivos
 INDUÇÃO COMPLETA ou INDUÇÃO FORTE
1. P(1) verdadeira
2. (∀k)[P(r) verdadeira para todo r, 1   r   k,≤ ≤
  → P(k+1) verdadeira]
ENTÃO P(n) verdadeira para todos os n inteiros positivos
 Em   algumas   situações   não   conseguimos   realizar   uma 
demonstração   por   indução   usando   apenas   a   indução   fraca. 
Nesses   casos   o   uso     da   INDUÇÃO   FORTE   é   absolutamente 
necessário.
 Prove que para todo n  ≥  2, n é um número primo ou é um 
produto de números primos.
○ Porque não podemos usar a INDUÇÃO FRACA?
■ Propriedade: Todo inteiro n ≥ 2 é um número primo ou é 
um produto de números primos.
■ Usando a indução fraca:
• Base: 2 é primo VERDADE
• Hipótese indutiva: k é primo ou produto de primos
 se k é primo, tudo bem
 se k NÃO É PRIMO, então k=a.b onde a e b são primos 
ou produtos de primos
 a e b devem estar nos intervalos: 1<a<k e 1<b<k, 
respectivamente, caso contrário, isto é, se  1≤ a≤ k 
e 1≤b≤k, e k=a.b, então k é primo (uma contradição)
 Logo, a< k e  b< k
 De onde se conclui que precisamos de uma hipótese 
indutiva que possa valer para inteiros menores que 
k; na verdade, para inteiros no intervalo (fechado) 
[2,k]
 Isso   nos   obriga   a   tentar   a   INDUÇÃO   FORTE,   como 
descrito a seguir.
○ Base:
■ 2 é primo ou produto de primos. VERDADE
○ Hipótese   indutiva:   Vamos   supor   que   para   qualquer   r   no 
intervalo  2 ≤ r ≤ k, P(r) é verdadeira, isto é, r é primo 
ou é produto de números primos.
○ Tomemos agora o número k+1.
■ Se k+1 é primo, o resultado se verifica.
■ Se k+1 não é primo, então ele é um número composto e 
pode ser escrito como k+1=a.b, onde 1<a< k+1 e  1<b< k+1, 
ou  2≤a≤ k e  2≤b≤ k. Observe quea hipótese indutiva se 
aplica a a e b. Logo, ou a e b são primos ou são produto 
de primos. Isso verifica P(k+1) C.Q.D. (Como Queríamos 
Demonstrar)
 Prove   que   qualquer   valor   postal   maior   ou   igual   a   oito 
unidades monetárias pode ser obtido usando­se apenas selos 
com valores de 3 e 5. Em outras palavras, um inteiro positivo 
n, para todo n ≥ 8, pode ser representado como a soma de 3s e 
5s
○ Porque não podemos usar a INDUÇÃO FRACA?
■ Propriedade: Todo inteiro n  ≥  8 pode ser representado 
como a soma de 3s e 5s
■ Usando a indução fraca:
• Base: 8 = 3 + 5 VERDADE
• Hipótese indutiva: k pode ser representado como a soma 
de 3s e 5s
 vamos verificar se k + 1 pode ser representado como 
a soma de 3s e 5s
 k + 1 = [(soma de 3s e 5s) + 1] ≠ (soma de 3s e 5s) 
 não   consigo   realizar   a   demostração   indutiva 
considerando   verdadeira   a   hipotese   apenas   para   o 
item imediatamente anterior (k)
 é necessário considerar a hipótese verdadeira para 
um inteiro menor que k
 isso   nos   obriga   a   tentar   a   INDUÇÃO   FORTE,   como 
descrito a seguir.
○ Base:   a   base,   por   motivos   óbvios   será   o   8.   P(8)   é   a 
sentença de que 8 resulta da soma de 3s e 5s. De Fato, 
8 = 3 + 5 e P(8) é verdadeira.
○ Hipótese indutiva: Vamos  supor agora que para qualquer r, 
8 ≤ r ≤ k, P(r) é verdadeira, isto é, P(r) é a sentença de 
que r resulta da soma de 3s e 5s.
○ Vejamos agora o ocorre com k+1.  Queremos mostrar que k+1 
pode ser representado como a soma de 3s e 5s. Então, para 
usar a hipótese indutiva, isto é, usar o fato de que a 
propriedade   é   verdadeira   para   r,   onde   8  ≤ r  ≤ k,   devo 
considerar um inteiro menor que k
○ A   fim   de   que   a   hipótese   indutiva   (8  ≤ r  ≤ k)   seja 
verdadeira, é necessário que (k+1)­3 ≥ 8. Assim k+1 precisa 
ser  ≥  11. Logo não podemos usar a hipótese indutiva para 
verificar P(9) e P(10). Mas podemos verificar P(9) e P(10) 
diretamente.
■ P(9) = 3 + 3 + 3
■ P(10) = 5 + 5
○ Uma vez que P(r) é verdadeira para 8, 9 e 10 (8 ≤ r ≤ k), 
podemos assumir que k+1 é no mínimo 11, isto é, k+1 ≥ 11.
■ (k+1) ­ 3 ≥ (11 – 3)
■ (k–2) ≥ 8
■ Pela H.I.  P(r) é verdadeira para 8 ≤ r ≤ k
■ Logo P(k­2) é verdadeira (pode ser escrita como a soma 
de  3s e 5s)
■ (k­2)+3 = soma de 3s e 5s
■ (k­2+3) = k + 1 = soma de 3s e 5s c.q.d