Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 1 Números Naturais Sumário 1.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 O Conjunto dos Números Naturais . . . . . . . . . . 3 1.3 O Axioma da Indução . . . . . . . . . . . . . . . . . 4 1.4 As Duas Operações: Adição e Multiplicação . . . . 5 1.5 A Ordenação nos Números Naturais . . . . . . . . . 6 1.6 Exercícios Recomendados . . . . . . . . . . . . . . . 8 1.7 Textos Complementares . . . . . . . . . . . . . . . . 10 1.1 Introdução �Deus criou os números naturais. O resto é obra dos homens.� Leopold Kronecker Enquanto os conjuntos constituem um meio auxiliar, os números são um dos dois objetos principais de que se ocupa a Matemática. O outro objeto é o espaço, juntamente com as �guras geométricas nele contidas. Os números são objetos abstratos que foram desenvolvidos pelo homem para servir como modelos que permitem contar e medir e, portanto avaliar as diferentes quantidades de uma grandeza. Os compêndios tradicionais dizem o seguinte: �Número é o resultado da comparação entre uma grandeza e a unidade. Se a grandeza é discreta, essa comparação chama-se uma contagem e o resultado é um número inteiro; se a grandeza é contínua, a comparação chama-se uma medição e o resultado é um número real.� Nos padrões atuais de rigor matemático, o trecho acima não pode ser consi- derado como uma de�nição matemática, pois faz uso de idéias (como grandeza, unidade, discreta, contínua) e processos (como comparação) de signi�cado não estabelecido. Entretanto, todas as palavras que nela aparecem possuem um sentido bastante claro na linguagem do dia-a-dia. Por isso, embora não sirva para demonstrar teoremas a partir dela, a de�nição tradicional tem o grande mérito de nos revelar para que servem e por qual motivo foram inventados os números. Isto é muito mais do que se pode dizer sobre a de�nição que encon- tramos no nosso dicionário mais conhecido e festejado, conforme reproduzimos a seguir. Número. [Do lat. numeru.] S.m. 1. Mat. O conjunto de todos os conjuntos equivalentes a um conjunto dado. Discutiremos este ponto logo mais, quando tratarmos de números cardinais. + Para Saber Mais - Comentários sobre De�nições e axiomas - Cli- que para ler Unidade 1Números Naturais + Na Sala de Aula - Re�exões sobre a sala de aula - Clique para ler 1.2 O Conjunto dos Números Naturais Lentamente, à medida em que se civilizava, a humanidade apoderou-se desse modelo abstrato de contagem (um, dois, três, quatro, ...) que são os números naturais. Foi uma evolução demorada. As tribos mais rudimentares contam apenas um, dois, muitos. A língua inglesa ainda guarda um resquício desse estágio na palavra thrice, que tanto pode signi�car �três vezes� como �muito� ou �extremamente�. As necessidades provocadas por um sistema social cada vez mais complexo e as longas re�exçõs, possíveis graças à disponibilidade de tempo trazida pelo progresso econômico, conduziram, através dos séculos, ao aperfeiçoamento do extraordinário instrumento de avaliação que é o conjunto dos números naturais. Decorridos muitos milênios, podemos hoje descrever concisa e precisamente o conjunto N dos números naturais, valendo-nos da notável síntese feita pelo matemático italiano Giuseppe Peano no limiar do século 20. N é um conjunto, cujos elementos são chamados números naturais. A essência da caracterização de N reside na palavra �sucessor�. Intuitivamente, quando n, n′ ∈ N, dizer que n′ é o sucessor de n signi�ca que n′ vem logo depois de n, não havendo outros números naturais entre n e n′. Evidentemente, esta explicação apenas substitui �sucessor� por �logo depois�, portanto não é uma de�nição. O termo primitivo �sucessor� não é de�nido explicitamente. Seu uso e suas propriedades são regidos por algumas regras, abaixo enumeradas: a) Todo número natural tem um único sucessor; b) Números naturais diferentes têm sucessores diferentes; c) Existe um único número natural, chamado um e representado pelo símbolo 1, que não é sucessor de nenhum outro; d) Seja X um conjunto de números naturais (isto é, X ⊂ N). Se 1 ∈ X e se, além disso, o sucessor de todo elemento de X ainda pertence a X, então X = N. 3 Unidade 1 O Axioma da Indução As a�rmações (a), (b), (c) e (d) acima são conhecidas como os axiomas de Peano. Tudo o que se sabe sobre os números naturais pode ser demonstrado como consequência desses axiomas. + Para Saber Mais - Sobre o sistema de numeração - Clique para ler + Para Saber Mais - Um comentário gramatical - Clique para ler + Na Sala de Aula - Uma recomendação - Clique para ler 1.3 O Axioma da Indução O último dos axiomas de Peano é conhecido como o axioma da indução. Ele é a base de um e�ciente método de demonstração de proposições referentes a números naturais (demonstrações por indução, ou por recorrência). Enunciado sob a forma de propriedades em vez de conjuntos, ele se formula assim: Seja P (n) uma propriedade relativa ao número natural n. Suponhamos que i) P (1) é válida; ii) Para todo n ∈ N, a validez de P (n) implica a validez de P (n′), onde n′ é o sucessor de n. Então P (n) é válida qualquer que seja o número natural n. Com efeito, se chamarmos de X o conjunto dos números naturais n para os quais P (n) é válida, veremos que: 1 ∈ X em virtude de (i); e que n ∈ X ⇒ n′ ∈ X em virtude de (ii). Logo, pelo axioma da indução, concluímos que X = N. Definição 1 Esta formulação do Axioma da Indução é chamada de Princípio de Indução Matemática 4 Unidade 1Números Naturais + Para Saber Mais - Cuidado! - Clique para ler 1.4 As Duas Operações: Adição e Multipli- cação Entre os números naturais estão de�nidas duas operações fundamentais: a adição, que aos números n, p ∈ N faz corresponder a soma n + p e a multiplicação, que lhes associa o produto np. A soma n + p é o número natural que se obtém a partir de n aplicando-se p vezes seguidas a operação de tomar o sucessor. Em particular, n + 1 é o sucessor de n, n + 2 é o sucessor do sucessor de n, etc. Por exemplo, tem-se 2 + 2 = 4 simplesmente porque 4 é o sucessor do sucessor de 2. De agora em diante, o sucessor do número natural n será designado por n+ 1. Quanto ao produto, põe-se n · 1 = n por de�nição e, quando p 6= 1, np é a soma de p parcelas iguais a n. Em última análise, a soma n+ p e o produto np têm mesmo os signi�cados que lhes são atribuídos pelas explicações dadas acima. Entretanto, até que saibamos utilizar os números naturais para efetuar contagens, não tem sentido falar em �p vezes� e �p parcelas�. Por isso, as operações fundamentais devem ser de�nidas por indução, como se segue. Adição: n + 1 = sucessor de n e n + (p + 1) = (n + p) + 1 . Esta última igualdade diz que se sabemos somar p a todos os números naturais n, sabemos também somar p+1: a soma n+(p+1) é simplesmente o sucessor (n+p)+1 de n + p . O axioma da indução garante que a soma n + p está de�nida para quaisquer n, p ∈ N. Multiplicação: n·1 = n e n(p+1) = np+n. Ou seja: multiplicar um número n por 1 não o altera. E se sabemos multiplicar todos os números naturais n por p, sabemos também multiplicá-los por p+1: basta tomar n(p+1) = np+n. Por indução, sabemos multiplicar todo n por qualquer p. Estas operações gozam das conhecidas propriedades de associatividade, comutatividade e distributividade. As demonstrações são feitas por indução. (Voltaremos ao assunto na Unidade 5 de MA12, onde mais detalhes serão apresentados.) 5 Unidade 1 A Ordenação nos Números Naturais 1.5 A Ordenação nos Números Naturais Nossa breve descrição do conjunto N dos números naturais termina com a relação de ordem m < n. Dados m, n ∈ N, diz-se que m é menor do que n, e escreve-se m < n, para signi�car que existe algum p ∈ N tal que n = m + p. (Isto quer dizer que n é o sucessor do sucessor... do sucessor de m, o ato de tomar o sucessor sendo iterado p vezes.) A relação m < n tem as seguintes propriedades: Transitividade: Se m < n e n < p então m < p. Tricotomia: Dados m, n ∈ N, vale uma, e somente uma, das alternativas:m = n, m < n ou n < m. Monotonicidade: Se m < n então, para qualquer p ∈ N, tem-se m+p < n+p e mp < np. Boa-ordenação: Todo subconjunto não-vazio X ⊂ N possui um menor ele- mento. Isto signi�ca que existe um elemento m0 ∈ X que é menor do que todos os demais elementos de X. A boa-ordenação pode muitas vezes substituir com vantagem a indução como método de prova de resultados referentes a números naturais. São muito raros e pouco interessantes os exemplos de demonstração por indução que podem ser dados sem usar as operações fundamentais e as desi- gualdades. Por isso, somente agora apresentamos um deles, seguido de uma demonstração por boa-ordenação. Exemplo 1. Queremos provar a validez, para todo número natural n, da igualdade P (n) : 1 + 3 + 5 + . . .+ (2n− 1) = n2 Usaremos indução. Para n = 1, P (1) se resume a a�rmar que 1 = 1. Supondo P (n) verdadeira para um certo valor de n, somamos 2n+1 a ambos os membros da igualdade acima, obtendo 1 + 3 + 5 + . . .+ (2n− 1) + (2n+ 1) = n2 + 2n+ 1, 6 Unidade 1Números Naturais ou seja: 1 + 3 + 5 + . . .+ [2(n+ 1)− 1] = (n+ 1)2. Mas esta última igualdade é P (n+1). Logo P (n) ⇒ P (n+1). Assim, P (n) vale para todo n ∈ N. Podemos então a�rmar que a soma dos n primeiros números ímpares é igual ao quadrado de n. Exemplo 2. (Usando boa-ordenação.) Lembremos que um número natural p chama-se primo quando não pode ser expresso como produto p = mn de dois números naturais, a menos que um deles seja igual a 1 (e o outro igual a p); isto equivale a dizer que os fatores m, n não podem ser ambos menores do que p. Um resultado fundamental em Aritmética diz que todo número natural é primo ou é um produto de fatores primos. Provaremos isto por boa ordenação. Usaremos a linguagem de conjuntos. Seja X o conjunto dos números naturais que são primos ou produtos de fatores primos. Observemos que se m e n pertencem a X então o produto mn pertence a X. Seja Y o complementar de X. Assim, Y é o conjunto dos números naturais que não são primos nem são produtos de fatores primos. Queremos provar que Y é vazio. Isto será feito por redução ao absurdo (como sempre se dá nas demonstrações por boa- ordenação). Com efeito, se Y não fosse vazio, haveria um menor elemento a ∈ Y . Então todos os números menores do que a pertenceriam a X. Como a não é primo, ter-se-ia a = m · n, com m < a e n < a, logo m ∈ X e n ∈ X. Sendo assim, mn ∈ X. Mas mn = a, o que daria a ∈ X, uma contradição. Segue-se que Y = ∅ , concluindo a demonstração. 7 Unidade 1 Exercícios Recomendados 1.6 Exercícios Recomendados 1. Dado o número natural a, seja Y ⊂ N um conjunto com as seguintes propriedades: (1) a ∈ Y ; (2) n ∈ Y ⇒ n+ 1 ∈ Y . Prove que Y contém todos os números naturais maiores do que ou iguais a a. (Sugestão: considere o conjunto X = Ia ∪ Y , onde Ia é o conjunto dos números naturais 6 a, e prove, por indução, que X = N.) 2. Use o exercício anterior para provar que 2n+ 1 6 2n para todo n > 2 e, em seguida, que n2 < 2n para todo n > 5. 3. Complete os detalhes da seguinte demonstração do Princípio de Boa Ordenação: Seja A ⊂ N um conjunto que não possui um menor ele- mento. Considere o conjunto X formado pelos números naturais n tais que 1, 2, ..., n não pertencem a A. Observe que 1 ∈ X e, além disso, se n ∈ X então todos os elementos de A são > n + 1. Como n + 1 não pode ser o menor elemento de A, conclua que n + 1 ∈ X. Logo, por indução, segue-se que X = N. Portanto A é vazio. 4. Prove, por indução, que (n+ 1 n )n 6 n para todo n > 3 e conclua daí que a sequência 1, √ 2, 3 √ 3, 4 √ 4 . . . é decrescente a partir do terceiro termo. 5. Prove, por indução, que 1 + 22 + 32 + · · ·+ n2 = n(n+ 1)(2n+ 1) 6 . 6. Critique a seguinte argumentação: Quer-se provar que todo número natu- ral é pequeno. Evidentemente, 1 é um número pequeno. Além disso, se n for pequeno, n+ 1 também o será, pois não se torna grande um número pequeno simplesmente somando-lhe uma unidade. Logo, por indução, todo número natural é pequeno. 8 Unidade 1Números Naturais 7. Use a distributividade para calcular (m + n)(1 + 1) de duas maneiras diferentes e em seguida use a lei do corte para concluir quem+n = n+m. 8. Seja X ⊂ N um conjunto não-vazio, com a seguinte propriedade: para qualquer n ∈ N, se todos os números naturais menores do que n perten- cem a X então n ∈ X. Prove que X = N. (Sugestão: boa ordenação.) 9. Seja P (n) uma propriedade relativa ao número natural n. Suponha que P (1), P (2) são verdadeiras e que, para qualquer n ∈ N, a verdade de P (n) e P (n + 1) implica a verdade de P (n + 2). Prove que P (n) é verdadeira para todo n ∈ N. 10. Use indução para provar que 13 + 23 + 33 + · · ·+ n3 = 1 4 n2(n+ 1)2. 9 Unidade 1 Textos Complementares 1.7 Textos Complementares Na Sala de Aula Re�exões sobre a sala de aula Do ponto de vista do ensino em nível do ensino médio, não tem cabimento expor a Matemática sob forma axiomática. Mas é necessário que o professor saiba que ela pode ser organizada sob a forma acima delineada. Uma linha de equilíbrio a ser seguida na sala de aula deve basear-se nos seguintes preceitos: 1. Nunca dar explicações falsas sob o pretexto de que os alunos ainda não têm maturidade para entender a verdade. (Isto seria como dizer a uma criança que os bebês são trazidos pela cegonha.) Exemplo: �in�nito é um número muito grande�. Para outro exemplo, vide RPM 29, págs. 13-19. 2. Não insistir em detalhes formais para justi�car a�rmações que, além de verdadeiras, são intuitivamente óbvias e aceitas por todos sem discussão nem dúvidas. Exemplo: o segmento de reta que une um ponto interior a um ponto exterior de uma circunferência tem exatamente um ponto em comum com essa circunferência. Em contraposição, fatos importantes cuja veracidade não é evidente, como o Teorema de Pitágoras ou a Fórmula de Euler para poliedros convexos, devem ser demonstrados (até mesmo de várias formas diferentes). Excetuam-se, naturalmente, demonstrações longas, elaboradas ou que fa- çam uso de noções e resultados acima do alcance dos estudantes desse nível (como o Teorema Fundamental da Algebra, por exemplo). Provar o óbvio transmite a falsa impressão de que a Matemática é inútil. Por outro lado, usar argumentos elegantes e convincentes para demonstrar resulta- dos inesperados é uma maneira de exibir sua força e sua beleza. As demons- trações, quando objetivas e bem apresentadas, contribuem para desenvolver o raciocínio, o espírito crítico, a maturidade e ajudam a entender o encadeamento lógico das proposições matemáticas. 3. Ter sempre em mente que, embora a Matemática possa ser cultivada por si mesma, como um todo coerente, de elevado padrão intelectual, formado por conceitos e proposições de natureza abstrata, sua presença no currículo escolar não se deve apenas ao valor dos seus métodos para a formação mental dos jovens. A importância social da Matemática provém de que ela fornece modelos 10 Unidade 1Números Naturais para analisar situações da vida real. Assim, por exemplo, conjuntos são o modelo para disciplinar o raciocínio lógico, números naturais são o modelo para contagem e números reais são o modelo para medida; funções a�ns servem de modelo para situações, como o movimento uniforme, em que os acréscimos da função são proporcionais aos acréscimos da variável independente. E assim por diante. 11 Unidade 1 Textos Complementares Na Sala de Aula Uma recomendação Não se deve dar muita importância à eterna questão de saber se 0 (zero) deve ou não ser incluído entre os números naturais. (Vide �Meu Professor de Ma- temática�, pág. 150.) Praticamente todos os livros de Matemática usados nas escolas brasileiras consideram 0 como o primeiro número natural (consequente- mente 1 é o segundo, 2 é o terceiro, etc). Como se viu acima, não adotamos esse ponto-de-vista. Trata-se, evidentemente, de uma questão de preferência. Deve-se lembrar que o símbolo 0 (sob diferentes formas grá�cas) foi empregado inicialmente pelos maias,posteriormente pelos hindus, difundido pelos árabes e adotado no ocidente, não como um número e sim como um algarismo, com o utilíssimo objetivo de preencher uma casa decimal vazia. (No caso dos maias, a base do sistema de numeração era 20, e não 10.) De resto, a opção do número natural para iniciar a sequência não se limita a escolher entre 0 e 1. Frequente- mente esquecemos que, do mesmo modo que conhecemos e usamos o zero mas começamos os números naturais com 1, a Matemática grega, segundo apre- sentada por Euclides, não considerava 1 como um número. Nos �Elementos�, encontramos as seguintes de�nições: �Unidade é aquilo pelo qual cada objeto é um. Número é uma multitude de unidades�. 12 Unidade 1Números Naturais Para Saber MaisComentários sobre De�nições e axiomas Uma de�nição matemática é uma convenção que consiste usar um nome, ou uma breve sentença, para designar um objeto ou uma propriedade, cuja descrição normalmente exigiria o emprego de uma sentença mais longa. Vejamos algumas de�nições, como exemplo. • Ângulo é a �gura formada por duas semirretas que têm a mesma origem. • Primos entre si são dois ou mais números naturais cujo único divisor comum é a unidade. Mas nem sempre foi assim. Euclides, por exemplo, começa os �Elementos� com uma série de de�nições, das quais selecionamos as seguintes: • Linha é um comprimento sem largura. • Superfície é o que possui comprimento e largura somente. • Quando uma reta corta outra formando ângulos adjacentes iguais, cada um desses ângulos chama-se reto e as retas se dizem perpendiculares. As de�nições de ângulo e de números primos entre si, dadas acima, bem como as de�nições de ângulo reto e retas perpendiculares dadas por Euclides, são corretas. Elas atendem aos padrões atuais de precisão e objetividade. Por outro lado, nas de�nições de linha e superície, Euclides visa apenas oferecer ao seu leitor uma imagem intuitiva desses conceitos. Elas podem servir para ilustrar o pensamento geométrico mas não são utilizáveis nos raciocínios matemáticos porque são formuladas em termos vagos e imprecisos. Na apresentação de uma teoria matemática, toda de�nição faz uso de termos especí�cos, os quais foram de�nidos usando outros termos, e assim sucessiva- mente. Este processo iterativo leva a três possibilidades: a) Continua inde�nidamente, cada de�nição dependendo de outras anteriores, sem nunca chegar ao �m. b) Conduz a uma circularidade, como nos dicionários. (Onde se vê, por exemplo: compreender → perceber, perceber → entender e entender → compreender.) 13 Unidade 1 Textos Complementares c) Termina numa palavra, ou num conjunto de palavras (de preferência dotadas de conotações intuitivas simples) que não são de�nidas, isto é, que são tomadas como representativas de conceitos primitivos. Exemplos: ponto, reta, conjunto. Evidentemente, as alternativas (a) e (b) acima citadas não convêm à Ma- temática. A alternativa (c) é a adotada. Se prestarmos atenção, veremos que foi assim que aprendemos a falar. Numerosas palavras nos foram apresentadas sem de�nição e permanecem até hoje em nosso vocabulário como conceitos primitivos, que aprendemos a usar por imitação e experiência. Para poder empregar os conceitos primitivos adequadamente, é necessário dispor de um conjunto de princípios ou regras que disciplinem sua utilização e estabeleçam suas propriedades. Tais princípios são chamados axiomas ou postulados. Assim como os conceitos primitivos são objetos que não se de�nem, os axiomas são proposições que não se demonstram. Uma vez feita a lista dos conceitos primitivos e enunciados os axiomas de uma teoria matemática, todas as demais noções devem ser de�nidas e as a�rmações seguintes devem ser demonstradas. Nisto consiste o chamado método axiomático. As proposições a serem demonstradas chamam-se teoremas e suas consequências imediatas são denominadas corolários. Uma proposição auxiliar, usada na demonstração de um teorema, é chamada um lema. Ser um axioma ou ser um teorema não é uma característica intrínseca de uma proposição. Dependendo da preferência de quem organiza a apresentação da teoria, uma determinada proposição pode ser adotada como axioma ou então provada como teorema, a partir de outra proposição que a substituiu na lista dos axiomas. A seguir veremos um resumo da teoria matemática dos números naturais, onde os conceitos primitivos são �número natural� e �sucessor� e os axiomas são os de Peano. 14 Unidade 1Números Naturais Para Saber MaisSobre o sistema de numeração Um engenhoso processo, chamado sistema de numeração decimal, permite representar todos os números naturais com o auxílio dos símbolos 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9. Além disso, os primeiros números naturais têm nomes: o sucessor do número um chama se �dois�, o sucessor de dois chama-se �três�, etc. A partir de um certo ponto, esses nomes tornam-se muito complicados, sendo preferível abrir mão deles e designar os grandes números por sua representação decimal. (Na realidade, os números muito grandes não possuem nomes. Por exemplo, como se chamaria o número 101000?). Deve �car claro que o conjunto N = {1, 2, 3, . . .} dos números naturais é uma sequência de objetos abstratos que, em princípio, são vazios de signi�cado. Cada um desses objetos (um número natural) possui apenas um lugar determi- nado nesta sequência. Nenhuma outra propriedade lhe serve de de�nição. Todo número tem um sucessor (único) e, com exceção de 1, tem também um único antecessor (número do qual é sucessor). Vistos desta maneira, podemos dizer que os números naturais são números ordinais: 1 é o primeiro, 2 é o segundo, etc. 15 Unidade 1 Textos Complementares Para Saber Mais Um comentário gramatical Quando dizemos �o número um�, �o número dois� ou �o número três�, as palavras �um�, �dois� e �três� são substantivos, pois são nomes de objetos. Isto contrasta com o uso destas palavras em frases como �um ano, dois meses e três dias�, onde elas aparecem para dar a ideia de número cardinal, isto é, como resultados de contagens. Nesta frase, �um�, �dois� e �três� não são substanti- vos. Pertencem a uma categoria gramatical que, noutras línguas (como francês, inglês e alemão, por exemplo) é chamada adjetivo numeral e que os gramáticos brasileiros e portugueses, há um par de décadas, resolveram chamar de numeral apenas. Este comentário visa salientar a diferença entre os números naturais, olhados como elementos do conjunto N, e o seu emprego como números cardi- nais. Este segundo aspecto será abordado no capítulo seguinte. 16 Unidade 1Números Naturais Para Saber MaisCuidado! O axioma da indução é uma forma sagaz e operacional de dizer que qualquer número natural n pode ser alcançado se partirmos de 1 e repetirmos su�ciente- mente a operação de tomar o sucessor de um número. Ele está presente (pelo menos de forma implícita) sempre que, ao a�rmarmos a veracidade de uma pro- posição referente aos números naturais, veri�camos que ela é verdadeira para n = 1, n = 2, n = 3 e dizemos �e assim por diante...�. Mas é preciso ter cuidado com esta última frase. Ela pressupõe que P (n) ⇒ P (n′) para todo n ∈ N. No �nal deste capítulo, apresentamos como exercícios algumas propo- sições demonstráveis por recorrência, bem como alguns curiosos paradoxos que resultam do uso inadequado do axioma da indução. 17 Unidade 1 Textos Complementares 18 2 1 Números Cardinais Sumário 2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Funções . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.3 A Noção de Número Cardinal . . . . . . . . . . . . 4 2.4 Conjuntos Finitos . . . . . . . . . . . . . . . . . . . 7 2.5 Exercícios Recomendados . . . . . . . . . . . . . . . 10 2.6 Exercícios Suplementares . . . . . . . . . . . . . . . 10 Unidade 2 Introdução 2.1 Introdução A importância dos números naturais provém do fato de que eles constituem o modelo matemático que torna possível o processo de contagem. Noutras palavras,eles respondem a perguntas do tipo: �Quantos elementos tem este conjunto?� Para contar os elementos de um conjunto é necessário usar a noção de cor- respondência biunívoca, ou bijeção. Trata-se de um caso particular do conceito de função, abordado aqui de forma breve, que será desenvolvido com maiores detalhes na Unidade 3 de MA11. 2.2 Funções Definição 1 Dados os conjuntos X, Y , uma função f : X → Y (lê-se �uma função de X em Y �) é uma regra (ou conjunto de instruções) que diz como associar a cada elemento x ∈ X um elemento y = f(x) ∈ Y . O conjunto X chama-se o domínio e Y é o contra-domínio da função f . Para cada x ∈ X, o elemento f(x) ∈ Y chama-se a imagem de x pela função f , ou o valor assumido pela função f no ponto x ∈ X. Escreve-se x 7→ f(x) para indicar que f transforma (ou leva) x em f(x). Exemplos particularmente simples de funções são a função identidade f : X → X, de�nida por f(x) = x para todo x ∈ X e as funções constantes f : X → Y , onde se toma um elemento c ∈ Y e se põe f(x) = c para todo x ∈ X. + Para Saber Mais - Recomendações - Clique para ler Exemplo 1 Sejam X o conjunto dos triângulos do plano Π e R o conjunto dos números reais (que abordaremos logo mais). Se, a cada t ∈ X, �zermos corresponder o número real f(t) = área do triângulo t, obteremos uma função f : X → R. 2 Unidade 2Números Cardinais Exemplo 2Sejam S o conjunto dos segmentos de reta do plano Π e ∆ o conjunto das retas desse mesmo plano. A regra que associa a cada segmento AB ∈ S sua mediatriz g(AB) de�ne uma função g : S → ∆. Exemplo 3A correspondência que associa a cada número natural n seu sucessor n+ 1 de�ne uma função s : N→ N, com s(n) = n + 1. Definição 2Uma função f : X → Y chama-se injetiva quando elementos diferentes em X são transformados por f em elementos diferentes em Y . Ou seja, f é injetiva quando x 6= x′ em X ⇒ f(x) 6= f(x′). Esta condição pode também ser expressa em sua forma contrapositiva: f(x) = f(x′) ⇒ x = x′. Nos três exemplos dados acima, apenas o terceiro é de uma função injetiva. (Dois triângulos diferentes podem ter a mesma área e dois segmentos distintos podem ter a mesma mediatriz mas números naturais diferentes têm sucessores diferentes.) Definição 3Diz-se que uma função f : X → Y é sobrejetiva quando, para qualquer elemento y ∈ Y , pode-se encontrar (pelo menos) um elemento x ∈ X tal que f(x) = y. Nos três exemplos dados acima, apenas o segundo apresenta uma função sobrejetiva. (Toda reta do plano é mediatriz de algum segmento mas apenas os números reais positivos podem ser áreas de triângulos e o número 1 não é sucessor de número natural algum.) Definição 4Chama-se imagem do subconjunto A ⊂ X pela função f : X → Y ao subconjunto f(A) ⊂ Y formado pelos elementos f(x), com x ∈ A. 3 Unidade 2 A Noção de Número Cardinal Portanto, uma função f : X → Y é sobrejetiva quando f(X) = Y . O conjunto f(X), imagem do domínio X pela função f chama-se também a imagem da função f . Nos Exemplos 1, 2 e 3, a imagem da função f é o conjunto dos números reais positivos, a imagem de g é todo o conjunto ∆ e a imagem de s é o conjunto dos números naturais ≥ 2. Dada a função f : X → Y , para saber se um certo elemento b ∈ Y pertence ou não à imagem f(X), escrevemos a �equação� f(x) = b e procuramos achar algum x ∈ X que a satisfaça. Consequentemente, para mostrar que f é sobrejetiva deve-se provar que a equação f(x) = y possui uma solução x ∈ X, seja qual for o y ∈ Y dado. + Para Saber Mais - Recomendação - Clique para ler Exemplo 4 Considere a tentativa de de�nir uma função f : N → N, estipulando que, para todo n ∈ N, o número natural p = f(n) deve ser tal que p2 + 3 = n. O número p = f(n) só pode ser encontrado se n for igual a 4, 7, 12, 19, ... pois nem todos os números naturais são da forma p2 + 3. Assim, esta regra não de�ne uma função com domínio N, porque tem exceções. Exemplo 5 Indiquemos com X o conjunto dos números reais positivos e com Y o conjunto dos triângulos do plano. Para cada x ∈ X, ponhamos f(x) = t caso t seja um triângulo cuja área é x. Esta regra não de�ne uma função f : X → Y porque é ambígua: dado o número x > 0, existe uma in�nidade de triângulos diferentes com área x. 2.3 A Noção de Número Cardinal A conceito de número cadinal se estabelece por meio da noção de bijeção. Definição 5 Uma função f : X → Y chama-se uma bijeção, ou uma correspondência biunívoca entre X e Y quando é ao mesmo tempo injetiva e sobrejetiva. 4 Unidade 2Números Cardinais Exemplo 6Sejam X = {1, 2, 3, 4, 5} e Y = {2, 4, 6, 8, 10}. De�nindo f : X → Y pela regra f(n) = 2n, temos uma correspondência biunívoca, onde f(1) = 2, f(2) = 4, f(3) = 6, f(4) = 8 e f(5) = 10. Exemplo 7Um exemplo particularmente curioso de correspondência biunívoca, que estende o exemplo anterior, foi descoberto pelo físico Galileu Galilei, que viveu há quatrocentos anos. Seja P o conjunto dos números naturais pares: P = {2, 4, 6, . . . , 2n, . . .}. Obtém-se uma correspondência biunívoca f : N→ P pondo-se f(n) = 2n para todo n ∈ N. O interessante deste exemplo é que P é um subconjunto próprio de N. Exemplo 8Sejam Y a base de um triângulo e X um segmento paralelo a Y , unindo os outros dois lados desse triângulo. Seja ainda P o vértice oposto à base Y . Obtém-se uma correspondência biunívoca f : X → Y associando a cada x ∈ X o ponto f(x) onde a semirreta Px intersecta a base Y . 5 Unidade 2 A Noção de Número Cardinal Figura 2.1: Correspondência biunívoca entre dois segmentos Exemplo 9 Neste exemplo, X = C \ {P} é o conjunto obtido retirando da circun- ferência o ponto P e Y é uma reta perpendicular ao diâmetro que não passa por P . De�na a correspondência biunívoca f : X → Y pondo, para cada x ∈ X, f(x) = intersecção da semirreta Px com a reta Y . Figura 2.2: O círculo sem um ponto e a reta Definição 6 Diz-se que dois conjuntos X e Y tem o mesmo número cardinal quando se pode de�nir uma correspondência biunívoca f : X → Y . Cada um dos quatro exemplos acima exibe um par de conjuntos X, Y com o mesmo cardinal. 6 Unidade 2Números Cardinais Exemplo 10Sejam X = {1} e Y = {1, 2}. Evidentemente não pode existir uma correspondência biunívoca f : X → Y , portanto X e Y não têm o mesmo número cardinal. + Para Saber Mais - A palavra �número� no dicionário - Clique para ler 2.4 Conjuntos Finitos Dado n ∈ N, indiquemos com a notação In o conjunto dos números naturais de 1 até n. Assim, I1 = {1}, I2 = {1, 2}, I3 = {1, 2, 3} e, mais geralmente, um número natural k pertence a In se, e somente se, 1 ≤ k ≤ n. Definição 7Seja X um conjunto. Diz-se que X é �nito, e que X tem n elementos quando se pode estabelecer uma correspondência biunívoca f : In → X. O número natural n chama-se então o número cardinal do conjunto X ou, simplesmente, o número de elementos de X. A correspondência f : In → X chama-se uma contagem dos elementos de X. Pondo f(1) = x1, f(2) = x2, . . . , f(n) = xn, podemos escrever X = {x1, x2, . . . , xn}. Para todo n, o conjunto In é �nito e seu número cardinal é n. Assim, todo número natural n é o número cardinal de algum conjunto �nito. A �m de evitar exceções, admite-se ainda incluir o conjunto vazio ∅ entre os conjuntos �nitos e diz-se que ∅ tem zero elementos. Assim, por de�nição, zero é o número cardinal do conjunto vazio. Diz-se que um conjunto X é in�nito quando ele não é �nito. Isto quer dizer que X não é vazio e que, não importa qual seja n ∈ N , não existe correspondência biunívoca f : In → X. No Exemplo 6 acima, temos X = I5 e f : X → Y é uma contagem dos elementos de Y . Assim, Y é um conjunto �nito, com 5 elementos. O conjunto N dos números naturais é in�nito. Com efeito, dada qualquer função f : In → N , não importa qual n se �xou, pomos k = f(1) + f(2) + · · ·+ f(n) e vemos que, para todo x ∈ In, tem-se f(x) < k, logo não existe x ∈ In tal 7 Unidade 2 Conjuntos Finitos que f(x) = k. Assim, é impossível cumprir a condição de sobrejetividade na de�nição de correspondência biunívoca. O número cardinal de um conjunto�nito X, que indicaremos com a notação n(X), goza de algumas propriedades básicas, entre as quais destacaremos as seguintes: 1. O número de elementos de um conjunto �nito é o mesmo, seja qual for a contagem que se adote. Isto signi�ca que se f : Im → X e g : In → X são correspondências biunívocas então m = n. 2. Todo subconjunto Y de um conjunto �nito X é �nito e n(Y ) ≤ n(X). Tem-se n(Y ) = n(X) somente quando Y = X. 3. Se X e Y são �nitos então X ∪Y é �nito e tem-se n(X ∪Y ) = n(X) + n(Y )− n(X ∩ Y ) . 4. Sejam X, Y conjuntos �nitos. Se n(X) > n(Y ), nenhuma função f : X → Y é injetiva e nenhuma função g : Y → X é sobrejetiva. As demonstrações destes fatos se fazem por induçãoo ou por boa-ordenação. (Veja, por exemplo, [Lima]: Curso de Análise, vol. 1, págs. 33-38.) A primeira parte do item 4. acima é conhecida como o princípio das casas de pombos: se há mais pombos do que casas num pombal, qualquer modo de alojar os pombos deverá colocar pelo menos dois deles na mesma casa. As vezes, o mesmo fato é chamado o princípio das gavetas: se m > n, qualquer maneira de distribuir m objetos em n gavetas deverá por ao menos dois desses objetos na mesma gaveta. (Na referência [Lima] citada, este é o Corolário 1 na página 35.) O princípio das casas de pombos, com toda sua simplicidade, possui inte- ressantes aplicações. Vejamos duas delas. Exemplo 11 Tomemos um número natural de 1 a 9. Para �xar as ideias, seja 3 esse número. Vamos provar que todo número natural m possui um múltiplo cuja representação decimal contém apenas os algarismos 3 ou 0. Para isso, conside- remos o conjunto X = {3, 33, . . . , 33 . . . 3}, cujos elementos são os m primeiros números naturais representados somente por algarismos iguais a 3. Se algum dos elementos de X for múltiplo de m, nosso trabalho acabou. Caso contrário, 8 Unidade 2Números Cardinais formamos o conjunto Y = {1, 2, . . . ,m− 1} e de�nimos a função f : X → Y pondo, para cada x ∈ X, f(x) = resto da divisão de x por m. Como X tem mais elementos do que Y , o princípio das casas de pombos assegura que existem elementos x1 < x2 no conjuntoX tais que f(x1) = f(x2). Isto signi�ca que x1 e x2 , quando divididos porm, deixam o mesmo resto. Logo x2−x1 é múltiplo de m. Mas é claro que se x1 tem p algarismos e x2 tem p+q algarismos então a representação decimal de x2 − x1 consiste em q algarismos iguais a 3 seguidos de p algarismos iguais a 0. Exemplo 12Vamos usar o princípio das gavetas para provar que, numa reunião com n pessoas (n ≥ 2), há sempre duas pessoas (pelo menos) que têm o mesmo nú- mero de amigos naquele grupo. Para ver isto, imaginemos n caixas, numeradas com 0, 1, . . . , n − 1. A cada uma das n pessoas entregamos um cartão que pedimos para depositar na caixa correspondente ao número de amigos que ela tem naquele grupo. As caixas de números 0 e n− 1 não podem ambas receber cartões pois se houver alguém que não tem amigos ali, nenhum dos presentes pode ser amigo de todos, e vice-versa. Portanto temos, na realidade, n cartões para serem depositados em n−1 caixas. Pelo princípio das gavetas, pelo menos uma das caixas vai receber dois ou mais cartões. Isto signi�ca que duas ou mais pessoas ali têm o mesmo número de amigos entre os presentes. + Para Saber Mais - Sobre Conjuntos In�nitos - Clique para ler + Para Saber Mais - Fantasia Matemática - Clique para ler + Para Saber Mais - Cuidado! - Clique para ler 9 Unidade 2 Exercícios Recomendados 2.5 Exercícios Recomendados 1. Prove, por indução, que se X é um conjunto �nito com n elementos então existem n! bijeções f : X → X. 2. Prove, por indução, que um conjunto com n elementos possui 2n subcon- juntos. 3. Sejam X e Y dois conjuntos �nitos, com m e n elementos, respectiva- mente. Mostre que existem nm funções f : X → Y . Você seria capaz de resolver diretamente o Exercício 2, utilizando este resultado? 2.6 Exercícios Suplementares 1. De�na uma função sobrejetiva f : N → N tal que, para todo n ∈ N, a equação f(x) = n possui uma in�nidade de raízes x ∈ N. Sugestão: Todo número natural se escreve, de modo único sob a forma 2a · b, onde a, b ∈ N e b é ímpar. 2. Dados n (n > 2) objetos de pesos distintos, prove que é possível deter- minar qual o mais leve e qual o mais pesado fazendo 2n − 3 pesagens em uma balança de pratos. É esse o número mínimo de pesagens que permitem determinar o mais leve e o mais pesado? 3. Prove que, dado um conjunto com n elementos, é possível fazer uma �la com seus subconjuntos de tal modo que cada subconjunto da �la pode ser obtido a partir do anterior pelo acréscimo ou pela supressão de um único elemento. 4. Todos os quartos do Hotel Georg Cantor estão ocupados, quando chegam os trens T1, T2, . . . , (em quantidade in�nita), cada um deles com in�nitos passageiros. Que deve fazer o gerente para hospedar todos? 10 Referências Bibliográ�cas [Lima] Lima, Elon Lages. Curso de Análise, Vol. 1. Projeto Euclides, IMPA, Rio de Janeiro, 1976. 8, 15 11 Unidade 2 Textos Complementares 2.7 Textos Complementares Para Saber Mais Recomendações 1. É importante ressaltar que f(x) é a imagem do elemento x ∈ X pela função f , ou o valor da função f no ponto x ∈ X. Os livros antigos, bem como alguns atuais, principalmente os de Cálculo, costumam dizer �a função f(x)� quando deveriam dizer �a função f �. Algumas vezes essa linguagem inexata torna a comunicação mais rápida e �ca difícil resistir à tentação de usá-la. Mas é indispensável a cada momento ter a noção precisa do que se está fazendo. Na prática, há algumas funções com as quais é simples e natural lidar usando a terminologia correta. Por exemplo, é fácil acostumar-se a escrever as funções sen : R → R e log : R+ → R, guardando as notações senx e log x para os números reais que são os valores destas funções num dado ponto x. Por outro lado, quando se trata de uma função polinomial, o bom-senso nos leva a dizer �a função x2 − 5x + 6� em vez da forma mais correta e mais pedante �a função p : R→ R tal que p(x) = x2 − 5x + 6 para todo x ∈ R� . Caso análogo se dá com a função exponencial ex, embora recentemente se tenha tornado cada vez mais frequente escrever exp(x) = ex e assim poder falar da função exp : R→ R. 2. Deve-se ainda recordar que uma função consta de três ingredientes: domínio, contra-domínio e a lei de correspondência x 7→ f(x). Mesmo quando dizemos simplesmente �a função f �, �cam subentendidos seu domínio X e seu contra- domínio Y . Sem que eles sejam especi�cados, não existe a função. Assim sendo, uma pergunta do tipo �Qual é o domínio da função f(x) = 1/x� ?, estritamente falando, não faz sentido. A pergunta correta seria: �Qual é o maior subconjunto X ⊂ R tal que a fórmula f(x) = 1/x de�ne uma função f : X → R ?� Novamente, a pergunta incorreta é mais simples de formular. Se for feita assim, é preciso saber seu signi�cado. Segue-se do que foi dito acima que as funções f : X → Y e g : X ′ → Y ′ são iguais se, e somente se, X = X ′, Y = Y ′ e f(x) = g(x) para todo x ∈ X. 12 Unidade 2REFERÊNCIAS BIBLIOGRÁFICAS Para Saber MaisRecomendação 3. Em muitos exemplos de funções f : X → Y , principalmente na Matemática Elementar, X e Y são conjuntos numéricos e a regra x 7→ f(x) exprime o valor f(x) por meio de uma fórmula que envolve x. Mas em geral não precisa ser assim. A natureza da regra que ensina como obter f(x) quando é dado x é inteiramente arbitrária, sendo sujeita apenas a duas condições: a) Não deve haver exceções: a �m de que a função f tenha o conjunto X como domínio, a regra deve fornecer f(x), seja qual for x ∈ X dado. b) Não pode haver ambiguidades: a cada x ∈ X, a regra deve fazer corres- ponder um único f(x) em Y . Os exemplos a seguir ilustram essas exigências. 13 Unidade 2 Textos Complementares Para Saber Mais A palavra �número� no dicionário As vezes se diz que os conjuntos X e Y são (numericamente) equivalentes quando é possível estabelecer uma correspondência biunívoca f : X → Y , ou seja, quando X e Y têm o mesmo númerocardinal. Isto explica (embora não justi�que) a de�nição dada no dicionário mais vendido do país. Em algumas situações, ocorrem em Matemática de�nições do tipo seguinte: um vetor é o conjunto de todos os segmentos de reta do plano que são equipolentes a um segmento dado. (De�nição �por abstração�.) Nessa mesma veia, poder-se-ia tentar dizer: �número cardinal de um conjunto é o conjunto de todos os conjuntos equivalentes a esse conjunto.� No caso do dicionário, há um conjunto de defeitos naquela de�nição, com um número cardinal razoavelmente elevado. Os três mais graves são: 1. Um dicionário não é um compêndio de Matemática, e muito menos de Ló- gica. Deve conter explicações acessíveis ao leigo (de preferência, corretas). As primeiras acepções da palavra �número� num dicionário deveriam ser �quanti- dade� e �resultado de uma contagem ou de uma medida�. 2. A de�nição em causa só se aplica a números cardinais, mas a ideia de número deveria abranger os racionais e, pelo menos, os reais. 3. O �conjunto de todos os conjuntos equivalentes a um conjunto dado� é um conceito matematicamente incorreto. A noção de conjunto não pode ser usada indiscriminadamente, sem submeter-se a regras determinadas, sob pena de con- duzir a paradoxos, ou contradições. Uma dessas regras proíbe que se forme conjuntos a não ser que seus elementos pertençam a, ou sejam subconjuntos de, um determinado conjunto-universo. Um exemplo de paradoxo que resulta da desatenção a essa regra é �o conjunto X de todos os conjuntos que não são elementos de si mesmos.� Pergunta-se: X é ou não é um elemento de si mesmo? Qualquer que seja a resposta, chega-se a uma contradição. 14 Unidade 2REFERÊNCIAS BIBLIOGRÁFICAS Para Saber MaisSobre Conjuntos In�nitos Para encerrar estas considerações a respeito de números cardinais, faremos alguns comentários sobre conjuntos in�nitos. Em primeiro lugar, convém esclarecer que a maior contribuição de Cantor não foi a adoção da linguagem e da notação dos conjuntos e sim suas desco- bertas sobre os números cardinais de conjuntos in�nitos. Ele foi o primeiro a descobrir que existem conjuntos in�nitos com diferentes cardinalidades ao pro- var que não pode haver uma correspondência biunívoca entre N e o conjunto R dos números reais e que nenhum conjunto X pode estar em correspondência biunívoca com o conjunto P(X) cujos elementos são os subconjuntos de X. Além disso, ele mostrou que a reta, o plano e o espaço tri-dimensional (ou mesmo espaços com dimensão superior a três) têm o mesmo número cardinal. Estes fatos, que atualmente são considerados corriqueiros entre os matemáticos, causaram forte impacto na época (meados do século dezenove). A segunda observação diz respeito a funções f : X → X de um conjunto em si mesmo. Quando X é �nito, f é injetiva se, e somente se, é sobrejetiva (veja a referência [Lima].) Mas isto não é verdadeiro para X in�nito. Por exemplo, se de�nirmos a função f : N → N pondo, para cada n ∈ N, f(n) = número de fatores primos distintos que ocorrem na decomposição de n, veremos que f é sobrejetiva mas não é injetiva. (Para cada b ∈ N existe uma in�nidade de números n tais que f(n) = b.) Além disso, as funções f : N→ N, g : N→ N, h : N→ N e ϕ : N→ N, de�nidas por f(n) = n + 1, g(n) = n + 30, h(n) = 2n e ϕ(n) = 3n (2.1) são injetivas mas não são sobrejetivas. Estas quatro funções são protagonistas da historinha seguinte que fecha a unidade. 15 Unidade 2 Textos Complementares Para Saber Mais Fantasia Matemática O Grande Hotel Georg Cantor tinha uma in�nidade de quartos, numera- dos consecutivamente, um para cada número natural. Todos eram igualmente confortáveis. Num �m-de-semana prolongado, o hotel estava com seus quartos todos ocupados, quando chega um viajante. A recepcionista vai logo dizendo: � Sinto muito, mas não há vagas. Ouvindo isto, o gerente interveio: � Podemos abrigar o cavalheiro, sim senhora. E ordena: � Trans�ra o hóspede do quarto 1 para o quarto 2, passe o do quarto 2 para o quarto 3 e assim em diante. Quem estiver no quarto n, mude para o quarto n + 1. Isto manterá todos alojados e deixará disponível o quarto 1 para o recém-chegado. Logo depois chegou um ônibus com 30 passageiros, todos querendo hospe- dagem. A recepcionista, tendo aprendido a lição, removeu o hóspede de cada quarto n para o quarto n+ 30 e acolheu assim todos os passageiros do ônibus. Mas �cou sem saber o que fazer quando, horas depois, chegou um trem com uma in�nidade de passageiros. Desesperada, apelou para o gerente que pron- tamente resolveu o problema dizendo: � Passe cada hóspede do quarto n para o quarto 2n. Isto deixará vagos todos os apartamentos de número ímpar, nos quais poremos os novos hóspedes. � Pensando melhor: mude quem está no quarto n para o quarto 3n. Os novos hóspedes, ponha-os nos quartos de número 3n+2. Deixaremos vagos os quartos de número 3n + 1. Assim, sobrarão ainda in�nitos quartos vazios e eu poderei ter sossego por algum tempo. 16 Unidade 2REFERÊNCIAS BIBLIOGRÁFICAS Para Saber MaisCuidado! Não confunda conjunto in�nito com aquele que tem um número muito grande (porém �nito) de elementos. Quando, na linguagem comum, se diz algo como �- Já ouvi isto uma in�nidade de vezes�, trata-se de uma mera força de expressão. Não há distâncias in�nitas (mesmo entre duas galáxias bem afastadas) e até o número de átomos do universo é �nito. (O físico Arthur Eddington estimou o número de prótons do universo em 136 × 2256. O número de átomos é certamente menor pois todo átomo contém ao menos um próton.) E importante ter sempre em mente que nenhum número natural n é maior do que todos os demais: tem-se sempre n < n + 1. 17 Unidade 2 Textos Complementares 18 3 1 O Princípio de Indução Matemática Sumário 3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 2 3.2 O Poder do Método de Indução . . . . . . . . . . . 2 3.3 Exercícios Recomendados . . . . . . . . . . . . . . . 12 3.4 Exercícios Suplementares . . . . . . . . . . . . . . . 13 3.5 Textos Complementares . . . . . . . . . . . . . . . . 14 Unidade 3 Introdução 3.1 Introdução Nesta unidade e na próxima, mostraremos como utilizar o Axioma de Indução para de�nir com rigor objetos matemáticos e também como utilizá-lo como poderoso instrumento para demonstrar os mais variados resultados envolvendo números naturais. Algumas das noções introduzidas nesta e na próxima unidade serão retomadas de modo mais sistemático nas Unidades 5 a 8. 3.2 O Poder do Método de Indução Comecemos com a pergunta: O que signi�cam expressões do tipo 1 + 2 + · · ·+ n e 1 · 2 · · · · n? Note que as operações de adição e de multiplicação nos números naturais (ou em qualquer sistema numérico) são binárias, isto é, elas relacionam dois elementos de cada vez. Apesar disso, temos uma ideia bastante intuitiva do signi�cado das expressões acima, até mesmo no que diz respeito aos pontinhos que nelas aparecem. Existe, contudo, um modo de tornar mais rigorosas de�nições desse tipo por meio do Princípio de Indução Matemática, como veremos mais adiante. Antes, porém, recordemos este princípio que demonstramos na Unidade 1. Princípio de Indução Matemática Se P (n) é uma propriedade relativa ao número natural n, tal que i) P (1) é válida; ii) Para todo n ∈ N, a validez de P (n) implica a validez de P (n+ 1). Então P (n) é válida qualquer que seja o número natural n. + Para Saber Mais - Comentário - Clique para ler + Para Saber Mais - Indução Empírica vs Indução Matemática - Cli- que para ler 2 Unidade 3O Princípio de Indução Matemática Para de�nir uma expressão En, para todo número natural n, basta de�nirmos E1 e mostrar, para todo n ∈ N, como obter sem ambiguidade En+1 a partir de En. Nesse caso, dizemos que En foi de�nido por recorrência. Vejamos como intervém o Princípio de Indução Matemática para justi�car este tipo de de�nição. Seja X o subconjunto de N, determinado pela condição: n ∈ X ⇐⇒ En está de�nido. Pela caracterização do conjuntoX, temos que 1 ∈ X e, para todo n ∈ N, n ∈ X ⇒ n+ 1 ∈ X. Portanto, X = N. De�nições por recorrência podem ser utilizadas para dar um signi�cado a expressões como no início da unidade. Exemplo 1De�nimos S1 = 1. Em seguida, supondo Sn de�nido, pomos Sn+1 = Sn + (n+ 1). Damos assim, um sentido matemático preciso à expressão: Sn = 1 + 2 + · · ·+ n. Por outro lado, de�nindo 1! = 1 e pondo (n+1)! = n!(n+1), supondo que n! esteja de�nido, damos também, neste caso, um sentido matemático para a expressão: n! = 1 · 2 · · ·n. Para generalizar os exemplos acima, vamos introduzir a noção de sequência. Teremos oportunidade de comprovar, ao longo do curso, o quanto é central este conceito. Definição 1Uma sequência de elementos de um conjunto A é uma função x : N→ A. 3 Unidade 3 O Poder do Método de Indução Tendo em vista que uma função conhecida quando se sabe qual é a ima- gem de todo elemento de seu domínio, uma sequência x : N → A pode ser representada como x(1), x(2), . . . , x(n), . . . , ou ainda, denotando x(n) por xn, podemos representá-la concisamente por (xn). Por motivo de economia, quando dissermos que um conjunto A possui uma adição ou uma multiplicação satisfazendo às leis básicas da aritmética, esta- remos supondo que em A estão de�nidas duas operações com propriedades semelhantes às correspondentes operações nos naturais. Seja agora (xn) uma sequência de elementos de um conjunto A que possui duas operações, de adição e de multiplicação, satisfazendo às leis básicas da aritmética. Definição 2 De�nem-se Sn e Pn em A, como se segue: S1 = P1 = x1 e Sn+1 = Sn + xn+1 e Pn+1 = Pn · xn+1. Isto dá sentido às seguintes expressões: Sn = x1 + x2 + · · ·+ xn e Pn = x1 · x2 · · · xn. Somas e produtos, como acima, serão também escritos com as notações de somatórios e produtórios: Sn = n∑ i=1 xi e Pn = n∏ i=1 xi, que se leem como �somatório quando i varia de 1 até n de xi� e �produto quando i varia de 1 até n de xi�, respectivamente. Note que a partir de uma sequência dada (xn), pudemos de�nir de modo natural duas outras sequências, a saber: (Sn) e (Pn). Dada uma sequência constante, x(n) = a, para todo n ∈ N, onde a ∈ A, os termos da sequência Pn a ela associada são por de�nição as potências de a. Pela sua importância, destacamos essa de�nição a seguir. 4 Unidade 3O Princípio de Indução Matemática Definição 3Seja a um elemento de um conjunto A munido de uma multiplicação sujeita às leis básicas da aritmética. As potências an de a, com n ∈ N, são de�nidas por recorrência como segue: a1 = a e an+1 = an · a. Quando a 6= 0, convenciona-se de�nir a0 = 1. Isto será especialmente con- veniente quando estendermos as potências para expoentes não necessariamente números naturais. Isto se tornará bem mais claro na Unidade 13 de MA11. Exemplo 2Neste exemplo, queremos determinar uma fórmula para a soma dos n pri- meiros números naturais: Sn = 1 + 2 + · · ·+ n. Conta-se a seguinte história sobre o matemático alemão Carl Friedrich Gauss (1777-1855), considerado um dos maiores gênios da matemática de todos os tempos, quando ainda garoto. Na escola, o professor, para aquietar a turma de Gauss, mandou os alunos calcularem a soma de todos os números naturais de 1 a 100. Qual não foi a sua surpresa quando, instantes depois, o menino deu a resposta: 5050. Indagado sobre como tinha descoberto tão rapidamente o resultado, Gauss, então, descreveu o método a seguir. Sendo Sn = 1 + 2 + · · ·+ n, o objetivo é encontrar uma fórmula fechada1 para Sn. Somando a igualdade acima, membro a membro, com ela mesma, porém com as parcelas do segundo membro em ordem invertida, temos que Sn = 1 + 2 + · · · + n Sn = n + (n− 1) + · · · + 1 2Sn = (n+ 1) + (n+ 1) + · · · + (n+ 1) Daí segue-se que 2Sn = n(n+ 1) e, portanto, Sn = n(n+ 1) 2 . 1Uma fórmula fechada para Sn, a grosso modo, é uma função de n que permite calcular diretamente os valores de Sn fazendo um pequeno número de cálculos. 5 Unidade 3 O Poder do Método de Indução Vamos ser críticos com relação à prova acima. Para a maioria das pessoas, essa prova parece impecável, mas se alguém nos perguntasse o que está escon- dido atrás dos pontinhos, talvez nos sentíssemos embaraçados. Também, como ter absoluta certeza de que nada acontece fora do nosso controle, exatamente na imensa região coberta pelos pontinhos? Para não pairar nenhuma dúvida sobre o nosso resultado, vamos provar a fórmula utilizando o Princípio de Indução Matemática. Considere a sentença sobre os naturais: P (n) : 1 + 2 + · · ·+ n = n(n+ 1) 2 . (3.1) Note que P (1) : 1 = 1(1 + 1) 2 é verdadeira. Observe também que P (n+ 1): 1 + 2 + · · ·+ n+ (n+ 1) = (n+ 1)(n+ 2) 2 . Agora, suponhamos que para algum n ∈ N, tenhamos P (n) verdadeira, isto é, a fórmula (1.1) é válida para tal valor de n. Somando n+1 a ambos os lados dessa igualdade, temos que é verdadeira a igualdade 1 + 2 + · · ·+ n+ (n+ 1) = n(n+ 1) 2 + n+ 1 = n(n+ 1) + 2(n+ 1) 2 = (n+ 1)(n+ 2) 2 , o que estabelece a veracidade de P (n+ 1). Pelo Princípio de Indução, tem-se que a fórmula P (n) é verdadeira para todo n ∈ N. + Na Sala de Aula - Considerações sobre o Rigor - Clique para ler Exemplo 3 Queremos validar a fórmula P (n) : 12 + 22 + · · ·+ n2 = n(n+ 1)(2n+ 1) 6 . (3.2) 6 Unidade 3O Princípio de Indução Matemática Note que P (1) : 12 = 1(1 + 1)(2 + 1) 6 é verdadeira. Suponha que, para algum n ∈ N, se tenha que P (n) é verdadeira, isto é, (1.2) é válida. Somando (n + 1)2 a ambos os lados da igualdade (1.2), temos que 12 + 22 + · · ·+ n2 + (n+ 1)2 = n(n+ 1)(2n+ 1) 6 + (n+ 1)2 = n(n+ 1)(2n+ 1) + 6(n+ 1)2 6 = (n+ 1)[n(2n+ 1) + 6(n+ 1)] 6 = (n+ 1)[(n+ 1) + 1][2(n+ 1) + 1] 6 , estabelecendo assim a veracidade de P (n+ 1). Portanto, a fórmula é válida para todo n ∈ N. Exemplo 4Vamos provar que é verdadeira, para todo n ∈ N, a fórmula: P (n) : 1 1.2 + 1 2.3 + · · ·+ 1 n(n+ 1) = n n+ 1 . (3.3) Observemos inicialmente que P (1) : 1 1.2 = 1 1 + 1 é verdadeira. Suponhamos que, para algum n, tem-se que P (n) é verdadeira, ou seja, que a fórmula (1.3) seja verdadeira para esse valor de n. Somando a ambos os lados dessa igualdade 1 (n+ 1)(n+ 2) , temos que 1 1.2 + 1 2.3 + · · ·+ 1 n(n+ 1) + 1 (n+ 1)(n+ 2) = n n+ 1 + 1 (n+ 1)(n+ 2) = n+ 1 n+ 2 , mostrando, assim, que P (n+ 1) é verdadeira. 7 Unidade 3 O Poder do Método de Indução Portanto, pelo Princípio de Indução Matemática, temos que a fórmula vale para todo n ∈ N. A seguir, vamos estabelecer, por meio de indução, as propriedades usuais das potências. Proposição 4 Sejam a, b ∈ A e m,n ∈ N. Então, i) am · an = an+m. ii) (am)n = amn. iii) (a · b)n = an · bn. Demonstração Provaremos (i), deixando o restante como exercício. Fixemos a ∈ A e m ∈ N, arbitrariamente. Demonstremos a propriedade por indução sobre n. Para n = 1, a propriedade é válida, pois, pelas de�nições, am · a1 = am · a = am+1. Por outro lado, supondo que am · an = am+n, temos que am · an+1 = am · (an · a) = (am · an) · a = am+n · a = am+n+1. Isso, pelo Princípio de Indução Matemática, prova a nossa propriedade. Exemplo 5 Utilizando a noção de potência e de suas propriedades, mostraremos que 3 divide 5n + 2 · 11n nos inteiros, para todo n ∈ N. De fato, para n = 1, temos que 3 divide 51 + 2 · 111 = 27. Suponha, agora, que, para algum n ≥ 1, saibamos que 3 divide 5n+2 ·11n. Logo, existe um número inteiro a tal que 5n + 2 · 11n = 3a. Mutiplicando por 5 ambos os lados da igualdade acima, temos 5 · 3a = 5n+1 + 5 · 2 · 11n = 5n+1 + 2 · 11 · 11n − 12 · 11n. 8 Unidade 3O Princípio de Indução Matemática Daí segue-se a igualdade 5n+1 + 2 · 11n+1 = 5 · 3a+ 12 · 11n, cujo segundo membro é divisível por 3, por ser igual a 3(5a+ 4 · 11n). Assim, provamos que 3 divide 5n+1 + 2 · 11n+1, o que, pelo Princípio de Indução Matemática, acarreta que 3 divide 5n + 2 · 11n, para todo número natural n. Pode ocorrer que uma determinada propriedade seja válida para todos os números naturais a partir de umdeterminado valor a, mas não necessariamente para valores menores. Como proceder nesses casos? Por exemplo, como provar que a desigualdade 2n > n2 é verdadeira para todo valor de n natural maior ou igual do que 5? Fazemos isso baseados na seguinte pequena generalização do Princípio de Indução Matemática: Teorema 1Seja P (n) uma sentença sobre N, e seja a ∈ N. Suponha que: (i) P (a) é verdadeira, e (ii) qualquer que seja n ∈ N, com n ≥ a, sempre que P (n) é verdadeira, segue-se que P (n+ 1) é verdadeira. Então, P (n) é verdadeira para todo número natural n ≥ a. DemonstraçãoDe�na o conjunto S = {m ∈ N; P (m+ a− 1) }. Por (i) temos que 1 ∈ S. Por outro lado, se m ∈ S, temos que P (m + a − 1) é verdadeira. Logo, por (ii), P (m + 1 + a − 1) é verdadeira. Portanto, m+ 1 ∈ S. Em vista do Princípio de Indução Matemática, temos que S = N. Consequentemente, P (n) é verdadeira para todo n ≥ a. Exemplo 6Vamos mostrar que a desigualdade na sentença P (n) : 2 n > n2 é verdadeira, para todo número natural n ≥ 5. 9 Unidade 3 O Poder do Método de Indução Note que P (1) : 21 > 12 é verdadeira, P (2) : 22 > 22 é falsa, P (3) : 23 > 32 é falsa e P (4) : 24 > 42 é falsa. Tudo isso não importa, pois queremos veri�car a veracidade dessa desigualdade para n ≥ 5. De fato, temos que P (5) : 25 > 52 é verdadeira. Seja n ≥ 5 tal que 2n > n2. Multiplicando ambos os lados da desigualdade acima por 2, obtemos 2n+1 > 2n2. Note que 2n2 > (n + 1)2, se n ≥ 3, pois tal desigualdade é equivalente a n(n − 2) > 1. Daí, deduzimos que 2n+1 > (n + 1)2, o que signi�ca que P (n + 1) é verdadeira, estabelecendo o resultado em vista do Teorema 1. Exemplo 7 Um banco tem um suprimento ilimitado de notas de 3 e de 5 (unidades de moeda). Mostre que ele pode pagar qualquer quantia (de unidades de moeda) maior do que 7. Para isto, basta mostrar que a sentença: P (n) : A equação 3x+ 5y = n tem solução em (N ∪ {0})× (N ∪ {0}), é verdadeira para todo n ≥ 8. De fato, ela é verdadeira para n = 8, pois a equação 3x+ 5y = 8 admite a solução (x, y) = (1, 1). Suponha agora que a equação 3x + 5y = n tenha uma solução (a, b) para algum n ≥ 8; isto é, 3a + 5b = n. Note que, para qualquer solução (a, b), devemos ter a ≥ 1 ou b ≥ 1. Se b ≥ 1, observando que 3× 2− 5× 1 = 1, segue que 3(a+ 2) + 5(b− 1) = 3a+ 5b+ 3× 2− 5× 1 = 3a+ 5b+ 1 = n+ 1, o que mostra que a equação 3x + 5y = n + 1 admite a solução (a + 2, b− 1) em (N ∪ {0})× (N ∪ {0}). Se, por acaso, b = 0, então, a ≥ 3; usando a igualdade −3× 3+5× 2 = 1, temos 3(a− 3) + 5× 2 = 3a− 3× 3 + 5× 2 = 3a+ 5b+ 1 = n+ 1, o que mostra que a equação 3x + 5y = n + 1 admite a solução (a− 3, b + 2) em (N ∪ {0})× (N ∪ {0}). 10 Unidade 3O Princípio de Indução Matemática Mostramos assim, que, em qualquer caso, a equação 3x+5y = n+1 admite solução, sempre que a equação 3x+5y = n, para algum n ≥ 8, tenha solução. Como o resultado vale para n = 8, segue a conclusão desejada pelo Teorema 1. Note que n0 = 8 é o menor valor de n para o qual a equação tem solução para todo n ≥ n0. 11 Unidade 3 Exercícios Recomendados 3.3 Exercícios Recomendados 1. Mostre, por indução, a validez das seguintes fórmulas: (a) 1.20 + 2.21 + 3.22 + · · ·+ n.2n−1 = 1 + (n− 1)2n; (b) ( 1 + 1 1 )( 1 + 1 2 )2 · · · ( 1 + 1 n− 1 )n−1 = nn−1 (n− 1)! , (c) 1.1! + 2.2! + 3.3! + · · ·+ n.n! = (n+ 1)!− 1. 2. Sejam a e b números reais distintos. Mostre que, para todo n ∈ N, vale a igualdade: bn + abn−1 + a2bn−2 + · · ·+ an−1b+ an = b n+1 − an+1 b− a . 3. Se senα 6= 0, mostre que, para todo n ∈ N, vale a igualdade: cosα · cos 2α · cos 22α · · · cos 2nα = sen 2 n+1α 2n+1 senα . Sugestão: Use a fórmula sen 2β = 2 sen β cos β. 4. Para todo n ∈ N, mostre que, nos inteiros, (a) 80 divide 34n − 1; (b) 9 divide 4n + 6n− 1; (c) 8 divide 32n + 7; (d) 9 divide n4n+1 − (n+ 1)4n + 1. 5. Mostre que (a) n! > 2n, se n ≥ 4; (b) n! > 3n,se n ≥ 7; (c) n! > 4n, se n ≥ 9. 6. Prove que, para todo n natural, vale a desigualdade: 1 2 · 3 4 · 5 6 · · · 2n− 1 2n ≤ 1√ 3n+ 1 . 12 Unidade 3O Princípio de Indução Matemática 7. Mostre que o número de diagonais de um polígono convexo de n lados é dado por dn = n(n− 3) 2 . 3.4 Exercícios Suplementares 1. Mostre que n0 = 32 é o menor valor para o qual a equação 5x+ 9y = n possui solução em (N ∪ {0})2 para todo n ≥ n0. 2. Prove que, para qualquer número natural n: a) n3 + (n+ 1)3 + (n+ 2)3 é divisível por 9; b) 32n+2 + 8n− 9 é divisível por 16; c) 4n + 15n− 1 é divisível por 9; d) 11n+2 + 122n+1 é divisível por 133; e) 23 n + 1 é divisível por 3n+1. 3. Prove que: a) 2n > n, onde n é um número natural arbitrário; b) 1 · 3 · 5 · · · (2n− 1) 2 · 4 · 6 · · · 2n ≤ 1√ 2n+ 1 , para qualquer n ∈ N; c) 1 n+ 1 + 1 n+ 2 + · · ·+ 1 2n > 13 24 , se n ∈ N e n ≥ 2.; d) 2n > 1 + n √ 2n−1, se n ∈ N e n ≥ 2. 4. Suponha que x+ 1 x seja um número natural. Prove que xn+ 1 xn é também um número natural, qualquer que seja o número natural n. 5. Mostre que o número 111 . . . 1 (formado por 3n algarismos iguais a 1) é divisível por 3n. Sugestão: Para o passo indutivo, divida o número escrito com 3n+1 algarismos iguais a 1 pelo número formado por 3n algarismos iguais a 1 e veri�que que o resultado é um número divisível por 3. 13 Unidade 3 Textos Complementares 3.5 Textos Complementares Para Saber Mais Comentário Note que, na argumentação acima, poderia parecer que estamos usando o fato de P (n) ser verdadeira para deduzir que P (n + 1) é verdadeira para em seguida concluir que P (n) é verdadeira. O que está ocorrendo? Estamos usando a tese para provar o resultado? A resposta é não! Preste bem atenção, pois essa é a parte mais delicada de toda a trama. Dado um número natural n, temos duas possibilidades: (a) P (n) é verdadeira, ou (b) P (n) é falsa. A hipótese (ii) do Princípio não exige em absoluto que assumamos P (n) verdadeira para todo n ∈ N, podendo eventualmente ser falsa para algum valor de n, ou mesmo para todos os valores de n. O que a hipótese (ii) exige é que sempre que algum n pertença à categoria (a), acima, então n+1 também pertença a essa mesma categoria; não exigindo nada quando n pertencer à categoria (b). Por exemplo, a sentença P (n) : n = n+1 satisfaz (por vacuidade) a hipótese (ii) do Princípio, já que nenhum n ∈ N pertence à categoria (a). O que falha para que o Princípio de Indução nos garanta que P (n) é verdadeira para todo n é que a hipótese (i) não é veri�cada, pois P (1) : 1 = 2 é falsa! 14 Unidade 3O Princípio de Indução Matemática Para Saber MaisIndução Empírica vs Indução Matemática É preciso ter clareza que a Indução Matemática é diferente da indução empírica das ciências naturais, em que é comum, após um certo número de experimentos, necessariamente �nito, enunciar leis gerais que governam o fenô- meno em estudo. Essas leis são tidas como verdades, até prova em contrário. Na matemática, não há lugar para a�rmações �verdadeiras até prova em con- trário�. A Prova por Indução Matemática trata de estabelecer que determinada sentença sobre os naturais é sempre verdadeira. A indução empírica foi batizada, de modo irônico, pelo matemático, �lósofo e grande humanista inglês do século passado, Bertrand Russel (1872-1970), de indução galinácea, com base no seguinte conto: Havia uma galinha nova no quintal de uma velha senhora. Diariamente, ao entardecer, a boa senhora levava milho às galinhas. No primeiro dia, a galinha, descon�ada, esperou que a senhora se retirasse para se alimentar. No segundo dia, a galinha, prudentemente, foi se alimentando enquanto a senhora se retirava. No nonagésimo dia, a galinha, cheia de intimidade, já não fazia caso da velha senhora. No centésimo dia, ao se aproximar a senhora, a galinha, por indução, foi ao encontro dela para reclamar o seu milho. Qual não foi a sua surpresa quando a senhora pegou-a pelo pescoço com a intenção de pô-la na panela. 15 Unidade 3 Textos Complementares Na Sala de Aula Considerações sobre o Rigor Neste curso, o nosso objetivoé mostrar como se pode estabelecer um maior padrão de rigor no tratamento de problemas matemáticos que ocorrem no En- sino Médio, mas isso não deve ser tomado ao pé da letra na sua prática docente. Certos argumentos informais, quando acompanhados de um raciocínio correto, são corriqueiramente aceitos. Por exemplo, o argumento utilizado por Gauss para somar os n primeiros números naturais é perfeitamente aceitável. Por- tanto, um conselho: use o formalismo para ajudar e não para atrapalhar e nunca o deixe se sobrepor à criatividade, pois, via de regra, primeiro vem a descoberta para depois vir a formalização. Procure estimular sempre os seus alunos a serem criativos. Num primeiro momento, deixe as ideias �uirem, só depois preocupe-se com a sua organização e formalização. 16 4 1 Aplicações do Princípio de Indução Matemática Sumário 4.1 Exercícios Recomendados . . . . . . . . . . . . . . . 9 4.2 Exercícios Suplementares . . . . . . . . . . . . . . . 9 4.3 Textos Complementares . . . . . . . . . . . . . . . . 11 Unidade 4 Apresentaremos nesta unidade algumas aplicações lúdicas do Princípio de Indução Matemática ao mundo material. Exemplo 1 [A Torre de Hanói] Você provavelmente já conhece esse jogo bastante popular e que pode ser facilmente fabricado ou ainda encontrado em lojas de brinquedos de madeira. O jogo é formado por n discos de diâmetros distintos com um furo no seu centro e uma base onde estão fincadas três hastes. Numa das hastes, estão enfiados os discos, de modo que nenhum disco esteja sobre um outro de diâmetro menor (veja figura abaixo). �� ���� ���� ���� �� �� �� Figura 1 O jogo consiste em transferir a pilha de discos para uma outra haste, deslo- cando um disco de cada vez, de modo que, a cada passo, a regra acima seja observada. As perguntas naturais que surgem são as seguintes: 1. O jogo tem solução para cada n ∈ N? 2. Em caso afirmativo, qual é o número mínimo jn de movimentos para resolver o problema com n discos? Usando Indução Matemática, vamos ver que a resposta à primeira pergunta é afirmativa, qualquer que seja o valor de n. Em seguida, deduziremos uma fórmula que nos fornecerá o número jn. Considere a sentença P (n) : O jogo com n discos tem solução. 2 Unidade 4Aplicações do Princípio de Indução Matemática Obviamente, P (1) é verdade. Suponha que P (n) seja verdadeiro, para algum n; ou seja, que o jogo com n discos tem solução. Vamos provar que o jogo com n+ 1 discos tem solução. Para ver isso, resolva inicialmente o problema para os n discos superiores da pilha, transferindo-os para uma das hastes livre (isso é possível, pois estamos admitindo que o problema com n discos possua solução): �� �� �� ���� ���� ���� �� �� �� Figura 2 Em seguida, transfira o disco que restou na pilha original (o maior dos discos) para a haste vazia: �� �� �� ���� ���� ���� �� �� �� Figura 3 Feito isto, resolva novamente o problema para os n discos que estão juntos, transferindo-os para a haste que contém o maior dos discos: �� ���� ���� ���� �� �� ���� �� Figura 4 Isso mostra que o problema com n + 1 discos também possui solução, e, portanto, por Indução Matemática, que P (n) é verdadeira para todo n ∈ N. 3 Unidade 4 Para determinar uma fórmula para jn, veja que, para resolver o problema para n + 1 discos com o menor número de passos, temos, necessariamente, que passar duas vezes pela solução mínima do problema com n discos. Temos, então, que jn+1 = 2jn + 1. Obtemos, assim, uma sequência (jn) definida recorrentemente. Pode-se mostrar, sem dificuldade, por indução, que seu termo geral é dado por jn = 2 n − 1. (Este tipo de sequências, as recorrências, será estudado de modo sistemático nas Unidades U7 e U8.) + Para Saber Mais - Origem da Torre de Hanói - Clique para ler Exemplo 2 [Os Coelhos de Fibonacci] Trata-se do seguinte problema proposto e resolvido pelo matemático italiano Leonardo de Pisa em seu livro Liber Abacci, de 1202: Quot paria coniculorum in uno anno ex uno pario germinentur. Como não se ensina mais latim nas escolas, aí vai uma tradução: Quantos casais de coelhos descendem de um casal em um ano. Leonardo passa a explicar o seu problema e a sua solução, como segue (com adaptação nossa): Um casal de coelhos recém-nascidos foi posto num lugar cercado. Deter- minar quantos casais de coelhos ter-se-ão após um ano, supondo que, a cada mês, um casal de coelhos produz outro casal e que um casal começa a procriar dois meses após o seu nascimento. Vamos organizar a nossa contagem na tabela a seguir. 4 Unidade 4Aplicações do Princípio de Indução Matemática mês número de casais do mês anterior número de casais recém-nascidos total 1o 0 1 1 2o 1 0 1 3o 1 1 2 4o 2 1 3 5o 3 2 5 6o 5 3 8 7o 8 5 13 8o 13 8 21 9o 21 13 34 10o 34 21 55 11o 55 34 89 12o 89 55 144 Portanto, o número de casais de coelhos em um determinado mês é igual ao número total de casais do mês anterior acrescido do número de casais nascidos no mês em curso, que é igual ao número total de casais do mês anterior ao anterior. Se denotarmos o número de coelhos existentes no n-ésimo mês por un, temos, então, que un = un−1 + un−2, u1 = u2 = 1. Essas relações definem, por recorrência, uma sequência de números naturais, chamada de sequência de Fibonacci, cujos elementos, chamados de números de Fibonacci, possuem propriedades aritméticas notáveis, que ainda hoje são objeto de investigação. + Para Saber Mais - O que é uma Recorrência? - Clique para ler + Para Saber Mais - Leonardo de Pisa - Fibonacci - Clique para ler 5 Unidade 4 Exemplo 3 [O Enigma do Cavalo de Alexandre] Num mosaico romano, Bucéfalo, o cavalo de Alexandre, o Grande, é repre- sentado como um fogoso corcel cor de bronze. Nesse exemplo, vamos “provar” que isso é uma falácia (uma grande mentira). Inicialmente, “provaremos” que todos os cavalos têm mesma cor. De fato, considere a sentença: P (n) : Num conjunto com n cavalos, todos têm a mesma cor. Note que P (1) é obviamente verdadeira. Agora, suponha o resultado válido para conjuntos contendo n cavalos. Considere um conjunto C = {C1, C2, . . . , Cn, Cn+1} com n+ 1 cavalos. Decompomos o conjunto C numa união de dois conjuntos: C = C ′ ∪ C ′′ = {C1, . . . , Cn} ∪ {C2, . . . , Cn+1}, cada um dos quais contém n cavalos. Pela hipótese indutiva, segue-se que os cavalos em C ′ têm mesma cor, ocor- rendo o mesmo para os cavalos em C ′′. Como C2 ∈ C ′ ∩ C ′′, segue-se que os cavalos de C ′ têm a mesma cor dos cavalos de C ′′, permitindo assim concluir que todos os cavalos em C têm a mesma cor. Assim, a nossa “demonstração” por indução está terminada, provando que P (n) é verdadeira para todo n ∈ N. Agora, todo mundo sabe (você sabia?) que Marengo, o famoso cavalo de Napoleão, era branco. Logo, Bucéfalo deveria ser branco. Onde está o erro nessa prova? Sugestão: Para achá-lo, sugerimos que você tente provar que, se P (1) é verdadeira, então P (2) é verdadeira. Esse problema foi inventado pelo matemático húngaro George Polya (1887- 1985). 6 Unidade 4Aplicações do Princípio de Indução Matemática Exemplo 4[Descobrindo a Moeda Falsa] Têm-se 3n moedas de ouro, sendo uma delas falsa, com peso menor do que as demais. Dispõe-se de uma balança de dois pratos, sem nenhum peso. Vamos mostrar, por indução sobre n, que é possível achar a moeda falsa com n pesagens. Para n = 1, isso é fácil de ver, pois, dadas as três moedas, basta pôr uma moeda em cada prato da balança e descobre-se imediatamente qual é a moeda falsa. Suponha, agora, que o resultado seja válido para algum valor de n e que se tenha que achar a moeda falsa dentre 3n+1 moedas dadas. Separemos as 3n+1 moedas em 3 grupos de 3n moedas cada. Coloca-se um grupo de 3n moedas em cada prato da balança. Assim, poderemos descobrir em que grupo de 3n moedas encontra-se a moeda falsa. Agora, pela hipótese de indução, descobre- se a moeda falsa com n pesagens, que, junto com a pesagem já efetuada, perfazem o total de n+ 1 pesagens. Exemplo 5[A Pizza de Steiner] O grande geômetra alemãoJacob Steiner (1796-1863) propôs e resolveu, em 1826, o seguinte problema: Qual é o maior número de partes em que se pode dividir o plano com n cortes retos? Pensando o plano como se fosse uma grande pizza, temos uma explicação para o nome do problema. Denotando o número máximo de pedaços com n cortes por pn, vamos provar por indução a fórmula: pn = n(n+ 1) 2 + 1. Para n = 1, ou seja, com apenas um corte, é claro que só podemos obter dois pedaços. Portanto, a fórmula está correta, pois p1 = 1(1 + 1) 2 + 1 = 2. Admitamos agora que, para algum valor de n, a fórmula para pn esteja correta. Vamos mostrar que a fórmula para pn+1 também está correta. 7 Unidade 4 Suponhamos que, com n cortes, obtivemos o número máximo n(n+1)/2+1 de pedaços e queremos fazer mais um corte, de modo a obter o maior número possível de pedaços. Vamos conseguir isso se o (n + 1)-ésimo corte encontrar cada um dos n cortes anteriores em pontos que não são de interseção de dois cortes (faça um desenho para se convencer disso). Por outro lado, se o (n+1)-ésimo corte encontra todos os n cortes anteriores, ele produz n + 1 novos pedaços: o corte começa em um determinado pedaço e, ao encontrar o primeiro corte, ele separa em dois o pedaço em que está, entrando em outro pedaço. Ao encontar o segundo corte, ele separa em dois o pedaço em que está, entrando em outro pedaço, e assim sucessivamente, até encontrar o n-ésimo corte separando o último pedaço em que entrar em dois. Assim, são obtidos n+ 1 pedaços a mais dos que já existiam; logo, pn+1 = pn + n+ 1 = n(n+ 1) 2 + 1 + n+ 1 = (n+ 1)(n+ 2) 2 + 1, mostrando que a fórmula está correta para n + 1 cortes. O resultado segue então do Princípio de Indução Matemática. 8 Unidade 4Aplicações do Princípio de Indução Matemática 4.1 Exercícios Recomendados 1. Prove que, qualquer que seja o número natural n maior do que 3, existe um polígono convexo com n lados e exatamente 3 ângulos agudos. 2. Um plano está dividido em regiões por várias retas. Prove que é pos- sível colorir essas regiões com duas cores de modo que quaiquer duas regiões adjacentes tenham cores diferentes (dizemos que duas regiões são adjacentes se elas tiverem pelo menos um segmento de reta em comum). 3. A sequência (an) é definida pelos dados: a1 = 1, a2 = 2, an+1 = an−an−1 se n > 2. Prove que an+6 = an para todos os números naturais n. Descreva todos os termos dessa sequência. 4. A sequência a1, a2, . . . , an, . . . de números é tal que a1 = 3, a2 = 5 e an+1 = 3an − 2an−1 para n > 2. Prove que an = 2n + 1 para todos os números naturais n. 4.2 Exercícios Suplementares 1. Ache o erro na “prova” do seguinte “Teorema” Todos os números naturais são iguais. Vamos provar o resultado mostrando que, para todo n ∈ N, é verdadeira a sentença P (n) : : dado n ∈ N, todos os número naturais menores ou iguais do que n são iguais. (i) P (1) é claramente verdadeira. (ii) Suponha que P (n) seja verdadeira, logo n − 1 = n. Somando 1 a ambos os lados dessa igualdade, obtemos n = n + 1. Como n era igual a todos os naturais anteriores, segue que P (n+ 1) é verdadeira. Portanto, P (n) ’e vedadeira para todo n ∈ N . 2. (O queijo de Steiner) Para fazer a sua pizza, Steiner teve que cortar, primeiro, o queijo. Imaginando que o espaço é um enorme queijo, você 9 Unidade 4 Exercícios Suplementares seria capaz de achar uma fórmula para o número máximo de pedaços que poderíamos obter ao cortá-lo por n planos? 3. Mostre que a sequência de Fibonacci satisfaz às seguintes identidades: (a) u1 + u2 + · · ·+ un = un+2 − 1. (b) u1 + u3 + · · ·+ u2n−1 = u2n. (c) u2 + u4 + · · ·+ u2n = u2n+1 − 1. (d) u21 + u 2 2 + · · ·+ u2n = unun+1. 4. Sabendo que q = 1 + √ 5 2 é raiz da equação x2 = x + 1, mostre que qn = unq + un−1. 5. Prove que u3 + u6 + u9 + · · ·+ u3n = u3n+2 − 1 2 . 6. Dada a recorrência an+2 = 2an+1 + an, com a1 = 1 e a2 = 3, ache uma fórmula para an. 10 Unidade 4Aplicações do Princípio de Indução Matemática 4.3 Textos Complementares Para Saber MaisOrigem da Torre de Hanói Esse jogo foi idealizado e publicado pelo matemático francês Edouard Lucas, em 1882, que, para dar mais sabor à sua criação, inventou a seguinte “lenda”: Na origem do tempo, num templo oriental, uma Divindade colocou 64 discos perfurados de ouro puro ao redor de uma de três colunas de diamante e ordenou a um grupo de sacerdotes que movessem os discos de uma coluna para outra, respeitando as regras acima explicadas. A Divindade sentenciou que, quando todos os 64 discos fossem transferidos para uma outra coluna, o mundo acabaria. Você não deve se preocupar com a iminência do fim do mundo, pois, se, a cada segundo, um sacerdote movesse um disco, o tempo mínimo para que ocorresse a fatalidade seria de 264− 1 segundos e isto daria, aproximadamente, um bilhão de séculos! 11 Unidade 4 Textos Complementares Para Saber Mais O que é uma Recorrência? Uma recorrência é uma fórmula que define um elemento de uma sequência a partir de termos anteriores. Uma recorrência do tipo: xn = xn−1 + xn−2, (4.1) só permite determinar o elemento xn se conhecermos os elementos anteriores xn−1 e xn−2, que, para serem calculados, necessitam do conhecimento dos dois elementos anteriores, e assim por diante. Fica, portanto, univocamente definida a sequência quando são dados x1 e x2. A sequência de Fibonacci corresponde à recorrência (4.1), onde x1 = x2 = 1. Quando é dada uma recorrência, um problema importante é determinar uma fórmula fechada para o termo geral da sequência, isto é, uma fórmula que não recorre aos termos anteriores. No caso da sequência de Fibonacci, existe uma tal fórmula, chamada fórmula de Binet, que apresentamos a seguir e que será demonstrada em um contexto mais geral na Unidade 8. Para todo n ∈ N, tem-se que un = ( 1+ √ 5 2 )n − ( 1− √ 5 2 )n √ 5 É notável que seja necessário recorrer a fórmulas envolvendo números ir- racionais para representar os elementos da sequência de Fibonacci, que são números naturais. Mais notável, ainda, é que o número ϕ = 1 + √ 5 2 seja a proporção áurea que aparece nas artes, e que 1− √ 5 2 = −ϕ−1 seja o simétrico de seu inverso. Intrigante essa inesperada relação entre criar coelhos e a divina proporção, não? 12 Unidade 4Aplicações do Princípio de Indução Matemática Para Saber MaisLeonardo de Pisa - Fibonacci Leonardo de Pisa (1170-1250), filho de Bonacci, e por isso apelidado Fi- bonacci, teve um papel fundamental no desenvolvimento da Matemática no Ocidente. Em 1202, publicou o livro Liber Abacci, que continha grande parte do conhecimento sobre números e álgebra da época. Esta obra foi responsável pela introdução na Europa do sistema de numeração indo-arábico e pelo pos- terior desenvolvimento da álgebra e da aritmética no mundo ocidental. 13 5 1 Progressões Aritméticas Sumário 5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . 2 5.2 Primeiros Exemplos . . . . . . . . . . . . . . . . . . 2 5.3 Soma dos Termos de uma PA . . . . . . . . . . . . 6 5.4 Somas Polinomiais . . . . . . . . . . . . . . . . . . . 9 5.5 Exercícios Recomendados . . . . . . . . . . . . . . . 14 5.6 Exercícios Suplementares . . . . . . . . . . . . . . . 16 5.7 Textos Complementares . . . . . . . . . . . . . . . . 20 Unidade 5 Introdução 5.1 Introdução As Progressões Aritméticas (PA) constituem-se na família mais simples de sequências de�nidas recorrentemente. Elas são comuns na vida real e sempre aparecem quando se apresentam grandezas que sofrem variações iguais em in- tervalos de tempos iguais como, por exemplo, no cálculo de juros simples, ou desvalorização de um bem ao longo do tempo. Nessa unidade, você encontrará também a fórmula que fornece a soma dos n primeiros termos de uma PA, fórmula que generaliza a que foi descoberta por Gauss, quando menino, conforme vimos na Unidade 3. Em seguida, são de�nidas generalizações do conceito de PA, introduzindo as PAs de segunda ordem, terceira ordem, etc. Esse tópico, em geral, não é explorado no Ensino Médio, mas coloca
Compartilhar