Transcript
Exercícios Resolvidos
Diego Oliveira - Vitória da Conquista/BA
Indução Matemática (Indução Fraca) Contato: Contato:
nibbledi nibblediego@ ego@gmai gmail.co l.com m
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ú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 supondo que se consiga provar que:
≥
, sendo um inteiro dado,
) 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 o sucessor de qualquer inteiro po- sitivo n é maior que seu antecessor ( n ≥ 1).
Exemplo 2: Demonstre 2: Demonstre por indução:
a) 1 + 2 + · · · + n =
Solução:
b) 1 + 3 + 5 + (n ≥ 1)
Prova de :
n(n + 1 )
· · · +
2
( n ≥ 1)
(2n − 1) = n2
c) 13 + 23 + · · · + n3 = (1 + 2 + ... + n)2 (n ≥ 1)
Note Note que a propo proposiç sição ão é valid valida a para para 1. Pois, 2 é sucessor de 1 e 2 > 1 .
d) 1 · 2 + 2 · 3 + n( n + 1 )( n + 2 )
Prova de :
+ n · ( n + 1) =
(n ≥ 1)
3
Se a proposição é válida para k então, ele deve ser menor que seu sucessor.
···
e) n2 > n + 1 (n ≥ 2) Solução de a:
k < k + 1
Prova de :
Somando 1 em cada membro
Observe Observe que a proposi proposição ção é verdadei verdadeira ra para n = 1 , pois
k + 1 < ( k + 1 ) + 1
1 =
k + 1 < k + 2
1( 1 + 1 ) 2
= 1
Prova de :
Como k + 2 é sucess sucessor or de k + 1 então, Admi Admiti tind ndo o que que a prop propos osiç ição ão seja seja ver verpela desigualdade acima a proposição tamdadeira para um k ∈ A então: bém deve ser válida para k + 1 . Desse modo, pelo princípio de indução a proposição é válida para todo n ∈ Z, maior ou igual a 1.
= 1 + · · · + k =
k ( k + 1 ) 2
Somando ( k + 1 ) em ambos os termos 1
Exercícios Resolvidos
1 + · · · + k + (k + 1 ) =
Diego Oliveira - Vitória da Conquista/BA
k ( k + 1 ) 2
13 + 2 3 + · · · + k 3 = (1 + 2 + ... .. . + k )2
+ (k + 1 )
Somando ( k + 1)3 em ambos os membros então
chegamos á:
1 + · · · + k + (k + 1 ) =
13 + 23 + · · ·+ k 3 + ( k + 1) 3 = (1+ 2+ ... + k )2 + ( k + 1) 3
( k + 1 )( k + 2 ) 2
Como visto na letra do exercício 1 + 2 + k (k + 1 ) O que mostra que a proposição também ... + k = . Assim Assim,, podemo podemos s fazer fazer a 2 seria válida para k + 1 . seguinte substituição Ass Assim, im, pelo pelo prin princ cípio ípio de ind induçã ução a proposição é valida para todo n ∈ Z maior ou igual a 1. k ( k + 1 ) 2 2 3 ( 1+ 2+ ... + k ) + ( k + 1) = + ( k + 1) 3 2 Solução de b:
Prova de : A propo proposiç sição ão é verdad verdadeir eira a para para 1 pois, pois, ( k + 1 )2 ( k + 2 )2 2 3 ( 1 + 2 + ... .. . + k ) + ( k + 1) = 1 = 1 2 . 2 2
Prova de : Se a proposição é verdadeira para k en( k + 1 )( k + 2 ) ( 1 + 2 + ... + k ) 2 + (k + 1)3 = tão:
2
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,...). 5,...). Assim Assim o próx próximo imo termo termo Com isso mostramos que se a proposição da sequencia depois de 2 k − 1 seria 2k + 1 . é válida para k então ela também é válida + 1 . Assim, para k + 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 . Sendo assim, então ela é válida para k + assim, pelo princípio de indução a proposição é verdadeira para todo n ≥ 1.
1 · 2 =
1( 1 + 1 )( 1 + 2 ) 3 6 = 6
Solução de c:
Prova de :
prova de :
Tomando Tomando a proposição proposição como verdadeira para k então:
A prop propos osiç ição ão é váli válida da para para 1, poi pois s 13 = 1 2 . Prova de :
1 · 2 + 2 · 3 + · · · + k · (k + 1 ) =
Se a proposição é válida para k então 2
k ( k + 1 )( k + 2 ) 3
Exercícios Resolvidos
Diego Oliveira - Vitória da Conquista/BA
Somando a ambos os membros ( k + 1)( k +
propriedades:
2)
(1) a (2) n
1 · 2 + 2 · 3 + · · · + k · ( k + 1) + ( k + 1) · ( k + 2) k ( k + 1 )( k + 2 ) = + (k + 1 )( k + 2 ) 3
∈ Y; ∈ Y ⇒
n + 1 ∈ Y. Y.
Prov Prove e que Y contem contem todos os númer números os naturais maiores do que ou iguais a .
1 · 2 + 2 · 3 + · · · + (k + 1 ) · (k + 2 ) ( k + 1 )( k + 2 )( k + 3 ) = 3
Solução
Consider Considere e um conjunto conjunto X = ∪ Y onde Com isso mostramos que se a proposição = {n ∈ N; n < }. Se prova provarmo rmos s que X = é válida para k então ela também é válida N, então então logica logicamen mente te Y = {n ∈ N; n ≥ }. para k + 1 . Assim, Assim, pelo princípio de indução Como a primeira demonstração é mais sima 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 que 0 ∈ X .
Se a proposição é verdadeira para k então:
∈
Y que implica
Assim, como mostrado em ambos os casos, a proposição é verdadeira para zero.
k 2 > k + 1
Prova de :
Somando 1 em ambos os membros então:
Supondo que k ∈ N, então ou k ∈ I ou amos considerar considerar ambas as hipótehipótek ∈ Y . Vamos ses.
k 2 + 1 > k + 2
Como (k + 1 )2 > k 2 + 1 então
Se k ∈ I a então k < que implica que:
( k + 1 ) 2 > k 2 + 1 > k + 2 ◦ k + 2
1 ≥ , nesse caso
k + 1 ∈ Y; ◦ ou então k + 1 < , nesse caso k + 1 ∈ I .
O que resulta em (k + 1 ) > k + 2 Com isso mostramos que se a proposição é válida para k então ela também é válida para k + 1 . Assim, Assim, pelo princípio de indução a proposição é válida para todo n ≥ 2.
Em todo caso k + 1 ∈ X. + 1 > Se k ∈ Y então k ≥ ⇒ k + ∈ Y que implica novamente que k + 1 ∈ X, pois Y ⊂ X.
Exemplo Exemplo 3: Dado o numero natural , seja Y ⊂ N um conjunto com as seguintes 3
Exercícios Resolvidos
Diego Oliveira - Vitória da Conquista/BA
Como o 0 e todos os seus sucessores pertencem a X então X = N. O que que cond conduz uz a conclusão de que Y = { n ∈ N; n ≥ }.
Completando a demonstração. Solução da segunda parte: Prova de :
Exemplo 4: Use 4: Use o exercício anterior para provar provar que 2n + 1 < 2n em seguid seguida, a, que n n ≤ 2 < 2 para todo n ≤ 5.
Para n = 5 temos: 52 < 2 5
Solução da primeira parte:
Logo a desigualdade é valida para n = 5 . Prova de :
Prova de :
Se a formula e verdadeira para k , então:
Essa Essa prop propos osiç ição ão simp simple lesm smen ente te não não ocorre para n = 2 (verifique (verifique!). !). No entanto entanto para n ≥ 3 isso ocorre. Vamos prova-la pela indução já que pro outro caso isso não seria possível.
( k + 1 ) 2 = (2k + 1 ) + k 2 ≤ 2k + k 2
Vamos provar que 2k + k 2 < 2 k + 1 . 2k + k 2 < 2 k + 1 k 2 < 2 k + 1 − 2k k 2 < 2 k ( 2 − 1) k 2 < 2 k
Para n = 3 temos: 2( 3) + 1 < 2 3
Essa última inequação inequação e verdadei verdadeira ra por hipótese assim:
Logo a desigualdade é valida para n = 3 . Prova de :
( k + 1 ) 2 < 2 k + k 2 < 2 k + 1
Se a desigualdade é verdadeira para um ∈ N, então: k ∈
Que simplificando fica: ( k + 1 ) 2 < 2 k + 1
2k + 2 + 1 = 2 k + 2
O que completa a demonstração.
2( k + 1 ) + 1 = 2 k + 2
Exem Exempl plo o 5:
Acontece que 2k + 2 < 2 k + 1 . Veja:
2k + 2 < 2 k + 1
n + 1 n
n
≤
Prov Prove e por por indu induçã ção o que que
n, para todo n
≥
3.
Solução:
2 < 2 k + 1 − 2k
Prova de :
k
2 < 2 ( 2 − 1)
Para n = 3 temos: 2 < 2 k
Como n = k , então k não pode ser menor que três. O que prova prova essa ultima desigualdesigualdade. Assim:
3 + 1 3
3
< 3
O que é verdadeiro. Prova de :
2( k + 1 ) + 1 = 2 k + 2 < 2 k + 1
⇒
O que desejamos agora é provar que a desigualdade
2( k + 1 ) + 1 < 2 k + 1
4
( k + 1 ) + 1
k + 1
k + 1
< k + 1
Exercícios Resolvidos
Diego Oliveira - Vitória da Conquista/BA
Ocorre que
(k + 1 ) + 1
k + 1
k + 1
=
k + 2 k + 1
k
·
k + 2 k + 1
1+ 22 + 32 + . . .+ k 2 + (k + 1)2 =
=
então podemos escrever a desigualdade como:
k + 2 k + 1
k
·
k + 2 k + 1
( k + 2
( k + 1 )k + 1
6
=
6
+ (k + 1 )2
(k + 1 )( k + 2 )( 2k + 3 ) 6
< k + 1 =
)k + 1
k ( k + 1 )( 2k + 1 )
k ( k + 1 )( 2k + 1 )
(k + 1 )(( k + 1 ) + 1 )( 2(k + 1 ) + 1 ) 6
que implica em:
< k + 1
1 + 2 2 + 3 2 + . . . + k 2 + (k + 1 ) 2 (k + 1 )(( k + 1 ) + 1 )( 2( k + 1 ) + 1 ) = 6
(k + 2 ) k + 1 < ( k + 1 )k + 1 ( k + 1 ) = (k + 1 ) k + 2
Completando a demonstração. Simplificando: Exempl Exemplo o 7: Critiq Critique ue a segui seguinte nte arguargumentação: Quer-se provar que todo numero natural natural é pequeno. pequeno. Evidenteme Evidentemente, nte, 1 é um numero o pequen pequeno. o. Além Além disso disso,, se n for peO que evidencia a afirmação, concluindo numer queno, n + 1 também sera, pois não se torna que: grande um numero pequeno simplesmente soma somand ndoo-lh lhe e uma uma unid unidad ade. e. Logo Logo,, por por inindução, todo numero natural e pequeno. ( k + 1 ) + 1 k + 1 < k + 1 k + 1 Solução: ( k + 2 )k + 1 < ( k + 1 ) k + 2
O probl problema ema aqui aqui ocorr ocorreri eria a no passo passo indutivo dutivo.. Pois Pois quando quando tomamos tomamos um n natural "pequeno" temos de nos perguntar, pequen queno o em rela relaçã ção o a que? que? Se em relaç relação ão ao maior de todos os números naturais pequenos então n + 1 seria grande?
Exemplo 6: Prove 6: Prove por indução que:
.. . + n 2 = 1 + 2 2 + 3 3 + ...
n(n + 1 )( 2n + 1 ) 6
Solução:
Exemplo 8: Use 8: Use indução para provar que 13 + 2 3 + 3 3 + . . . + n 3 =
Prova de :
A igualdade se verifica para 1. Veja: 1 =
1 4
n2 ( n + 1 ) 2
Solução:
1( 1 + 1 )( 2( 1) + 1 )
Prova de :
6
A igualdade se verifica para 1. 1 = 1 1 =
Prova de :
Supo Supond ndo o que que a prop propos osiç ição ão seja seja ver verdadeira para k ∈ N, então:
1 4
·1
2
( 1 + 1 ) 2
1 = 1
5
+ ( k + 1)2
Exercícios Resolvidos
Diego Oliveira - Vitória da Conquista/BA
Exemplo 9: Prove por indução que n! > n , para n > 3 . 2
Prova de : Solução:
Consid Considera erando ndo a propo proposiç sição ão verdad verdadeir eira a para k então:
Prova de i: 13 + 23 + 33 + . . . + k 3 + (k + 1) 3 = 1)2 + (k + 1 ) 3
1 4
· k 2 ( k +
Para n = 4 a proposição é verdadeira pois 4! > 4 . Prova de ii:
Operando com o lado direito da igualdade acima facilmente se chega á: 1 4
=
· k 2 ( k + 1 )2 2
Fazendo n = k + 1 então:
+ (k + 1 ) 3
2
k (k + 1 ) + 4 ( k + 1 )
n! > n2
3
4
E após certa álgebra: k 2 ( k + 1 ) 2 + 4 ( k + 1 )3 4
=
1 4
2
( k + 1) ( k + 2)
2
⇒
(k + 1 ) ! > ( k + 1 ) 2
⇒
(k + 1 ) k ! > ( k + 1 )( k + 1 )
⇒
k ! > k + 1
Que de fato ocorre para todo k > 3 . Completando a demonstração.
Concluindo 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ãoComercialCompartilhaIgual 4.0 Internacional.
Esse documento documento está sujeito a constant constante e atualiza atualização ção ou mesmo mesmo correç correções, ões, por isso, isso, certifi certifique que se que o que você você têm em mãos mãos é de fato a última última versão versão do mesmo 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