Aula_005_Indução forte

Prévia do material em texto

Indução forte
Série de Fibonacci
Conteúdo:
Indução forte generalizada
Aula 5: Indução forte
5.1Indução matemática
É uma sequência de números naturais {F1, F2, F3, ...} ,
denotada por {Fn} definida da seguinte forma:
Sequência de Fibonacci: 
F1 = 1
F2 = 1
Fn = Fn - 1 + Fn - 2 para n ≥ 3
5.2Indução matemática
F1
...
1 1 ...
Ou seja, os termos Fn n ≥ 3 são calculados 
recursivamente:
F2
Voltar
2 3
F4 F5 F6
8
F7 F8
13 215
F3
{ 1, 1, 2, 3, 5, 8, 13, 21, ... }
5.3Indução matemática: Sequência de Fibonacci
Observe a seguinte propriedade:
Somando os termos da sequência de Fibonacci 
elevada ao quadrado:
F21 = 1
2 = 1 Voltar
F21 + F
2
2 = 1
2 + 12 = 1 + 1 = 2 = 1 . 2 = F2 . F3
F21 + F
2
2 + F
2
3 = 1
2 + 12 + 22 = 6 = 2 . 3 = F3 . F4
F21 + F
2
2 + F
2
3 + F
2
4 = 1
2 + 12 + 22 + 32= 15 = 3 . 5 = F4 . F5
F21 + F
2
2 + F
2
3 + F
2
4 + F
2
5 = 1
2+12+22+32+52= 40 = 5 . 8 = F5 . F6
5.4Indução matemática: Sequência de Fibonacci
Conjectura: F21 + F
2
2 + F
2
3 + ... + F
2
n = Fn . Fn + 1 
Exemplo 1:
(1) Base da indução: 
P(1) : F21 = 1 = F1 . F2 = 1 . 1 = 1 verdadeira
(2) Hipótese de indução (HI): 
 P(k) : F21 + F
2
2 + ... + F
2
k = Fk . Fk - 1 verdadeira
Prova: 
Seja P(n) : F21 + F
2
2 + ... + F
2
n = Fn . Fn + 1
5.5Indução matemática: Sequência de Fibonacci
Mostre que F21 + F
2
2 + ... + F
2
n = Fn . Fn + 1 n ∈ N8
(3) Passo indutivo: 
P(k) verdadeira => P(k + 1) verdadeira 
5.6Indução matemática: Sequência de Fibonacci
F21 + F
2
2 + ... + F
2
k + F
2
k + 1 = Fk + 1 • Fk + 2
Fk . Fk + 1 + F
2
k + 1 
=
(HI)
= Fk + 1 (Fk + Fk + 1) = Fk +1 . Fk + 2 =
Fk + 2 
 Desenvolvendo:
F21 + F
2
2 + ... + F
2
k + F
2
k + 1 =
Logo P(k + 1) verdadeira
 Então pelo PIM 
 P(n) : F21 + F
2
2 + ... + F
2
n = Fn . Fn + 1 verdadeira n ∈ 8 N
Indução forte (IF): 
 IF
Observação: O PIM e a IF são equivalentes. 
Voltar
Se:
(i) P(1) verdadeira e
(ii) P(1), P(2), ... ,P(k) verdadeira => P(k+1) verdadeira 
Então P(n) verdadeira n ∈ 
N8
5.7Indução matemática
8
N
Seja P(n) uma afirmação, para cada n ∈ . 
N
Para aplicarmos a indução forte 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 forte:
 Assumir que P(1), P(2), ... , P(k) são verdadeiras
(3) Passo indutivo:
 Mostrar que P(k + 1) verdadeira, assumindo (2)
5.8Indução matemática: Indução forte
Exemplo 2:
5.9Indução matemática: Indução forte
4(
(
Considerando a sequência de Fibonacci {Fn} ,
mostre que Fn < 7__
 n n ∈
N
8
Prova: 
 Seja P(n) : Fn < 7__
 n 
4( )
(1) Base da indução: 
 P1 : F1 = 1 < 7__
 1 verdadeira
4( )
5.10Indução matemática: Indução forte
4( )
 P1, P2, ... , Pk verdadeiras => P(k + 1) verdadeira
(3) Passo indutivo: 
Fk + 1 < 7__
 k + 1
4( )
(2) Hipótese da indução forte (HIF): 
 Assuma que P1, P2, ... , Pk são verdadeiras
 
 
 
Fi < 7__
 i i , 1 ≤ i ≤ k
8
Desenvolvendo:
Fk + 1= Fk + Fk - 1 
5.11Indução matemática: Indução forte
4( )Fk < 7__
 k
Fk - 1 < 7__
 k-1
4( )
{= {=
HF HF
Observe que 
 
 11__
 < 3 < 
4
 
 7__
 2 
4( )
 
 49__
 = 
16
Fk + 1 < < • = 
 
 7__
 k - 1 
4( )
 
 7__
 k - 1 
4( )
 
 7__
 2 
4( )
 
 7__
 k + 1 
4( )
 
 11__
 
4
Logo P(k + 1) verdadeira
 Então pelo IF Fn < n ∈ 8 N
 
 7__
 n 
4( )
 
 7__
 k 
 
 11__
 
 
 7__
 
 +1 
 
 7__
 k - 1 
 
 7__
 k - 1 
 
 7__
 k - 1 ( 4 )4( )4( ) 4( ) 4( ) 4( )< + = = 
Se:
(i) P(n0) verdadeira 
(ii) P(n0), P(n0+1), ...,P(k) verdadeira => P(k+1) verdadeira 
 (k = n0 + k
,
) 
 
8
Então P(n) é verdadeira n ≥ n0 n ∈ N
Indução forte generalizada: 
VoltarIFG
5.12Indução matemática
Seja P(n) uma afirmação, para cada n ∈ . 
N
N8
8
N
8
N N
(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)
Para aplicarmos a IF generalizada precisamos 
executar os três passos a seguir:
5.13Indução matemática: Indução forte generalizada
(2) Hipótese de indução:
 Assumir que P(n0), P(n0 + 1), ... , P(k) são 
8
verdadeiras ( k ≥ n0 ) 
Exemplo 3:
Mostre que todo inteiro maior do que 1 é primo ou 
produto de primos.
(Obs: primo é um inteiro maior do que 1, que só é divisível por 1 e por
ele mesmo. Exemplos: 2, 3, 5, 7 são primos )
(1) Base da indução: 
P(2) : 2 é primo verdadeira
5.14Indução matemática: Indução forte generalizada
Prova: 
Seja P(n) : n é primo ou produto de primos.
 
(2) Hipótese de indução forte: 
 
P(i) é verdadeira para 2 ≤ i ≤ k
Assuma que:
 i é primo ou produto de primos, 2 ≤ i ≤ k 
k + 1 é primo ou produto de primos
=
(3) Passo indutivo: 
 P(i) verdadeira 2 ≤ i ≤ k => P(k + 1) verdadeira 
5.15Indução matemática: Indução forte generalizada
 
Desenvolvendo:
Temos duas possibilidades mutuamente exclusivas
(i) k + 1 é primo
(ii) k + 1 não é primo
Se (i) acontece então P(k + 1) é verdadeira
Caso contrário (ii) acontece, então k + 1 não é primo
5.16Indução matemática: Indução forte generalizada
k + 1 não é primo
Então k + 1 pode ser escrito como:
k + 1 = a . b onde 1 < a < k + 1
1 < b < k + 1
5.17Indução matemática: Indução forte generalizada
Usando agora a hipótese de indução forte temos que:
P(a) e P(b) são verdadeiras 1 < a ≤ k
1 < b ≤ k
ou seja, a é primo ou produto de primos e
b é primo ou produto de primos 
5.18Indução matemática: Indução forte generalizada
Então pelo princípio da indução forte generalizada 
 P(n) : n é primo ou produto de primos n ∈ n > 1
8 N
Logo k + 1 = a . b é produto de primos
Logo P(k + 1) é verdadeira
Resumo: 
Conceitos:
- Base de indução: P(n) verdadeira n = n0
- Hipótese de indução: 
 P(n0), (n0+1), ..., P(k) verdadeira => P(k + 1) verdadeira 
 Sequência de Fibonacci
 Indução forte generalizada
 Em particular
 n0 = 1 : Indução forte
5.19Indução matemática
 Estrutura 
Exercícios: 
(1) Seja {an} a sequência definida por: 
a1 = 1 , a2 = 5
an+1 = an + 2an -1 n ≥ 3
Mostre que usando a indução forte an = 2
n + (-1)n 
(2) Seja {Fn} a sequência de Fibonacci. 
Mostre usando a indução forte que
5.20Indução matemática
8 n ≥ 2
8
N
n ∈Fn = 1 1 + √5 n 1 1 − √5 n −__
√5
______ 
 2 
______ 
 2 
__
√5( )( )