Indução

Arquivo cedido por Alex Pereira Bezerra

Lista de Discussão OBM

Principio da Indução Finita (PIF)
1) Axioma da Boa Ordem em N: Cada subconjunto não vazio de N possui um menor( ou primeiro) elemento O axioma da boa ordem em N afirma que se A é um subconjunto do conjunto N e A então existe um elemento n0 em A satisfazendo n0 a para cada inteiro a do conjunto A Teorema : 1. Não existe um inteiro n tal que 0 < n < 1; 2. Para cada inteiro m, não existe n tal que m < n < m + 1; 3. Se m e n são inteiros com m < n então m + 1 n. Reciprocamente, se m + 1 < n. Demonstração: 1. Suponhamos que existe um inteiro n tal que 0 < n < 1. Tal n é um número natural, e, portanto o conjunto A de números naturais caracterizado por A {x N / 0 x 1} é um conjunto não vazio ( visto que n A ).Pelo axioma da boa ordem,A tem um menor elemento n0 .Porém 0. n0 1 0.n 0 n0 .n0 1.n0 ,ou seja ,

n então m

0

2 n0

n0 .Temos aí uma contradição ,pois 0

2 n0

1

2 n0

A , porém n 0 é o

2 menor elemento de A e n0 n0 . 2. Sejam m e n dois inteiros e suponhamos m < n < m +1.Então m n5. solução: a) (1) Para n = 1, 21 = 2 < 21 + 1 = 22 = 4, verdadeiro. (2) Hipótese: 2n < 2n + 1. (1) Provar 2n + 1 < 2n + 2. Demonstração:

www.rumoaoita.com

Arquivo cedido por Alex Pereira Bezerra

Lista de Discussão OBM

Por hipótese 2n < 2n + 1

2.2n < 2.2n + 1

2n + 1 < 2 n + 2 .

(1) É verdade para n = 5, pois 25 = 32 e 52 = 25. (2) Hipótese: 2n > n2. (3) Provar 2n + 1 > (n + 1)2 Demonstração: - Provemos inicialmente que 2n > 2n + 1, para n > 5. Esta proposição é verdadeira para n = 5, pois 25 > 10 + 1 = 11. Supondo verdadeira para n, 2n > 2n + 1, devemos ter 2n + 1 > 2(n + 1) + 1 = 2n + 3. Ora, 2n > 2n + 1 e 2n > 2 para n > 1. Somando membro a membro, 2n + 2n > 2n + 1 + 2 +3 2n+1 > 2n + 3 ( i )

2.2n > 2n

Pela hipótese 2n > n2 e conforme demonstrado, 2n > 2n + 1. Somando membro a membro essas igualdades, concluímos: 2n + 2n > n2 + 2n + 1 2n + 1 > (n + 1)2. (expressão a ser