TEORIA DOS NÚMEROS - INDUÇÃO MATEMÁTICA

INDUÇÃO MATEMÁTICA

3.1 - ALGUMAS PROPRIEDADES DO CONJUNTO DOS  NÚMEROS INTEIROS          Além das propriedades já destacadas no capítulo anterior, podemos observar no conjunto dos números inteiros, as propriedades: P1 - Dado um subconjunto A de Z, o subconjunto A admite um elemento mínimo "a" se, e somente se, para todo x de A,  a < x.  Indicamos o elemento mínimo de A por min(A).  Simbolizando temos:                                        min(A) = a Û a Î A e x Î A, x > a.         Com relação ao elemento mínimo tem-se:  Se "a" é o mínimo de A, então "a" é único. Demonstração:- Suponhamos que exista outro elemento "b" que também seja mínimo de A. Por definição temos: a < b pois a é min(A). Se b é min(A), b < a. Como a relação de ordem é anti-simétrica somente se pode concluir que b = a. P2 - Todo conjunto não vazio de inteiros não negativos  tem um elemento mínimo. P3 - O conjunto dos inteiros não positivos não tem elemento mínimo. P4 - Se "a" e "b" são dois inteiros positivos, então existe um inteiro positivo n tal que na > b.  3.2 - DEDUÇÃO E INDUÇÃO         Consideremos as seguintes seqüências de raciocínio:          i) Todo homem é mortal.             Sócrates é mortal.             Então, Sócrates é homem.         ii) Seja o trinômio: n2 + n + 17. Se fizermos n = 0, 1, 2, 3, 4 e 5, obtemos: 17, 19, 23, 29, 37, 47. Todos esses resultados são números primos. Poder-se-ia dai concluir que para todo n Î N, n2 + n + 17 é um número primo.         As duas conclusões são evidentemente falsas pois (i)  "Sócrates pode ser um gatinho" que é mortal mas não é homem e, (ii) para n = 17, n2 + n + 17 = 17x19 que não é primo. A sentença é verdadeira para n < 16.         Entretanto, raciocínio como estes, desde que seguidas algumas regras, poderão ser válidas.         No exemplo (i) partimos de uma afirmação geral para se chegar a uma afirmação particular. Um raciocínio desse tipo é chamado de DEDUÇÃO. No exemplo (ii) de algumas situações particulares tentou-se chegar a uma afirmação que poderia ser válida para todas as situações. Este tipo de raciocínio é denominado INDUÇÃO. Esquematizando temos:

Daremos, nesse capítulo, ênfase ao processo de indução.3.3 - PRIMEIRA FORMA DO PRINCÍPIO DA INDUÇÃO MATEMÁTICA FINITA         Seja P(n) uma propriedade. Essa propriedade é válida para todo número natural se: (i) P(n) é válida para n = 1, isto é P(1) é verdadeira; (ii) Supondo P(n)  válida para um número natural arbitrário k, for possível provar que P(k + 1)  é verdadeira.        Assim, a demonstração pelo princípio da indução matemática consiste em observar os passos: (i) Verificar a validade da propriedade para n = 1. (ii) Considerar válida a propriedade para n = k (iii) Provar que a propriedade é válida para n = k + 1 (sucessor de k) a partir da validade para n = k. A consideração feita no item (ii) é conhecida como hipótese de recorrência.       Vejamos alguns exemplos de aplicação do princípio da indução matemática.  Ex. 1 - Demonstrar que a soma dos n primeiros números inteiros positivos é Sn = (n + 1).n/2. Primeiro passo: Verificar se a propriedade é válida para n = 1. Temos S1 = (1 + 1).1/2 = 1. É verdade pois o único inteiro é 1. Segundo passo: Consideremos que Sk = (k + 1).k/2. Isto é, a propriedade é válida para n = k, ou seja Sk = 1 + 2 + 3 + ... + k Terceiro passo: Provemos que Sk+1 = (k + 1 + 1)(k + 1)/2 = (k + 2)(k + 1)/2.Ora, Sk+1 = 1 + 2 + 3 + ... + k + (k + 1) = Sk + k + 1 = (k + 1)k/2 + (k + 1) =  (k + 1)[(k/2) + 1] = = (k + 1)[(k + 2)/2] = (k + 2)(k + 1)/2. Como pode ser visto, provou-se que a propriedade é valida para n = k + 1. Assim, a propriedade é válida para todo n inteiro. Ex. 2 - Demonstrar que 1 + 3 + 5 + .... (2n - 1) = n2, " n Î N. ( i ) A propriedade é valida para n = 1, pois 1 = 12. (ii ) Hipótese de recorrência: 1 + 3 + 5 + .... (2k - 1) = k2 (soma dos inteiros ímpares) (iii)  Provemos que   1 + 3 + 5 + ... (2k - 1) + (2k + 1) = (k + 1)2.Temos: 1 + 3 + 5 + ... (2k - 1) + (2k + 1) = k2 + (2k + 1) = k2 + 2k + 1 = (k + 1)2. 3.4 - UMA VARIAÇÃO DO PRINCÍPIO DA INDUÇÃO MATEMÁTICA          O princípio da indução matemática, em seu primeiro passo exige que P(1) seja verdadeira. Entretanto, esse primeiro passo pode ser comprovado para qualquer valor de n. Pode-se usar qualquer número natural.         Quando a propriedade é válida para n > a, verifica-se no primeiro passo a validade da propriedade para  n = a. Exemplo: Provar que 2n < n!, " n > 4. - P(4) é verdadeira pois 24 = 16 e 4! = 4.3.2.1 = 24. - Hipótese de recorrência: 2k < k! (1) - Provemos que; 2(k + 1) < (k + 1)!. Demonstrando: Como k > 4,  0 < 2 < k + 1. (2). Multiplicando membro a membro as desigualdades (1) e (2) resulta: 2.2k < k!. (k + 1) Þ Þ 2k + 1 < (k + 1)!. Como a propriedade é válida para n = k + 1, ela é valida para todo n > 4. Também terá validade o raciocínio pelo princípio da indução matemática: (1) (i) Se P(n) é uma proposição válida n = 1,      (ii) Para todo inteiro positivo k, se  P(1), P(2), P(3)..., P(k) são todas verdadeiras então P(k + 1) também é verdadeira. (2)  (i) P(r) é verdadeira para todo inteiro k > r, se P(m) é verdadeira para todo inteiro m, tal que r < m < k é verdadeira implicar em que P(k) é verdadeira, então a proposição P(n) é verdadeira para todo inteiro n > r. EXERCÍCIOS:- Página 45/46 - Teoria Elementar dos números - Edgar de Alencar Filho - Ed. Nobel - 1985. (Você pode baixar os exercícios resolvido no site Meu Mundo). 1 – Demonstrar por indução matemática (a)  12 + 22 + 32 + ..... + n2 = (n/6)(n = 1)(2n + 1)  " n Î N.  (b)  13 + 23 + 33 + ..... + n3 = (n2/4).(n + 1)2,  " n Î N.  (c)  12 + 32 + 52 + ..... + (2n – 1)2 = (n/3).(4n2 – 1), " n Î N.  (d)  13 + 33 + 53 + ..... + (2n – 1)3 = n2(2n2 – 1), " n Î N.  (e)  1.2 + 2.3 + 3.4 + ... + n(n + 1) = (n/3)(n + 1)(n + 2), " n Î N.  (f)    1 + ¼ + 1/9 + ..... + 1/n2 < 2 – 1/n, " n Î N  (g)  a + aq + aq2 + ... + aqn = a(qn+1 – 1)/(q – 1), " n Î N.  (h)  2n < 2n + 1, " n Î N.                         (i)     2n > n2, " n > 5. (j)  2n > n3, " n > 10.  (k)  4n > n4, " n Î N. (l) 2 | (3n – 1), " n Î N.(m) 6 | (n3 – n), " n Î N. 2) Demonstre que n3/3 + n5/5 + 7n/15 é um inteiro positivo para todo n Î N.