Teoria Elementar dos Numeros

Prévia do material em texto

<p>TEORIA ELEMENTAR DOS NÚMEROS Edgard de Alencar Filho Ex-professor de GEOMETRIA ANALÍTICA e CÁLCULO da Escola Militar do Realengo e de MATEMÁTICA da Escola Preparatória de São Paulo</p><p>CIP-Brasil. Câmara Brasileira do Livro, SP Alencar Filho, Edgard de, 1913- A353t Teoria elementar dos números/Edgard de Alencar Filho. Sao Paulo : Nobel, 1981. Bibliografia. ISBN 35-213-0040-9 1. Números - Teoria I. Título. 17. CDD-512.31 13. -512.7 81-0333 para 1. Teoria dos números 512.31 (17.) 512.7 (13.)</p><p>ÍNDICE 1 - INTEIROS: NOÇÕES FUNDAMENTAIS 1.1 Numeros inteiros 13 1.2 Propriedades dos inteiros 14 1.3 Valor absoluto de um inteiro 16 1.4 Fatorial 13 1.5 Numero binomial 20 1.6 Numeros binomiais complementares 21 1.7 Numeros binomiais consecutivos 21 Exercicios 25 2 - MATEMÁTICA 2.1 Elemento minimo de um conjunto de inteiros 31 2.2 da boa 32 2.3 de indução finita 34 2.4 matematica 35 2.5 Exemplos de demonstração por indução matemati ca 37 2.6 Outras formas de indução matematica 40 Exercicios 45 CAPÍTULO 3 - SOMATÓRIOS E PRODUTÓRIOS 3.1 Somatorios 47 3.2 Propriedades dos somatorios 49 3.3 Somatorios duplos 50 3.4 52 3.5 Propriedades dos produtorios 53 3.6 Teorema do binomio 55 3.7 Triângulo de PASCAL 5.7 3.8 Propriedades do de PASCAL 59 3.9 Numeros triangulares 61 65</p><p>4 - DIVISIBILIDADE 4.1 Relação de divisibilidade em Z 68 4.2 Conjunto dos divisores de um inteiro 71 4.3 Divisores comuns de dois inteiros 72 4.4 Algoritmo da divisão 74 4.5 Paridade de um inteiro 78 80 CAPÍTULO 5 - MÁXIMO DIVISOR COMUM 5.1 Maximo divisor comum de dois inteiros 34 5.2 Existência e unicidade do mdc 35 5.3 Inteiros primos entre si 89 5.4 Caracterização do mdc de dois inteiros 93 5.5 Mdc de inteiros 94 96 6 - ALGORITMO DE MINIMO MULTIPLO COMUM 6.1 Algoritmo de EUCLIDES 101 6.2 comuns de dois inteiros 108 6.3 Minimo comum de dois inteiros 110 6.4 Relação entre o mdc e o mmc 111 6.5 Mmc de varios inteiros 112 113 CAPÍTULO 7 - NÚMEROS PRIMOS 7.1 Numeros primos compostos 116 7.2 Teorema fundamental da Aritmetica 119 7.3 que dao primos 125 7.4 Crivo de ERATÓSTENES 126 7.5 Primos gêmeos 127 7.6 Sequências de inteiros consecutivos compostos 128 7.7 Conjectura de GOLDBACH 129 7.8 Metodo de fatoração de FERMAT 131 132 CAPÍTULO 8 - EQUAÇÕES DIOFANTINAS LINEARES 8.1 Generalidades 137 8.2 de de solução 138 8.3 da equaçao ax + by = 139 Exercícios 146</p><p>9 - CONGRUÊNCIAS 9.1 Inteiros congruentes 148 9.2 de inteiros congruentes 150 9.3 Propriedades das 152 9.4 Sistemas completos de restos 159 Exercícios 162 10 - CONGRUÊNCIAS LINEARES Generalidades 165 10.2 de de soluçao 167 10.3 Soluçoes da ax b (mod. m) 168 10.4 de diofantinas lineares por 175 10.5 Inverso de um inteiro 178 179 11 - SISTEMAS DE CONGRUÊNCIAS LINEARES 11.1 Generalidades 181 11.2 Teorema do resto chinez 133 Exercícios 191 12 - TEOREMAS DE FERMAT E WILSON 12.1 Teorema de FERMAT 193 12.2 Teorema de WILSON 199 203 13 - DIVISORES DE UM INTEIRO 13.1 Divisores de um inteiro 205 13.2 Numero de divisores 203 13.3 Soma de divisores 212 13.4 215 Notaçao 13.5 Produto de divisores 216 Exercícios 218 CAPÍTULO 14 - FUNÇÕES 14.1 Conceito de função aritmetica 221 14.2 Funçoes aritmeticas multiplicativas 222 14.3 Funçao de MOBIUS 227 14.4 Funçoes multiplicativas completas 231 14.5 Funçao maior inteiro 231</p><p>14.6 Formula de de MOBIUS 233 235 CAPÍTULO 15 - FUNÇÃO E TEOREMA DE EULER 15.1 Funçao de EULER 237 15.2 de (n) 240 15.3 Propriedades da função de EULER 244 15.4 Teorema de EULER 249 15.5 entre as e u 253 255 16 - PERFEITOS 16.1 Numeros perfeitos 258 16.2 Numeros multiperfeitos 265 16.3 Numeros amigos 266 16.4 deficientes e abundantes 267 16.5 Numeros de MERSENNE 263 16.6 Numeros de FERMAT 272 Exercícios 274 17 - DE FIBONACCI Sequências recorrentes 278 de FIBONACCI 279 17.3 Somas de numeros de FIBONACCI 280 17.4 Soma dos quadrados de numeros de FIBONACCI 234 Identidades entre numeros de FIBONACCI 17.6 Propriedades dos numeros de FIBONACCI 287 292 CAPÍTULO 18 - TERNOS 18.1 Conceito de terno pitagórico 296 18.2 Formulas que dao ternos pitagoricos 297 18.3 Ternos primitivos 299 18.4 Propriedades dos ternos pitagoricos 301 Exercícios 305 CAPÍTULO 19 - CLASSES RESIDUAIS 19.1 Conceito de classe residual 303 19.2 Propriedades das classes residuais 310 19.3 Conjunto das classes residuais 312 317</p><p>20 - REPRESENTAÇÃO DOS INTEIROS EM OUTRAS BASES. CRITÉRIOS DE DIVISIBILIDADE 20.1 Representação dos inteiros em outras bases. 318 20.2 de divisibilidade 20.3 323 de divisibilidade por 9 325 20.4 de divisibilidade por 11 327 Exercícios 21 - RAIZES PRIMITIVAS 21.1 Ordem de um inteiro modulo 21.2 Raiz primitiva de um inteiro 333 341 Exercícios 344 EXERCÍCIOS SUPLEMENTARES 346 RESPOSTAS DOS EXERCÍCIOS 367 BIBLIOGRAFIA 385</p><p>PREFÁCIO 0 conceito de numero desempenha papel fundamental na civi lização moderna, e as ciências mais avançadas sao preci- samente aquelas que mais empregam a linguagem dos nume- ros. Alias, a Matematica vem se tornando cada vez mais ne em todos os ramos do conhecimento humano, desde a Física à Biologia, bem como nas ciências sociais (Econo- mia, Finanças, etc.). Até mesmo na Psicologia tem sido utilizada com exito. 0 livro que ora publicamos pela conceituada "Editora NO- BEL" tem por única finalidade fornecer aos estudantes as primeiras noçoes da "Teoria dos Numeros". Desta forma pro curo contribuir, na medida das minhas forças, para a me- lhoria do ensino da em nosso venho fazendo muitos anos. Em cada um dos Capítulos do livro os conceitos defini dos com precisão e as proposições fundamentais pertinen- tes sao todas demonstradas e, logo em seguida, exemplifi- cadas, tendo em vista o leitor que pela primeira vez abor da esta fascinante parte da pura. disso, cada Capítulo termina por um conjunto de Exercícios, nume ricos e teoricos, cujas respostas sao dadas no final do livro, os quais permitem completar a aprendizagem. Edgard de Alencar Filho</p><p>CAPÍTULO 1 NÚMEROS INTEIROS FUNDAMENTAIS 1.1 INTEIROS inteiros ou apenas os inteiros sao: cujo conjunto representa-se pela letra z, isto e: } Neste conjunto 2 destacam-se os seguintes subconjuntos: (1) Conjunto Z* dos inteiros nutos (# 0) : } (2) Conjunto dos inteiros nao negativos ( : = } (3) Conjunto dos inteiros positivos = }</p><p>14 (4) Conjunto dos inteiros positivos (> 0): 2* = = (5) Conjunto dos inteiros negativos (<0) : } inteiros positivos tambem denominados inteiros na- turais e por isso o conjunto dos inteiros positivos e ha- bitualmente designado pela letra N(N = 2*). 1.2 PROPRIEDADES DOS INTEIROS 0 conjunto Z dos inteiros munido das operações de adição (+) e possui as propriedades fundamen- que a seguir enumeramos, onde a, b e são intei- ros quaisquer, isto elementos de Z: (1) e ab = ba (2) e = (3) 0 + a = a e = a (4) e a - a = a + (-a) = 0 (5) a(b + c) = ab + ac (6) 0.a = 0, e se ab = 0, então a = 0 ou b = 0. Tambem existe uma "relação de ordem" entre os inteiros, representada pelo sinal que)", que possui as se guintes propriedades:</p><p>15 (7) Se a # 0, então a<0 ou (8) Se e então (9) Se então a (10) Se a<b e então ac <bc (11) Se a<b e entao bc < ac Destas propriedades podem ser deduzidas muitas outras pro priedades dos inteiros. Exemplo 1.1 Demonstrar: -(a + b) = (-a) + (-b). . Com efeito, temos + b) = (Propriedade 4) = (-1)a + (-1)b = (Propriedade 5) + (-b) (Propriedade 4) Exemplo 1.2 Demonstrar que, 0, então Com efeito: (1) Se então ou (Propriedade 7) (2) Se x<0, então 0.x<x.x (Propriedade 11) (Propriedade 6) (3) Se entao 0.x<x.x (Propriedade 10) (Propriedade 6) NOTA - Com o mesmo significado. de escreve-se b>a.</p><p>16 Indica-se, de modo abreviado, que a<b ou a = b por a<b. Por exemplo, temos porque 2<3, e 2<2, porque Com o mesmo de escreve-se b>a. Em lugar de e se escreve significados tem: a<b<c, a>b>c, etc. 1.3 VALOR ABSOLUTO DE UM INTEIRO 1.1 Chama-se valor absoluto de um inteiro inteiro que se indica por e tal que a se = -a se a<0 Assim, p.ex.: = 3 e = 5 Consoante a definição de para todo inteiro a, temos: = 0 valor absoluto de um inteiro a tambem pode ser de- finido pelas igualdades: = ,</p><p>17 onde denota a raiz quadrada não negativa de e max(-a,a) indica o maior dos dois inteiros Assim, p.ex.: = = 16=4 = max(-6,6) = 6 Teorema 1.1 Se aeb sao dois inteiros, = Demonstração: Com efeito: = (ab)2 2,2 = a Teorema 1.2 sao dois inteiros, então: Demonstração: Com efeito, pela definição de temos: - Somando ordenadamente estas desigualdades, obtemos: + que implica: +</p><p>18 Corolario 1.1 sao dois inteiros, + Demonstração: Com efeito: = + (-b) a + = 1.4 FATORIAL Definição 1.2 Chama-se fatorial de um inteiro não negati von o inteiro que se indica por e tal que: 1 se n = 0 ou n! n(n-1) (n-2)...3.2.1 se Assim, p.ex.: 7.6.5.4.3.2.1 = 5040 Observe-se que Exemplo 1.3 Escrever, usando o simbolo de fatorial,o pro duto dos n primeiros inteiros positivos pares e produ- to dos n primeiros inteiros positivos impares. n primeiros inteiros positivos pares sao: 2n-2, 2n isto e: 2.1, 2. (n-1), 2.n</p><p>19 Portanto: 2.4.6 (2n-2).2n = (n-1).n) = Os n primeiros inteiros positivos impares sao: 2n-3, 2n-1 Portanto: 1.3.5. (2n-3).(2n-1) = 1.2.3.4... 2.4.6 = Exemplo 1.4 Calcular a soma: 1.1! + +...+ Tomemos a igualdade: k.k! - k! e nela façamos sucessivamente k = o que dá: n.n. - n!</p><p>20 Somando ordenadamente todas essas n igualdades simplifi cando, obtemos: 1.1! + + +...+ :-1 1.5 BINOMIAL Definição 1.3 Sejam dois inteiros tais que Chama-se binomial de numerador n e classe o inteiro que se indica por e tal que = Obviamente, tambem podemos escrever: = n(n-1) ...(n-k k! Em particular, para k = 0 ou k = n, temos: Assim, p.ex.: = = 8.7.6 = 56 3.2.1.5.4.3.2.1 3.2.1 = = 3.2.1 =</p><p>21 1.6 NÚMEROS BINOMIAIS COMPLEMENTARES Definição 1.4 Chamam-se numeros binomiais complementares dois numeros binomiais que o mesmo numerador e cuja so ma das suas classes respectivas e igual ao numerador co- mum. Assim, ; (20) e (20) sao numeros binomiais comple- mentares, pois, o mesmo numerador 20 e 7 + 13 20. Teorema 1.3 Dois numeros binomiais complementares sao iguais. Sejam e dois números binomiais complementares. Entao, Portanto: = (n - (n n! - - = ! h! = 1.7 NÚMEROS BINOMIAIS CONSECUTIVOS Definicao 1.5 Chamam-se binomiais consecutivos dois numeros binomiais que tem o mesmo numerador e cujas classes respectivas sao inteiros consecutivos. Assim, p. ex. , 18 e 18 10 sao numeros binomiais consecu-</p><p>22 tivos, pois, tem o mesmo numerador 18 e as suas classes respectivas sao os inteiros consecutivos 9 e 10. Teorema 1.4 Entre dois numeros binomiais consecutivos e com subsiste a relação de STIFEL: Demonstração: Com efeito: + = n! = + = n! = = = = Assim, p.ex.:</p><p>23 1.2 + + Demonstração: Com efeito, mudando na relação de STIFEL n sucessivamente por n-1, n-2, n-3, ..., k, obtemos: = Alem disso, e evidente: Somando ordenadamente todas essas igualdades e suprimindo os termos comuns aos dois membros acha-se a dese- jada. Substituindo, nesta cada numero binomial pelo seu complementar, obtemos: a Corolário 1.3 + +...+</p><p>24 Demonstração: Consoante a relação de STIFEL, temos: + disso, Somando ordenadamente todas essas igualdades e suprimindo os termos comuns aos dois membros acha-se a relação dese- jada.</p><p>25 EXERCÍCIOS 1. Calcular a soma dos n primeiros inteiros positivos. 2. Calcular o inteiro positivo n sabendo: = 2592 3. Calcular o inteiro positivo n sabendo: + 3n+1 + 3n+2 + 3n+3 1080 4. Achar os valores de para os quais + I e um quadrado perfeito. 5. Sendo m e n inteiros positivos, dizer se e verdadeiro ou falso: = e = + n! 6. Demonstrar: - = 7. Sendo demonstrar: 8. Decompor o inteiro 565 numa soma de cinco inteiros pares consecutivos. 9. Achar todas as inteiras e positivas da equa-</p><p>26 10. Achar um inteiro positivo de dois algarismos-que ja igual ao quadruplo da soma dos seus algarismos. 11. Achar o menor e o maior inteiro positivo de n algaris mos. 12. Resolver a 13. Resolver a equação: X 2 7 = 7 ) 14. Demonstrar: 15. Achar todas as soluçoes inteiras e positivas da equa- x2 - 16. Verificar que o quadrado de um inteiro nao pode termi nar em 2, 3, 7 ou 8. 17. Reconstituir as adições: (a) 3 * 76 + 2 * * * + 5 * 28 12838 (b) 5 * 23 + 40 * * + 1269 = 1 * 927 18. Reconstituir as subtrações: (a) 1 * 256 - 431 * = 89 * 6 (b) 63 * 1 - 43 * If 5 * 86</p><p>27 19. 0 produto de um inteiro positivo de tres algarismos por 7 termina à direita por 638. Achar esse inteiro. 20. Determinar quantos algarismos se empregam para nume- rar todas as paginas de um livro que tem 2748 nas. 21. Reconstituir as multiplicações: (a) 4 3 5 (b) 2 * 03 * 6 * 2 0 4806 1305 * 1 148986 22. Calcular a soma dos tres maiores inteiros de, respec- tivamente, tres, quatro e cinco 23. Determinar a diferença entre o maior inteiro com seis algarismos diferentes e o maior inteiro com cinco al- garismos tambem diferentes. 24. Um livro tem 1235 Determinar o numero de ve- zes que o algarismo 1 aparece na das pagi- nas deste livro.</p><p>28 25. Reconstituir as divisoes: (a) * * ** (b) 6 4 * 26. Mostrar que o produto de quatro inteiros consecutivos, aumentado de 1, e um quadrado perfeito. 27. A soma dos quadrados de dois inteiros e 3332 e um de- les e o quadruplo do outro. Achar os dois 28. Sejam a e b dois Demonstrar: max(a,b) If (a + b + 29. Determinar o inteiro n>1 de modo que a soma n! seja um quadrado perfeito. 30. A media de dois inteiros positivos e 5 e a media geometrica e 4. Achar os dois inteiros. 31. Achar os cinco inteiros positivos consecutivos cuja soma dos quadrados e igual a 2010. 32. 0 resto por falta da raiz quadrada de um inteiro posi tivo e 135 e o resto por excesso e 38. Achar esse in- teiro.</p><p>29 33. Resolver a 31 = 29 34. Achar o inteiro que deve ser somado a cada um dos in- teiros 2, 6 e 14 para que, nesta ordem, formem uma proporção continua. 35. Mostrar que o produto 12345679 X sendo k#0 um algarismo, e kkk.kkk.kkk. 36. Achar o valor minimo de uma soma de 10 inteiros posi- tivos distintos, cada um dos quais se escreve com tres algarismos. 37. Mostrar que o produto 37037037 X sendo k # 0 um algarismo, e kkk.kkk.kkk. 38. Um estudante ao efetuar a multiplicação de 7432 por um certo inteiro achou produto 1731656, tendo troca do, por engano, o algarismo das dezenas do multiplica dor, tomando um 3 em vez de 8. Achar o verdadeiro pre duto. 39. Achar o menor inteiro cujo produto por 21 e um intei- ro formado apenas com algarismos 4. 40. Escreve-se a natural dos inteiros positi- vos, sem separar os Determinar:</p><p>30 (a) o 4350 algarismo que se escreve; (b) o algarismo que se escreve; (c) o algarismo que se escreve. 41. Escreve-se a sequência natural dos inteiros positi- vos pares, sem separar os algarismos: 24681012141618 Determinar 25740 algarismo que se escreve. 42. Reconstituir as multiplicações: (a) * * (b) * * * * * ***** **** 90329 36733 43. Mostrar que o produto de dois fatores entre 10 e 20 e o da soma do primeiro com as unidades do se- gundo, mais o produto das unidades dos dois. 44. Achar o menor inteiro positivo que multiplicado por 33 da um produto cujos algarismos sao todos 7. 45. Os inteiros a e b sao tais que 4<a<7 e 3<b<4. Mostrar que 46. Os inteiros a e b sao tais que e Mostrar que 47. inteiros a e b sao tais que e Mostrar que -4</p><p>CAPÍTULO 2 MATEMÁTICA 2.1 ELEMENTO MÍNIMO DE UM CONJUNTO DE INTEIROS 2.1 Seja A um conjunto de Chama-se elemento minimo de A um elemento aEA tal que a <x pa- ra todo XEA. Representa-se pela notação "minA", que se "minimo de A". Portanto, simbolicamente: minA = a e Teorema 2.1 Se a e elemento minimo de A, então este ele- mento e Demonstração: Com efeito, se existisse um outro elemento minimo b de A, (i) a <b, porque a = minA (ii) b <a, porque b = minA</p><p>32 Logo, pela propriedade da relação de ordem natural em temos a = b. 0 elemento minimo de A, se existe, denomina-se tambem pri meiro elemento de A ou menor elemento de A. Exemplo 2.1 0 conjunto N = {1,2,3,...} dos inteiros po- sitivos tem o elemento minimo, que e 1 (minN = 1), por que e para todo Exemplo 2.2 0 conjunto A = > 12} tem o elemento minimo, que e 13 (minA = 13), porque e pa ra todo X EA. Exemplo 2.3 0 conjunto = dos intei- ros nao positivos não tem elemento minimo, porque não - existe tal que a<x para todo Exemplo 2.4 0 conjunto A = N 3 divide X 2 } tem o elemento 3 (minA = 3), porque 3EA (3 divide 9) e para todo XE A e 2.2 PRINCÍPIO DA BOA ORDENAÇÃO Todo conjunto vazio A de inteiros não negativos pos- sui elemento minimo. Em outros termos, todo subconjunto nao vazio A do conjun- to</p><p>33 dos inteiros nao negativos # possui o elemen- to minimo, isto e, 3 minA Exemplo 2.5 0 conjunto {1,3,5,7,...} dos inteiros positivos impares e um subconjunto nao vazio de Logo, pelo "Principio da boa A possui o ele- mento minimo Exemplo 2.6 0 conjunto P = {2,3,5,7,11,... dos intei- ros primos e um subconjunto nao vazio de # Logo, pelo "Principio da boa P possui o ele- mento minimo (minP = 2). Teorema 2.2 (de ARCHIMEDES) Se a e b sao dois inteiros positivos quaisquer, entao existe um inteiro positivo n tal que na b. Demonstração: Suponhamos que a e b sao dois inteiros positivos para os quais na <b para todo inteiro positivo n. to- dos os elementos do conjunto: sao inteiros positivos e, da boa ordena- S possui o elemento minimo, digamos mins = b-ka.</p><p>34 E como b - (k + 1) a pertence a S, porque S contem tódos os inteiros positivos desta forma, temos: b - - - a<b ka isto e, b - ka nao o elemento minimo de S, o que e uma contradição. Logo, a propriedade archimediana e verda deira. Assim, p.ex.: (i) se a = 2 e b If 11, entao n = 6, porque (ii) se a = 9 e b = 5, entao porque 5. 2.3 PRINCÍPIO DE FINITA Teorema 2.3 Seja S um subconjunto do conjunto N dos in- teiros positivos que satisfaz as duas seguintes (1) 1 pertence a S (2) para todo inteiro, positivo k, se k + Nestas S e o conjunto N dos inteiros positi- vos: S = N. Demonstração: Suponhamos, por absurdo, que S nao e o conjunto N dos in- teiros positivos (S # e seja X o conjunto de todos os</p><p>35 inteiros positivos que nao pertencem a S, isto e: XEN e N - S Então, X e um subconjunto nao vazio de e, pe- lo "Principio da boa existe o elemento de Pela de modo que 1 e, portanto, o - 1 um inteiro positivo que nao pertence a X. Logo, - e, pela condição (2), segue-se que (x_1)+1 = o o que e uma pois, E X = N - S, is to e, of S. Assim sendo, X Consoante este "Principio de indução finita", o único sub conjunto de N que satisfaz às condições (1) e (2) e o pro prio N. 2.4 Teorema 2.4 Seja P(n) uma proposição associada a cada in teiro positivo n e que satisfaz duas seguintes condi- (1) P(1) e verdadeira; (2) para todo inteiro positivo k, se P(k) e verdadeira, entao P(k+1) tambem e verdadeira. Nestas condições, a proposição P(n) verdadeira para to- do inteiro positivo n.</p><p>36 Demonstração: Seja S o conjunto de todos os inteiros positivos n para os quais a proposição P(n) e verdadeira, isto e: e verdadeira } Pela condição (1), P(1) e verdadeira e, portanto, la condição (2), para todo inteiro positivo k, se KES,en tao Logo, conjunto S satisfaz condições (1) e (2) do "Principio de indução finita" e, portanto, S=N, isto e, a proposição P(N) e verdadeira para todo inteiro positivo n. NOTA. 0 teorema 2.4 e geralmente denominado "Teorema da indução matematica" ou "Principio de indução matematica", e a demonstração de uma proposição usando-se este teorema chama-se "demonstração por indução matematica" ou "demons tração por indução sobre n". Na "demonstração por indução matematica" de uma dada pro- P(n) e obrigatório verificar que as (1) e (2) sao ambas satisfeitas. A verificação da (1) e geralmente muito mas a verificação da (2) implica em demonstrar o teorema auxiliar cuja hipote- se H: proposição e verdadeira, KEN denominada de indução", e cuja tese ou conclu- sao e : T: proposição P(k+1) e verdadeira.</p><p>37 2.5 EXEMPLOS DE DEMONSTRAÇÃO POR INDUÇÃO Exemplo 2.7 Demonstrar a proposição: P(n) : 1 3 5 ...+ + + + Demonstração: (1) P(1) e verdadeira, visto que = (2) A de indução e que a proposição: 1 + 3 + 5 + ... + KEN e verdadeira. Adicionando 2k+1 a ambos os membros desta igualdade, ob temos: (2k-1) + (2k+1) = + (2k+1) = (k+1)2 e isto significa que a proposição P(k+1) e verdadeira. Logo, pelo "Teorema da indução matematica", a proposi- çao P(n) e verdadeira para todo inteiro positivo n. Exemplo 2.8 Demonstrar a proposição: P(n) : 1.2 1 + 2.3 1 + 3.4 1 + + 1 = n , Demonstração: (1) P(1) verdadeira, visto que 1 = 1 1.2 1+1 . (2) A de indução e que a proposição:</p><p>38 P(k): 1 + 2.3 1 + 3.4 1 +...+ = k+1 , 1.2 KEN e verdadeira. Adicionando (k+1) a ambos os membros desta igualda (k+2) de, obtemos: + 2.3 + 3.4 + = (k+1)(k+2) If k + 1 = k+1 = k+2 e isto significa que a proposição P(k+1) e verdadeira.Lo go, pelo "Teorema da indução matematica", a P(n) e verdadeira para todo inteiro positivo n. Exemplo 2.9 Demonstrar a proposição: P(n) : - 1) , Demonstração: (1) P(1) e verdadeira, visto que 3 (2) A de indução e que a proposição: P(k) : 1) , KEN e verdadeira. Portanto: 22k 3q, com o que implica:</p><p>39 (k+1) 1 = 22.22k - 1 = 4.22k - 1 = 4 + 4 - 1 1) + 3 = = isto e, a proposição P(k+1) e verdadeira. Logo, pelo "Teo rema da indução a proposição P(n) e verdadei ra para todo inteiro positivo n. Exemplo 2.10 Demonstrar a proposição: P(n): Demonstração: (1) P(1) e verdadeira, visto que = (2) A de indução e que a proposição: P(k): KEN e verdadeira. Portanto: ou 2k+1 o que implica: isto e, a proposição P(k+1) e verdadeira. Logo, pelo "Teorema da indução a proposição P(n) e verdadeira para todo inteiro positivo n.</p><p>40 2.6 OUTRAS FORMAS DA INDUÇÃO Teorema 2.5 Seja r um inteiro positivo fixo e seja P(n) uma proposição associada a cada inteiro n>r e que sa- tisfaz duas seguintes (1) P(r) e verdadeira; (2) para todo inteiro se P(k) e verdadeira, P(k+1) tambem e verdadeira. Nestas P(n) e verdadeira para todo inteiro n>r. Demonstração: Seja S o conjunto de todos os inteiros positivos n para os quais a proposição (r + n - e verdadeira, isto e: e verdadeira } Pela condição P(r + 1 1) e verdadeira, isto e, 1E S. E, pela (2), se P(r + k 1) e verda- deira, + 1) = P(r + (k + 1) tambem e verdadeira, isto e, se KES, então Lo go, pelo "Principio de indução finita", S e o conjunto dos inteiros positivos: S = N, isto e, a proposição P(r + n - 1) e verdadeira ou seja, o que e a mesma coisa, a proposição P(n) e verdadeira para todo inteiro</p><p>41 Exemplo 2.11 Demonstrar a P(n) : , Demonstração: (1) P(4) e verdadeira, visto que 24 = = = 24. (2) Suponhamos, agora, que e verdadeira a proposição: P(k) por ser temos: 2k+1 <k! (k+1) ou < (k+1) ! isto e, a proposição P(k+1) e verdadeira. Logo, pelo teo rema 2.5, a proposição P(n) e verdadeira para todo intei- ro Observe-se que a proposição P(n) e falsa para n = 1,2,3, pois, temos: , Exemplo 2.12 Demonstrar a proposição: P(n) : Demonstração: (1) P(3) e verdadeira, visto que 32 9 > 2.3 + 1 = 7.</p><p>42 (2) Suponhamos, agora, que e verdadeira a P(k) : k>3 , Entao, temos: k2 + (2k+1) > (2k+1) + (2k+1) + 6 e, portanto: + 1 isto e, a proposição P(k+1) e teo- rema 2.5, a proposição P(n) e verdadeira para todo intei- ro n>3. Observe-se que a proposição P(n) e falsa para n = len = pois, temos: + 1 e + 1 Teorema 2.6 Seja P(n) uma proposição associada a cada inteiro positivo n e que satisfaz duas seguintes condi (1) P(1) e verdadeira; (2) para todo inteiro positivo k, se P(1),P(2) P(k) sao todas entao P(k+1) tambem e verda deira.</p><p>43 Nestas condições, a proposição P(n) e verdadeira para to do inteiro positivo n. Demonstração: Seja S o conjunto de todos os inteiros positivos n para os quais a proposição P(n) e verdadeira, isto e: e verdadeira } Suponhamos, por absurdo, que S # N e seja X o conjunto de todos os inteiros positivos que nao pertencem a S, is- to e: e = N - S Entao, X e um subconjunto nao vazio de pelo "Princi- pio da boa existe o elemento minimo j de X (minX = j). Pela condição (1), de modo que j>1, e como e o menor inteiro positivo que nao pertence a S, segue-se que as proposições P(1), P(2) P(j-1) sao todas verdadei- ras. Entao, pela condição (2), a proposição P(j) e verda deira e jes, o que e uma contradição, pois, jex, isto e, jc S. Assim sendo, S = N e a proposição P(n) e ver- dadeira para todo inteiro positivo n. Teorema 2.7 Seja r um inteiro positivo fixo e seja P(n) uma proposição associada a cada inteiro e que sa- tisfaz as duas seguintes</p><p>44 (1) P(r) e verdadeira; (2) para todo inteiro se P(m) e verdadeira para todo inteiro m tal que P(k) e verda Nestas condições, a proposição P(n) e verdadeira para to- do inteiro n>r. Demonstração: Seja S o conjunto de todos os inteiros para os quais a proposição P(n) e falsa, isto e: e P(n) e falsa } Suponhamos, por absurdo, que S nao e vazio (S # ). En- tao, pelo "Principio da boa ordenação", existe o elemen- to minimo j de = j). Pela condição (1) , r de modo que j>r, e por conse- guinte P(m) e verdadeira para todo inteiro m tal que Assim sendo, pela condição (2), P(j) e verdadei- ra e que e uma contradição, pois, jes. Logo, o conjunto S e vazio (S = e a proposição P(n) e verda- deira para todo inteiro</p><p>45 EXERCÍCIOS 1. Demonstrar por "indução matematica": (n+1) (2n+1), (b) (c) +...+ (d) +...+ (e) 1.2 + 2.3 + 3.4 + (g) 2. Demonstrar por "indução (a) 2nd (b) (c) (d) (e) (f) 3. Demonstrar por (a) 2 (b) 6</p><p>46 (c) 5 (d) 24 (52n-1), (e) 7 (23n- 1), (f) 8 4. Demonstrar que 10n+1 - - 10 e um miltiplo de 81 pa ra todo inteiro positivo n. 5. Demonstrar que + 15 7n e um inteiro positivo pa ra todo</p><p>CAPÍTULO 3 SOMATORIOS E PRODUTÓRIOS 3.1 Sejam os n>1 inteiros Para indicar, de modo abreviado, a soma + +...+ an desses intei- n ros usa-se a n a i=1 que se "somatorio de de 1 a Em particular, para n = , temos: 2 3 = i=1 + + i=1 A letra i chama-se o indice do somatório e pode ser subs- tituida por qualquer outra diferente de a e de - e um indice mudo. E os inteiros 1 e n que figuram abaixo e aci ma da letra grega (sigma) chamam-se respecti vamente limite inferior e superior do i.</p><p>48 0 numero de parcelas de um somatório e sempre igual di- ferença os limites superior e inferior do seu indi- ce mais uma unidade. Se m e n sao dois inteiros, com por defini n i=m = + n Exemplo 3.1 Temos: 7 5i = 5.1 + 5.2 + 5.3 + 5.4 + 5.5 + 5.6 + 5.7 = i=1 = + 10 + 15 + 20 + 25 + 30 + 35 = 140 4 (8j-3) = (8.1-3) + (8.2-3) + (8.3-3) + (8.4-3) = j=1 = + 13 + 21 + 29 = 68 3 k.2k = 3.23 + 4.24 + 5.25 + 6.26 + 7.27 + 8.28 = k=3 If 24 + 64 + 160 + 384 + 896 + 2048 = 3576 Exemplo 3.2 Temos: 6 2 + 4 + 8 + 16 + 32 + 64 = i=1 15 + 29 = - j=1</p><p>49 3.2 PROPRIEDADES DOS SOMATÓRIOS n Teorema 3.1 i=1 = i i=1 Demonstração: Com efeito, desenvolvendo o primeiro membro, temos: n i=1 + + ... + = = = i=1 i i=1 n Teorema 3.2 a = na i=1 Demonstração: Seja = a para i Então, temos: n n a = = = i=1 i=1 n n Teorema 3.3 = i=1 i=1 Demonstração: Consoante os dois teoremas anteriores, temos:</p><p>50 n n n i=1 a = + na i=1 i=1 n Teorema 3.4 i=1 Com efeito, desenvolvendo o primeiro membro, temos: n E = i=1 20 Exémplo 3.3 Calcular i=1 Consoante os teoremas anteriores temos, sucessivamente: 20 20 20 20 = = = i=1 i=1 i=1 i=1 5(1 + 2 + + 20) + 40 = + 20)20 + 40 If 5.210 + 40 = 1090 3.3 SOMATORIOS DUPLOS n Teorema 3.5 E i,j=1 ij</p><p>51 Com efeito, desenvolvendo o primeiro membro, temos: n i,j=1 = + + + + + + ou seja: n n n n n n = + i,j=1 j=1 j=1 + i=1 n m Teorema 3.6 = j=1 i=1 i=1 j=1 Demonstração: Com efeito, pelo teorema 3.4, temos: m n n m a.b. = = j=1 i=1 j=1 i=1 = bj i=1 j=1 2 3 Exemplo 3.4 Calcular j=1 i=1 Consoante o teorema 3.6, temos:</p><p>52 3 2 3j = (2 + + 32, = 23 j=1 i=1 i=1 j=1 = 14.12 = 168 3.4 Sejam os n>1 inteiros Para indicar, de mo do abreviado, o produto desses n inteiros usa- se a n II i=1 que se "produtório de de 1 a n". Em particular, para n = , temos: 2 3 II II i=1 i=1 A letra i chama-se o indice do produtório e pode ser subs por qualquer outra diferente de a e de n - e um indice mudo. E os inteiros 1 e n que figuram abaixo e aci ma da letra grega II (pi) chamam-se respectiva- mente inferior e limite superior do i. 0 numero de fatores de um e sempre igual à di- ferença entre os superior e inferior do seu ce mais uma unidade.</p><p>53 Se men sao dois inteiros, com por defini n II = an i=m Exemplo 3.5 Temos: 6 II 3i = (3 .1) (3.2) (3.3)(3.4)(3.5)(3.6) = i=1 = 3.6.9.12.15.18 = 524880 4 II (5j - 3) = (5.1 - 3) (5.2 - - 3) (5.4 - 3) = j=1 = 2.7.12.17 = 2856 Exemplo 3.6 Temos: 6 3.9.27.81.243.729 = II i=1 16 1.3.5.7....31 = II (2j - 1) j=1 n 1.2.3 = i=1 3.5 PROPRIEDADES DOS Teorema 3.7 n II a.b. = II b. 11 1 i=1 i=1 i=1</p><p>54 Demonstração: Com efeito, desenvolvendo o primeiro membro, temos: n II i=1 = i=1 i=1 n. Teorema 3.8 II = i=1 Demonstração: Seja para i = Entao, temos: n n i=1 II a = II = ... i=1 Teorema 3.9 II = i=1 i=1 Demonstração: Com efeito, desenvolvendo o primeiro membro, temos: n n i=1 II = = a. i=1 4 Exemplo 3,7 Calcular II i=1 Consoante teorema 3.7, temos:</p>