Baixe o app para aproveitar ainda mais
Prévia do material em texto
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 definir 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 significam 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 significado das expressões acima, até mesmo no que diz respeito aos pontinhos que nelas aparecem. Existe, contudo, um modo de tornar mais rigorosas definiçõ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 3 O Princípio de Indução Matemática Para definir uma expressão En, para todo número natural n, basta definirmos E1 e mostrar, para todo n ∈ N, como obter sem ambiguidade En+1 a partir de En. Nesse caso, dizemos que En foi definido por recorrência. Vejamos como intervém o Princípio de Indução Matemática para justificar este tipo de definição. Seja X o subconjunto de N, determinado pela condição: n ∈ X ⇐⇒ En está definido. Pela caracterização do conjunto X, temos que 1 ∈ X e, para todo n ∈ N, n ∈ X ⇒ n+ 1 ∈ X. Portanto, X = N. Definições por recorrência podem ser utilizadas para dar um significado a expressões como no início da unidade. Exemplo 1 Definimos S1 = 1. Em seguida, supondo Sn definido, pomos Sn+1 = Sn + (n+ 1). Damos assim, um sentido matemático preciso à expressão: Sn = 1 + 2 + · · ·+ n. Por outro lado, definindo 1! = 1 e pondo (n+1)! = n!(n+1), supondo que n! esteja definido, 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 definidas 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 Definem-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 definir 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 definição as potências de a. Pela sua importância, destacamos essa definição a seguir. 4 Unidade 3 O 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 definidas por recorrência como segue: a1 = a e an+1 = an · a. Quando a 6= 0, convenciona-se definir 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 2 Neste 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 fechada 1 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 . 1 Uma 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 3 O 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 4 Vamos 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 definiçõ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 3 O 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 um determinado 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 1 Seja 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ção Defina 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 6 Vamos mostrar que a desigualdade na sentença P (n) : 2n > 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 verificar 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 significa 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 3 O 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 3 O 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+ 1xn é 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 verifique 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 é verificada, pois P (1) : 1 = 2 é falsa! 14 Unidade 3 O 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 finito, 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 afirmaçõ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, filó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, desconfiada, 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 fluirem, só depois preocupe-se com a sua organização e formalização. 16 O Princípio de Indução Matemática Introdução O Poder do Método de Indução Exercícios Recomendados Exercícios Suplementares Textos Complementares
Compartilhar