Exercícios Resolvidos Diego Oliveira - Vitória da Conquista/BAIndução Matemática (Indução Fraca) Contato:
[email protected] Escrito por Diego Oliveira - Publicado em 20/12/2014 - Atualizado em 16/07/2017 O que é: A indução matemática é uma técnica usada para demonstrar proposições a respeito dos números inteiros. Não sendo possível utiliza-la com números racionais ou irracionais. Primeiro princípio de indução: Seja P(n) uma proposição dependente de n (n ∈ Z), com n ≥ , sendo um inteiro dado, supondo que se consiga provar que: ) P() é verdadeira. ) Se k ≥ e P(k) é verdadeira, então P(k + 1) também é verdadeira. então P(n) é verdadeira para todo n ≥ . Exemplo 1: Demonstre por indução que Exemplo 2: Demonstre por indução: o sucessor de qualquer inteiro po- sitivo n é maior que seu antecessor (n ≥ 1). n(n + 1) a) 1 + 2 + · · · + n = (n ≥ 1) Solução: 2 b) 1 + 3 + 5 + · · · + (2n − 1) = n2 Prova de : (n ≥ 1) c) 13 + 23 + · · ·+ n3 = (1+ 2+ ...+ n)2 Note que a proposição é valida para 1. (n ≥ 1) Pois, 2 é sucessor de 1 e 2 > 1. d) 1 · 2 + 2 · 3 + · · · + n · (n + 1) = n(n + 1)(n + 2) Prova de : (n ≥ 1) 3 Se a proposição é válida para k então, ele e) n2 > n + 1 (n ≥ 2) deve ser menor que seu sucessor. k<k+1 Solução de a: Somando 1 em cada membro Prova de : Observe que a proposição é verdadeira k + 1 < (k + 1) + 1 para n = 1, pois 1(1 + 1) k+1<k+2 1= =1 2 Prova de : Como k + 2 é sucessor de k + 1 então, pela desigualdade acima a proposição tam- Admitindo que a proposição seja ver- bém deve ser válida para k + 1. dadeira para um k ∈ A então: k(k + 1) Desse modo, pelo princípio de indução a 1+ ···+ k = proposição é válida para todo n ∈ Z, maior 2 ou igual a 1. Somando (k + 1) em ambos os termos 1 Exercícios Resolvidos Diego Oliveira - Vitória da Conquista/BA k(k + 1) 13 + 23 + · · · + k 3 = (1 + 2 + ... + k)2 1 + · · · + k + (k + 1) = + (k + 1) 2 Somando (k + 1)3 em ambos os membros chegamos á: então (k + 1)(k + 2) 13 +23 +· · ·+k 3 +(k+1)3 = (1+2+...+k)2 +(k+1)3 1 + · · · + k + (k + 1) = 2 Como visto na letra do exercício 1 + 2 + k(k + 1) O que mostra que a proposição também ... + k = . Assim, podemos fazer a seria válida para k + 1. 2 seguinte substituição Assim, pelo princípio de indução a proposição é valida para todo n ∈ Z maior ou igual a 1. 2 k(k + 1) 2 3 (1+2+...+k) +(k+1) = +(k+1)3 Solução de b: 2 Prova de : A proposição é verdadeira para 1 pois, 2 3 (k + 1)2 (k + 2)2 1 = 12 . (1 + 2 + ... + k) + (k + 1) = 22 Prova de : 2 Se a proposição é verdadeira para k en- (k + 1)(k + 2) tão: (1 + 2 + ... + k)2 + (k + 1)3 = 2 1 + 3 + 5 + · · · + (2k − 1) = k 2 (1+2+...+k)2 +(k+1)3 = (1 + 2 + ... + (k + 1))2 Note que os valores a direita crescem de 2 em 2 (1, 3, 5,...). Assim o próximo termo Com isso mostramos que se a proposição da sequencia depois de 2k − 1 seria 2k + 1. é válida para k então ela também é válida para k + 1. Assim, pelo princípio de indução a proposição é válida para todo n ≥ 1. 1+ 3+ 5+ · · ·+ (2k − 1)+ (2k + 1) = k 2 + (2k + 1) Solução de d: Prova de : 1 + 3 + 5 + · · · + (2k − 1) + (2k + 1) = (k + 1)2 A proposição é válida para 1. Ou seja, se a proposição é valida para k 1(1 + 1)(1 + 2) então ela é válida para k + 1. Sendo assim, 1·2= 3 pelo princípio de indução a proposição é ver- dadeira para todo n ≥ 1. 6=6 Solução de c: Prova de : prova de : Tomando a proposição como verdadeira para k então: A proposição é válida para 1, pois 13 = 12 . Prova de : k(k + 1)(k + 2) Se a proposição é válida para k então 1 · 2 + 2 · 3 + · · · + k · (k + 1) = 3 2 Exercícios Resolvidos Diego Oliveira - Vitória da Conquista/BA Somando a ambos os membros (k+ 1)(k+ propriedades: 2) (1) a ∈ Y; 1 · 2 + 2 · 3 + · · · + k · (k + 1) + (k + 1) · (k + 2) (2) n ∈ Y ⇒ n + 1 ∈ Y. k(k + 1)(k + 2) = + (k + 1)(k + 2) Prove que Y contem todos os números 3 naturais maiores do que ou iguais a . 1 · 2 + 2 · 3 + · · · + (k + 1) · (k + 2) (k + 1)(k + 2)(k + 3) Solução = 3 Considere um conjunto X = ∪ Y onde Com isso mostramos que se a proposição = {n ∈ N; n < }. Se provarmos que X = é válida para k então ela também é válida N, então logicamente Y = {n ∈ N; n ≥ }. para k + 1. Assim, pelo princípio de indução Como a primeira demonstração é mais sim- a proposição é válida para todo n ≥ 1. ples vamos focar nela. Solução de e: Nova proposição: Se n ∈ N, então n ∈ X. Prova de : Prova de : A proposição é verdadeira para 2. Para essa prova temos que analisar dois casos > 0 e = 0. 22 > 2 + 1 4>3 Se > 0 então 0∈I o que implica em 0 ∈ X; Prova de : Se = 0 então 0 ∈ Y que implica Se a proposição é verdadeira para k en- que 0 ∈ X. tão: Assim, como mostrado em ambos os ca- k2 > k + 1 sos, a proposição é verdadeira para zero. Somando 1 em ambos os membros en- Prova de : tão: Supondo que k ∈ N, então ou k ∈ I ou k ∈ Y. Vamos considerar ambas as hipóte- ses. k2 + 1 > k + 2 Como (k + 1)2 > k 2 + 1 então Se k ∈ I a então k < que im- plica que: (k + 1)2 > k 2 + 1 > k + 2 ◦ k + 1 ≥ , nesse caso O que resulta em (k + 1)2 > k + 2 k + 1 ∈ Y; ◦ ou então k + 1 < , Com isso mostramos que se a proposição nesse caso k + 1 ∈ I . é válida para k então ela também é válida para k + 1. Assim, pelo princípio de indução a proposição é válida para todo n ≥ 2. Em todo caso k + 1 ∈ X. Se k ∈ Y então k ≥ ⇒ k + 1 > Exemplo 3: Dado o numero natural , ∈ Y que implica novamente que seja Y ⊂ N um conjunto com as seguintes k + 1 ∈ X, pois Y ⊂ X. 3 Exercícios Resolvidos Diego Oliveira - Vitória da Conquista/BA Como o 0 e todos os seus sucessores per- Completando a demonstração. tencem a X então X = N. O que conduz a conclusão de que Y = {n ∈ N; n ≥ }. Solução da segunda parte: Prova de : Exemplo 4: Use o exercício anterior para Para n = 5 temos: provar que 2n + 1 < 2n em seguida, que n ≤ 2 < 2n para todo n ≤ 5. 52 < 25 Solução da primeira parte: Logo a desigualdade é valida para n = 5. Prova de : Prova de : Essa proposição simplesmente não Se a formula e verdadeira para k, então: ocorre para n = 2 (verifique!). No entanto (k + 1)2 = (2k + 1) + k 2 ≤ 2k + k 2 para n ≥ 3 isso ocorre. Vamos prova-la pela indução já que pro outro caso isso não seria Vamos provar que 2k + k 2 < 2k+1 . possível. 2k + k 2 < 2k+1 Para n = 3 temos: k 2 < 2k+1 − 2k k 2 < 2k (2 − 1) 2(3) + 1 < 23 k 2 < 2k Logo a desigualdade é valida para n = 3. Essa última inequação e verdadeira por hipótese assim: Prova de : (k + 1)2 < 2k + k 2 < 2k+1 Se a desigualdade é verdadeira para um Que simplificando fica: k ∈ N, então: (k + 1)2 < 2k+1 2k + 2 + 1 = 2k + 2 O que completa a demonstração. 2(k + 1) + 1 = 2k + 2 Exemplo 5: Prove por indução que Acontece que 2k + 2 < 2k+1 . Veja: n+1 n ≤ n, para todo n ≥ 3. n 2k + 2 < 2k+1 Solução: 2 < 2k+1 − 2k Prova de : 2 < 2k (2 − 1) Para n = 3 temos: 2 < 2k 3 3+1 <3 3 Como n = k, então k não pode ser menor que três. O que prova essa ultima desigual- O que é verdadeiro. dade. Assim: Prova de : 2(k + 1) + 1 = 2k + 2 < 2k+1 O que desejamos agora é provar que a desigualdade k+1 (k + 1) + 1 <k+1 ⇒ 2(k + 1) + 1 < 2k+1 k+1 4 Exercícios Resolvidos Diego Oliveira - Vitória da Conquista/BA Ocorre que k(k + 1)(2k + 1) k+1 k 1+22 +32 +. . .+k 2 +(k+1)2 = +(k+1)2 (k + 1) + 1 k+2 k+2 6 = · k+1 k+1 k+1 k(k + 1)(2k + 1) = + (k + 1)2 6 então podemos escrever a desigualdade como: (k + 1)(k + 2)(2k + 3) = k 6 k+2 k+2 · <k+1 k+1 k+1 (k + 1)((k + 1) + 1)(2(k + 1) + 1) = 6 (k + 2)k+1 <k+1 que implica em: (k + 1)k+1 1 + 22 + 32 + . . . + k 2 + (k + 1)2 (k + 1)((k + 1) + 1)(2(k + 1) + 1) (k + 2)k+1 < (k + 1)k+1 (k + 1) = (k + 1)k+2 = 6 Completando a demonstração. Simplificando: Exemplo 7: Critique a seguinte argu- (k + 2)k+1 < (k + 1)k+2 mentação: Quer-se provar que todo numero natural é pequeno. Evidentemente, 1 é um O que evidencia a afirmação, concluindo numero pequeno. Além disso, se n for pe- que: queno, n + 1 também sera, pois não se torna grande um numero pequeno simplesmente somando-lhe uma unidade. Logo, por in- k+1 (k + 1) + 1 dução, todo numero natural e pequeno. <k+1 k+1 Solução: O problema aqui ocorreria no passo in- Exemplo 6: Prove por indução que: dutivo. Pois quando tomamos um n natu- ral "pequeno" temos de nos perguntar, pe- queno em relação a que? Se em relação n(n + 1)(2n + 1) ao maior de todos os números naturais pe- 1 + 22 + 33 + ... + n2 = 6 quenos então n + 1 seria grande? Solução: Exemplo 8: Use indução para provar que 1 Prova de : 13 + 23 + 33 + . . . + n3 = n2 (n + 1)2 4 A igualdade se verifica para 1. Veja: Solução: 1(1 + 1)(2(1) + 1) 1= Prova de : 6 A igualdade se verifica para 1. 1=1 1 Prova de : 1= · 12 (1 + 1)2 4 Supondo que a proposição seja ver- dadeira para k ∈ N, então: 1=1 5 Exercícios Resolvidos Diego Oliveira - Vitória da Conquista/BA Exemplo 9: Prove por indução que n! > n2 , para n > 3. Prova de : Considerando a proposição verdadeira Solução: para k então: Prova de i: 1 13 + 23 + 33 + . . . + k 3 + (k + 1)3 = · k 2 (k + Para n = 4 a proposição é verdadeira pois 4 1)2 + (k + 1)3 4! > 4. Prova de ii: Operando com o lado direito da igualdade acima facilmente se chega á: Fazendo n = k + 1 então: 1 · k 2 (k + 1)2 + (k + 1)3 4 n! > n2 k 2 (k + 1)2 + 4(k + 1)3 = 4 ⇒ (k + 1)! > (k + 1)2 E após certa álgebra: ⇒ (k + 1)k! > (k + 1)(k + 1) k 2 (k + 1)2 + 4(k + 1)3 1 ⇒ k! > k + 1 = (k + 1)2 (k + 2)2 4 4 Que de fato ocorre para todo k > 3. Com- Concluindo a demonstração. pletando a demonstração. 6 Exercícios Resolvidos Diego Oliveira - Vitória da Conquista/BA Este trabalho está licenciado com uma Licença Creative Commons - Atribuição-NãoComercial- CompartilhaIgual 4.0 Internacional. Esse documento está sujeito a constante atualização ou mesmo correções, por isso, certifique se que o que você têm em mãos é de fato a última versão do mesmo. Para saber, bem como ter acesso a vários outros exercícios resolvidos de matemática, acesse: www.number.890m.com E se alguma passagem ficou obscura ou se algum erro foi cometido por favor entre em contato para que possa ser feito a devida correção. .ƒ cebook.com/ theNmberType nbbedego@gm.com .nmber.890m.com 7