Matemática Discreta - Princípio de indução finita

Prévia do material em texto

CAPÍTULO 2 – Princípio de indução finita Paulette 
 
 21 
 
 
PRINCÍPIO DE INDUÇÃO FINITA (PIF) 
 
 Sejam a e P(n) uma proposição (falsa ou verdadeira) associada a cada número natural n, 
n a. 
 Supondo que: 
 1
o
) P(n) seja verdadeira para n = a 
 2
o
) Para todo número natural k a, P(k) P(k+1). 
Nestas condições, P(n) será verdadeira para todo natural n a. 
 
 A aplicação do PIF para provar que P(n) é verdadeira para todo n, n a, é facilitada com o 
uso do seguinte procedimento: 
 a) Verificar que P(n) é verdadeira para n = a , 
 b) Supor que P(n) é verdadeira para n = k , k a. e 
 c) Provar que P(n) é verdadeira para n = k+1. 
 
Exemplo 1: 
Prove que P(n): 1+2+3+4+.......+(n-1)+ n = 
2
).1( nn
, n 1 
Prova: 
a) Verificar que P(n) é verdadeira para n = 1 
 1 membro = 1 (observe o termo geral) 
 2 membro = 
2
1).11(
 = 1 
 Portanto, P(n) é verdadeira para n = 1. 
 
 b) Supor (hipótese) que P(n) é verdadeira para n = k , k 1. 
 P(k): 1+2+3+4+.......+(k-1)+ k = 
2
).1( kk
 
 c) Provar (tese) que P(n) é verdadeira para n = k+1. 
 
 P(k+1): 1+2+3+4+.......+(k-1)+ k + (k+1) = 
2
)1).(2( kk
, k 1. 
 
 Partindo do primeiro membro da sentença P(k+1) acima e nele substituindo a P(k) (hipótese), 
temos: 
1+2+3+4+...+(k-1)+ k + (k+1) = [1+2+3+4+...+(k-1)+ k] + (k+1) = [
2
).1( kk
] + (k+1) = [
2
).1( kk
] 
+
2
)1(2 k
 = 
2
)1).(2( kk
. 
 A expressão final coincide com o segundo membro de P(k+1). 
 
 Portanto, pelo Princípio de Indução Finita, P(n) é verdadeira para todo n 1. 
CAPÍTULO 2 – Princípio de indução finita Paulette 
 
 22 
Exemplo 2: 
 Prove que P(n): 2 + 4 + 6 + 8 + ... + 2n = n.(n+1) , n 1. 
Prova: 
a) Verificar que P(n) é verdadeira para n = 1 
 1 membro = 2.(1) = 2 (observe o termo geral) 
 2 membro = (1).((1) + 1) = 1. (1 + 1) = 2 
 Portanto, P(n) é verdadeira para n = 1. 
 
 b) Supor (hipótese) que P(n) é verdadeira para n = k , k 1. 
 P(k): 2 + 4 + 6 + 8 + .......+ 2k = k (k + 1) 
 
 c) Provar (tese) que P(n) é verdadeira para n = k+1, k 1. 
 
 P(k+1): 2 + 4 + 6 + 8 + .......+ 2k + 2(k+1) = (k + 1) ( (k+1) + 1) ou 
 P(k+1): 2 + 4 + 6 + 8 + .......+ 2k + 2(k+1) = (k + 1)( k + 2) 
 
 Partindo do primeiro membro da sentença P(k+1) acima e nele substituindo a P(k) (hipótese), 
temos: 
 
 2 + 4+ 6 + 8 + ...+ 2k + 2(k+1) = [2 + 4+ 6 + 8 + ...+ 2k] + 2(k+1) = 
 = [ k (k + 1)] + 2(k+1) = (k+1) ( k + 2). 
 
 A expressão final coincide com o segundo membro de P(k+1). 
 
 Portanto, pelo Princípio de Indução Finita, P(n) é verdadeira para todo n 1. 
 
Exercícios de aplicação 7: 
 
Demonstrar as seguintes proposições, usando o PIF. 
 
1) P(n): 1+x+ 2x + 3x + .......+ nx = 
x
x n
1
1 1
 , n 1 e x 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 2 – Princípio de indução finita Paulette 
 
 23 
2) P(n): 1+3+5+........+(2n-1) = 
2n , n 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
3) P(n): 21 + 22 + 23 + ........+ 2n = 
6
)12).(1.( nnn
, n 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 4) P(n): 
31 + 32 +
33 + .......+ 3n = 
4
)1.( 22 nn
 , n 1. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 2 – Princípio de indução finita Paulette 
 
 24 
 5) P(n): 10
n
 > n , n 1. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 6) P(n): 2
n
 > n , n 1. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 7) P(n): 
22 1n é divisível por 3, n > 0. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 2 – Princípio de indução finita Paulette 
 
 25 
8) P(n): 
2 3n n , 4n . 
 
 
 
 
 
 
 
 
 
 
 
 
9) P(n): n ! > 
12n , n 4. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
10) Use o P.I.F. e mostre a lei de De Morgan generalizada. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 2 – Princípio de indução finita Paulette 
 
 26 
11) P(n): 10 1n é divisível por 9, n 0. 
 
 
 
 
 
 
 
 
 
 
 
 
 
12) P(n): 7 1n é divisível por 6, n 0 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
13) Mostre pelo PIF que o produto de dois números inteiros consecutivos é sempre par, ou n(n+1) é 
par.