Aula_004_Indução matemática

Prévia do material em texto

Módulo: Indução matemática
Indução forte
Princípio da indução matemática
4.1
Objetivo:
Aprender uma técnica para provar resultados
matemáticos.
4.2Indução matemática
Por exemplo: 
Provar que 1 + 2 + 3 + ... + n = n(n + 1) _______
 2
 n ∈ 
8
N
É uma técnica poderosa e muito útil usada para 
provar resultados que envolvem os números naturais.
Importância:
Princípio da indução matemática (PIM)
Introdução
Conteúdo:
Aula 4: Princípio da indução matemática
Princípio da indução matemática generalizado
4.3
Idéia intuitiva:
Exemplo 1: 
Consideremos uma sequência de dominós alinhados
tal que:
Se um cair ele vai derrubar o seguinte
PIM
Voltar
Introdução: 
4.4Indução matemática
Observação:
Se o primeiro dominó cair então todos os outros cairão.
Exemplo 2: 
Consideremos lâmpadas elétricas alinhadas e conectadas
tal que:
ao acender uma delas acende-se a seguinte
PIM
Voltar
4.5Indução matemática: Introdução
Se a primeira lâmpada for acesa então todas as 
outras estarão acesas.
Observação:
Formalização:
Princípio da indução matemática: 
4.6Indução matemática
Se : (i) P(1) verdadeira e
(ii) P(k) verdadeira => P(k+1) verdadeira, k ∈ 
8
N
Seja P(n) uma afirmação, para cada n ∈ . 
N
Então P(n) verdadeira para todo n ∈ . 
N
Para aplicarmos o PIM precisamos executar os três 
passos a seguir:
(1) Base da indução: 
 Mostrar que P(n) verdadeira para n = 1
(2) Hipótese de indução:
 Assumir que P(k) verdadeira para k ≥ 1
(3) Passo indutivo:
 Mostrar que P(k + 1) verdadeira, assumindo (2).
4.7Indução matemática: Princípio da indução matemática
Exemplo 3:
verdadeira
4.8Indução matemática: Princípio da indução matemática
Mostre que 1 + 2 + 3 + ... + n = n(n + 1)_______
 2
n ∈ .
8
N
Prova:
Seja P(n) : 1 + 2 + 3 + ... + n = n(n + 1) ________
 2
(1) Base da indução: 
P(1) : 1 = 1(1 + 1) = 1 _______
 2
(2) Hipótese de indução (HI): Assuma que P(k) é 
verdadeira, k ≥ 1:
 1 + 2 + ... + k = k(k+1)______
 2
4.9Indução matemática: Princípio da indução matemática
1 + 2 + ... + k + (k + 1) = (k + 1) (k + 2)_____________
 2
(3) Passo indutivo: 
P(k) verdadeira => P(k + 1) verdadeira 
Desenvolvendo:
_______
 2
k(k + 1) + (k + 1) = k2 + k + 2k + 2 =______________ 
 2
1 + 2 + ... + k + (k + 1) = 
=
(HI)
Logo P(k+1) verdadeira
= k2 + k + 2k + 2 =______________ 
 2
 (k+1)(k+2) __________ 
 2
 k2 + 3k + 2 =__________ 
 2
______
 2
k(k+1) + (k+1)
4.10Indução matemática: Princípio da indução matemática
Então pelo PIM 
verdadeira________ 
 2
P(n) : 1 + 2 + ... + n = n(n + 1)
N
n ∈ 
8
Exemplo 4:
Prova: 
Seja P(n) : 1 + 3 + 5 + ... + (2n − 1) = n2 
verdadeira
Mostre que 1 + 3 + 5 + ... + (2n − 1) = n2
N
n ∈ .
8
4.11Indução matemática: Princípio da indução matemática
(1) Base da indução: 
P(1) : 1 = 12 
(2) Hipótese de indução (HI): 
 P(k) : 1 + 3 + 5 + ... + (2k − 1) = k2 verdadeira
(3) Passo indutivo: 
 P(k) verdadeira => P(k + 1) verdadeira 
4.12Indução matemática: Princípio da indução matemática
1 + 3 + ... + [ 2(k + 1) − 1] = (k + 1)
2
Logo P(k + 1) verdadeira
 Então pelo PIM
 P(n) : 1 + 3 + ... + (2n - 1) = n2 verdadeira 
8
n ∈ 
N
1 + 3 + ... + (2k - 1) + [ 2(k + 1) - 1 ] = 
Desenvolvendo:
k2 + 2k+1 = (k + 1)2
=
(HI)
=
Exemplo 5:
 
 Seja P(n) : 8 divide 32n − 1 
Prova:
4.13Indução matemática: Princípio da indução matemática
Mostre que 8 divide 32n − 1
N
8
n ∈ .
32n - 1 = 8 . p para algum p ∈ 
N
ou
(1) Base da indução: 
verdadeiraP(1) : 32 . 1 − 1 = 9 − 1 = 8 . 1 (p = 1)
4.14Indução matemática: Princípio da indução matemática
(2) Hipótese de indução: 
P(k) verdadeira, 
32k - 1 = 8 . p para algum p ∈ 
N
(3) Passo indutivo: 
 P(k) verdadeira => P(k + 1) verdadeira
Desenvolvendo:
32(k + 1)- 1 = 32k. 32 - 1 = 32k (8 + 1) - 1 = 
N
32(k + 1)- 1 = 8 . p para algum p ∈ 
4.15Indução matemática: Princípio da indução matemática
= 32k. 8 + 32k- 1 = 
8 . p
(HI)
=
32k. 8
=
+ 32k. 8 32k- 1
Logo P(k+1) verdadeira
32(k + 1)- 1 = 32k. 8 + 8 . p = 8 . (32k+ p) ( p = 32k+ p )
∈ 
N
Então pelo PIM 
P(n) : 8 divide 32n - 1 verdadeira n ∈ 
8
N
4.16Indução matemática: Princípio da indução matemática
Se:
(ii,)
(i,) P(n0)
8
N N
 k ≥ n0 ,k ∈ 8 N
Princípio da indução matemática generalizado
Seja P(n) uma afirmação, para cada inteiro positivo n.
 verdadeira e
P(k) verdadeira => P(k+1) verdadeira, 
PIM
Princípio da indução matemática 
generalizado: 
Voltar
4.17Indução matemática
8
Então P(n) verdadeira n ∈ , n ≥ n0 .N
Para aplicarmos o PIM generalizado precisamos 
executar os três passos a seguir:
(1) Base da indução: 
 Mostrar que P(n) verdadeira para n = n0 
(3) Passo indutivo:
 Mostrar que P(k + 1) verdadeira, assumindo a 
 hipótese de indução (2)
(2) Hipótese de indução:
 Assumir que P(k) verdadeira para k ≥ n0 
4.18Indução matemática: PIM generalizado
Exemplo 6:
 
verdadeira
(2) Hipótese de indução: 
 P(k) : k2 > 3k , k ≥ 4 verdadeira 
4.19Indução matemática: PIM generalizado
8
Mostre que n2 > 3n n ≥ 4 , n ∈ .
N
(1) Base da indução: 
P(4) : 16 > 3 . 4 = 12 
Prova: 
Seja P(n) : n2 > 3n , n ≥ 4 
(3) Passo indutivo: 
 P(k) verdadeira => P(k + 1) verdadeira
k2 + 2k + 1 =
4.20Indução matemática: PIM generalizado
Logo P(k + 1) verdadeira
Então pelo PIM generalizado 
 P(n) : n2 > 3n verdadeira n ≥ 4 
8
(k ≥ 4) 
 ≥ 3k + 8 + 1 = 3k + 9
(k + 1)2 > 3k + 9 = 3(k + 3) > 3(k + 1)
Desenvolvendo:
P(k) : k2 > 3k verdadeira para k ≥ 4 
k2 + (2k + 1) > 3k + (2k + 1) 
(k + 1)
2
 > 3(k + 1)
P(n) : n2 > 3n não é verdadeira para n = 1, 2, 3
P(1) : 12 > 3 . 1
P(2) : 22 > 3 . 2
P(3) : 32 > 3 . 3
não são verdadeiras
Verifique que: 
4.21Indução matemática: PIM generalizado
Princípio PIM generalizado
Estrutura
Resumo: 
- Base de indução: P(n) verdadeira n = n0
- Passo indutivo: P(k) verdadeira => P(k + 1) verdadeira
n0 = 1 : PIM
Em particular
4.22Indução matemática
- Hipótese de indução: P(k) verdadeira k ≥ n08
Prove usando indução matemática
Exercícios: 
(v) 2 divide n2 + n
(i) 1 + 2 + 4 + ... + 2(n - 1) = 2n - 1
8 N
n ∈
4.23Indução matemática
(ii) 12 + 22 + 32 + ... + n2 = n(n + 1)(2n + 1)___________________
6
(iii) 2 + 5 + 8 + ... + (3n - 1) = n(1 + 3n)___________
2
(iv) (1 + 1) ( 1 + 1 ) ( 1 + 1 ) ... ( 1 + 1 ) = n + 1__
 2
__
 3
__
n