Baixe o app para aproveitar ainda mais
Prévia do material em texto
MAT 01375 – Matema´tica Discreta B 2013/1 Lista de Exerc´ıcios 9 Soluc¸o˜es de Exerc´ıcios Escolhidos 1 (d). Provaremos esse resultado pelo Princ´ıpio da Induc¸a˜o Matema´tica. Base (n = 0): Note que 100 + 3 · 42 + 5 = 54 = 6 · 9, de forma que a afirmac¸a˜o vale para n = 0. Passo da Induc¸a˜o: Seja n ≥ 0 e suponha que 10n + 3 · 4n+2 + 5 e´ divis´ıvel por 9. Note que 10n+1 + 3 · 4n+3 + 5 = 10 · 10n + 4 · 3 · 4n+2 + 5 = (9 + 1) · 10n + (3 + 1) · 3 · 4n+2 = 9 · 10n + 3 · 3 · 4n+2 + (10n + 3 · 4n+2 + 5) = 9 ( 10n + 4n+2 ) + ( 10n + 3 · 4n+2 + 5) . O primeiro termo desta u´ltima expressa˜o e´ claramente divis´ıvel por 9, enquanto que o segundo e´ divis´ıvel por 9 pela Hipo´tese de Induc¸a˜o. Logo, a sua soma e´ divis´ıvel por 9 e o resultado segue pelo Princ´ıpio da Induc¸a˜o Matema´tica. 1 (e). Provaremos esse resultado pelo Princ´ıpio da Induc¸a˜o Matema´tica. Base (n = 1): Nesse caso, temos 1∑ i=1 i3 = 13 = 1 = 12 = ( 1(1 + 1) 2 )2 , como de- sejado. Passo da Induc¸a˜o: Dado n ≥ 1, suponha que n∑ i=1 i3 = 13 + 23 + · · ·+ n3 = n 2(n+ 1)2 4 . Note que n+1∑ i=1 i3 = (n+ 1)3 + n∑ i=1 i3 = (n+ 1)3 + n2(n+ 1)2 4 = (n+ 1)2 ( n+ 1 + n2 4 ) = (n+ 1)2 4 (n2 + 4n+ 4) = (n+ 1)2(n+ 2)2 4 , como desejado. Note o uso da Hipo´tese da Induc¸a˜o na passagem para a segunda linha da equac¸a˜o acima. 1 (f). Provaremos esse resultado pelo Princ´ıpio da Induc¸a˜o Matema´tica. Para tanto, utilizaremos as seguintes relac¸o˜es: (I) ( n+ 1 k ) = ( n k ) + ( n k − 1 ) para 0 ≤ k ≤ n+1 e supondo ( nn+1) = ( n−1) = 0, ∀n (II) n∑ j=0 ( n j ) = 2n. Base (n = 0): Como 0∑ i=0 i ( 0 i ) = 0 = 0 · 2−1, o resultado vale neste caso. Passo da Induc¸a˜o: Dado n ≥ 0, suponha que n∑ i=0 i ( n i ) = n2n−1. Note que, pela igualdade mencionada acima, temos n+1∑ i=0 i ( n+ 1 i ) = n+1∑ i=0 i (( n i ) + ( n i− 1 )) = n+1∑ i=0 i ( n i ) + n+1∑ i=0 i ( n i− 1 ) = ( n∑ i=0 i ( n i )) + (n+ 1) ( n n+ 1 ) + ( n+1∑ i=1 i ( n i− 1 )) + 0 ( n −1 ) = n∑ i=0 i ( n i ) + n∑ j=0 (j + 1) ( n j ) = n∑ i=0 i ( n i ) + n∑ j=0 j ( n j ) + n∑ j=0 ( n j ) . Pela hipo´tese de induc¸a˜o, as duas primeiras somas sa˜o iguais a n2n−1 e, por (II), a terceira soma resulta em 2n. Conclu´ımos que n+1∑ i=0 i ( n+ 1 i ) = n2n−1 + n2n−1 + 2n = n2n + 2n = (n+ 1)2n, como quer´ıamos demonstrar. Outra demonstrac¸a˜o: Dado n ≥ 0, considere a func¸a˜o real f(x) = (x + 1)n, que, pelo Teorema Binomial, pode ser escrita como f(x) = (x+ 1)n = n∑ i=0 ( n i ) xi. A sua derivada e´ dada por f ′(x) = n(x + 1)n−1 = ∑n i=0 ( n i ) ixi−1. Assim, f ′(1) = n2n−1 = ∑n i=0 i ( n i ) , como quer´ıamos demonstrar. 3. Provaremos esse resultado pelo Princ´ıpio da Induc¸a˜o Forte (tambe´m chamado de 2a forma do Princ´ıpio da Induc¸a˜o). Base (n = 1): Note que 1 = 20, de forma que a afirmac¸a˜o vale para n = 1. Passo da Induc¸a˜o: Seja n ≥ 1. Suponha que todo inteiro m tal que 1 ≤ m ≤ n e´ soma de poteˆncias de dois distintas. Considere o inteiro n + 1. Inicialmente, suponha que n + 1 e´ ı´mpar enta˜o n+ 1 = n+ 20, e, pela Hipo´tese de Induc¸a˜o, n+ 1 = 2α1 + 2α2 + 2α3 + · · ·+ 2αr + 20, com αi 6= αj se i 6= j. Como n e´ par, αi 6= 0 para todo i ∈ {1, 2, . . . , r}, logo a expressa˜o acima e´ a representac¸a˜o de n+ 1 soma de poteˆncias de dois distintas. Por outro lado, se n+1 e´ par, temos que n+1 = 2m para certo inteiro positivo m ≤ n. Pela hipo´tese de induc¸a˜o, temos n+ 1 = 2 · (2β1 + 2β2 + 2β3 + · · ·+ 2βt) = 2β1+1 + 2β2+1 + · · · 2βt+1. Segue que n+ 1 e´ a soma de poteˆncias de 2 distintas. 4. Provaremos que 3n > n2, para todo inteiro n ≥ 0. Base (n ∈ {0, 1, 2}): Claramente, 30 = 1 > 0 = 02, 31 = 3 > 1 = 12 e 32 = 9 > 4 = 22. Passo da Induc¸a˜o: Seja n ≥ 2. Suponha que 3n > n2. Note que 3n+1 − (n+ 1)2 = 3 · 3n − (n2 + 2n+ 1) > 3n2 − (n2 + 2n+ 1) = 2(n2 − n)− 1, onde a desigualdade segue da Hipo´tese de Induc¸a˜o. Como n ≥ 2, temos n2−n > 0 e, portanto, 2(n2 − n)− 1 > 0. Conclu´ımos que 3n+1 > (n+ 1)2, como quer´ıamos demonstrar. Observac¸a˜o: Note que demosntramos treˆs casos na Base da Induc¸a˜o, pois o ar- gumento utilizado no Passo da Induc¸a˜o falha se n < 2. De fato, na˜o temos 2(n2 − n)− 1 para n ∈ {0, 1}. 5. Seja θ ∈ R. A prova sera´ por induc¸a˜o em n. Base (n = 0): Observe que (cos θ + i sen θ)0 = 1 = cos 0 + sen 0, como desejado. Passo da Induc¸a˜o: Seja n ≥ 0. Suponha que (cos θ + i sen θ)n = cos(nθ) + i sen(nθ). Temos que (cos θ + i sen θ)n+1 = (cos θ + i sen θ)(cos θ + i sen θ)n = (cos θ + i sen θ)(cos(nθ) + i sen(nθ)) = cos θ cos(nθ)− sen θ sen(nθ) + i (cos θ sen(nθ) + sen θ sen(nθ)) = cos (θ + nθ) + i sen (θ + nθ) = cos((n+ 1)θ) + i sen((n+ 1)θ), como quer´ıamos demonstrar. Note o uso da Hipo´tese da Induc¸a˜o para chegar- mos a` terceira linha da equac¸a˜o acima, e das equac¸o˜es de soma de aˆngulos para deduzirmos a quarta linha.
Compartilhar