3 Exemplos resolvidos

Prévia do material em texto

<p>UNIVERSIDADE DO VALE DO RIO DOS SINOS</p><p>Matemática para Computação</p><p>Prof. Rodrigo Orsini Braga</p><p>Mais exercícios de Indução</p><p>PRINCÍPIO DA INDUÇÃO MATEMÁTICA (PIM)</p><p>Se pretendemos provar que uma propriedade p n se verifica no conjunto IN, devemos provar que:</p><p> p(n) verifica-se para o número a (menor natural para o qual a sentença verifica-se ser</p><p>verdadeira).</p><p> p k ⇒ pk1 , ∀ ka , ou seja, supondo-se a propriedade p(n) verdadeira para um</p><p>número natural k , qualquer, ka , então a propriedade p(n) verifica-se para k1 .</p><p>Então, podemos concluir que p n é verdadeira, ∀ n∈ℕ , na .</p><p>Exercício 1: Prove que ,3)36(...1593 2nn =−++++ ∀ n∈ℕ , n1 .</p><p>Solução:</p><p>Você conseguiu compreender o que a soma acima representa? É uma soma de números naturais,</p><p>começando em 3, e sempre de 6 em 6. Assim, com um termo n=1  , temos que a soma é o primeiro</p><p>termo, isto é, 3=3⋅12 ; com dois termos n=2  , temos 39=12=3⋅22 ; com três termos n=3 ,</p><p>temos 3915=27=3⋅32 ; e assim por diante. Queremos verificar, que para qualquer quantidade n de</p><p>termos, a soma 3915...6n−3=3n2 . Note que 6n−3 é o n-ésimo termo da soma.</p><p>Devemos verificar a validade da fórmula acima por indução:</p><p>(Base de Indução) Verifiquemos que é válida para n=1. Temos que o primeiro termo da sequência é 3 e, por</p><p>outro lado, 312=3 . Logo, a propriedade é verdadeira, para n =1.</p><p>(Passo de Indução) Suponhamos que a propriedade se verifica para um número arbitrário k , k1 , isto</p><p>é, 23)36(...1593 kk =−++++ (hipótese de indução)</p><p>Vamos provar que a hipótese acima implica que a propriedade seja verdadeira para k+1, isto é, que</p><p>( ) 213)3)1(6(...1593 +=−+++++ kk , ou seja, ( ) 213)36(...1593 +=+++++ kk</p><p>Se adicionarmos 36 +k , nº que se segue ao 36 −k na sequência, aos dois membros da hipótese de</p><p>indução, fica-se com )36(336)36(...1593 2 ++=++−++++ kkkk , que é o mesmo que</p><p>( ) ,13)12(336)36(...1593 22 +=++=++−++++ kkkkk</p><p>como queríamos provar. Portanto, pode-se concluir, pelo Princípio da Indução Matemática, que a</p><p>proprifedade é válida ∀ n∈ℕ , n1 . J</p><p>Exercício 2: Vamos procurar uma fórmula fechada para a soma das frações abaixo:</p><p>1</p><p>1⋅2</p><p> 1</p><p>2⋅3</p><p> 1</p><p>3⋅4</p><p> 1</p><p>n⋅n1</p><p>.</p><p>Para n=1 , temos:</p><p>1</p><p>1⋅2</p><p>= 1</p><p>2</p><p>;</p><p>Para n=2 , temos:</p><p>1</p><p>1⋅2</p><p> 1</p><p>2⋅3</p><p>= 1</p><p>2</p><p> 1</p><p>6</p><p>= 31</p><p>6</p><p>= 4</p><p>6</p><p>= 2</p><p>3</p><p>;</p><p>Para n=3 , temos:</p><p>1</p><p>1⋅2</p><p> 1</p><p>2⋅3</p><p> 1</p><p>3⋅4</p><p>= 1</p><p>2</p><p> 1</p><p>6</p><p> 1</p><p>12</p><p>= 621</p><p>12</p><p>= 9</p><p>12</p><p>= 3</p><p>4</p><p>;</p><p>Para n=4 , temos:</p><p>1</p><p>1⋅2</p><p> 1</p><p>2⋅3</p><p> 1</p><p>3⋅4</p><p> 1</p><p>4⋅5</p><p>= 1</p><p>2</p><p> 1</p><p>6</p><p> 1</p><p>12</p><p> 1</p><p>20</p><p>= 301053</p><p>60</p><p>= 48</p><p>60</p><p>= 4</p><p>5</p><p>.</p><p>Ao que tudo indica, parece que o resultado da soma é sempre</p><p>n</p><p>n1</p><p>, mas como ter certeza deste</p><p>resultado? Como saber que nunca falhará? Para termos esta certeza, vamos usar a Indução Matemática.</p><p>Queremos então provar que, para qualquer natural n1 ,</p><p>1</p><p>1⋅2</p><p> 1</p><p>2⋅3</p><p> 1</p><p>3⋅4</p><p> 1</p><p>n⋅n1</p><p>= n</p><p>n1</p><p>.</p><p>Vejamos:</p><p>(1) (Base de Indução). Vamos verificar que a fórmula acima se verifica para n=1 . Sabemos que, para um</p><p>só termo, a soma é o próprio primeio termo, isto é,</p><p>1</p><p>2</p><p>. Por outro lado, substituindo-se n=1 em</p><p>n</p><p>n1</p><p>,</p><p>obtemos</p><p>1</p><p>11</p><p>= 1</p><p>2</p><p>, que é exatamente igual ao primeiro termo, como deveria mesmo ser.</p><p>(2) (Passo de Indução). Suponhamos, que, para certo valor k∈ℕ , k1 , a fórmula se verifique, isto é,</p><p>1</p><p>1⋅2</p><p> 1</p><p>2⋅3</p><p> 1</p><p>3⋅4</p><p> 1</p><p>k⋅k1</p><p>= k</p><p>k1</p><p>.</p><p>A mostrar: que se a proposição acima se verificar para k , também se verificará para k1 , ou seja,</p><p>1</p><p>1⋅2</p><p> 1</p><p>2⋅3</p><p> 1</p><p>3⋅4</p><p> 1</p><p>k⋅k1</p><p> 1</p><p>k1⋅k11</p><p>= k1</p><p>k2</p><p>.</p><p>Temos que:</p><p>[ 11⋅2  1</p><p>2⋅3</p><p> 1</p><p>3⋅4</p><p> 1</p><p>k⋅k1 ] 1</p><p>k1⋅k11</p><p>= k</p><p>k1</p><p> 1</p><p>k1⋅k11</p><p>=</p><p>=</p><p>k k21</p><p>k1k2</p><p>= k22k1</p><p>k1k2</p><p>=</p><p>k1k1</p><p>k1k2</p><p>= k1</p><p>k2</p><p>. Como queríamos demonstrar. Logo, o</p><p>Princípio da Indução garante que</p><p>1</p><p>1⋅2</p><p> 1</p><p>2⋅3</p><p> 1</p><p>3⋅4</p><p> 1</p><p>n⋅n1</p><p>= n</p><p>n1</p><p>, para todo n1 . J</p><p>Exercício 3: Vamos mostrar que 2n n2 , ∀ n5 .</p><p>Temos que ter cuidado com este tipo de sentença. Podemos ver que a sentença 2nn2 é verdadeira para</p><p>n=0 e n=1 , mas é falsa para n=2, 3 , 4 , e volta a ser verdadeira para n=5 . Veja a tabela:</p><p>n 2n n2 2nn2</p><p>0 1 0 V</p><p>1 2 1 V</p><p>2 4 4 F</p><p>3 8 9 F</p><p>4 16 16 F</p><p>5 32 25 V</p><p>6 64 36 V</p><p>O enunciado só afirma que é verdadeiro, para todo n5 . Vejamos agora o porquê disto, por indução</p><p>matemática.</p><p>(1) (Base de Indução) Vejamos que a sentença é verdadeira para n=5 . Temos que 2n=25=32 e</p><p>n2=52=25 e é verdadeiro que 3225 . Logo, 2nn2 para n=5 .</p><p>(2) (Passo de Indução) Suponhamos que para certo valor k∈ℕ , k5 , a sentença seja verdadeira, isto</p><p>é, que</p><p>2k  k 2 .</p><p>Vamos então mostrar que também será verdadeira a sentença para n=k1 , isto é, que também será</p><p>verdadeira a seguinte sentença: 2k1k12 . (Esta última sentença é que temos de provar).</p><p>Vejamos: temos que 2k1= 2k⋅21= 2⋅2k . Usando a hipótese que fizemos de que 2k  k 2 , teremos que</p><p>2k1= 2⋅2k 2⋅k2 .</p><p>Sabemos que 2 k 2= k 2k 2 . Precisaríamos então mostrar que k 22k1 . Por quê? Porque se</p><p>conseguirmos mostrar isto, então</p><p>2k1= 2⋅2k k 2 k 2k 22k1 = k12 ,</p><p>que é exatamente a sentença que queremos demonstrar.</p><p>Mas como vamos mostrar que k 22k1 ? Bom, vejamos o que podemos fazer. Temos que:</p><p>k22 k1 ⇔ k 2−2k 1 ⇔ k k−21 ,</p><p>mas isto é verdade, pois como k5 , então k−23 . Logo, o produto k k−2 com certeza é maior</p><p>ou igual a 5⋅3=15 , que é maior do que 1 . Portanto, k 22k1 , e isto completa o passo de indução.</p><p>Logo, o Princípio da Indução nos garante que 2n n2 , ∀ n5 . J</p><p>Exercício 4: 7n−2n é divisível por 5 , ∀n∈ℕ .</p><p>É sempre assim: uma sentença sobre os naturais não pode ser verificada, caso a caso, temos que mostrar</p><p>que ela é verdadeira para todos os infinitos números naturais, sem que seja, contudo, necessário verificar</p><p>um por um (isso sim é que é impossível!!!)</p><p>Vamos mostrar o resultado por indução:</p><p>(1)(Base de Indução) se queremos que a propriedade acima seja verdadeira para todos os número naturais,</p><p>começamos verificando para o menor deles, o zero. Temos que para n=0 , 70−20=1−1=0 , que é um</p><p>número divisível por 5 (note que 0=0×5 ; aliás, zero é divisível por qualquer número natural).</p><p>(2) (Passo de Indução) Suponhamos que para certo valor k∈ℕ , 7k−2k seja divisível por 5. Mas o que</p><p>isto quer dizer? Quer dizer que 7k−2k seja um múltilplo de 5, ou seja, 7k−2k=5m , para algum</p><p>m∈ℕ .</p><p>Vamos mostrar então, que ao supor isto como hipótese (que 7k−2k é múltiplo de 5), que também será</p><p>múltilplo de 5, o número 7k1−2k1 .</p><p>Como vamos mostrar isto?</p><p>Vejamos:</p><p>7k1−2k1= 7k⋅71−2k⋅21 = 7⋅7k −2⋅2k .</p><p>Precisamos de alguma forma por em evidência a expressão 7k−2k que, por nossa hipótese, é igual a</p><p>5m . Para isto, usamos que 7⋅7k = 52⋅7k = 5⋅7k 2⋅7k . No que isto vai ajudar? Veja na próxima</p><p>linha:</p><p>7k1−2k1= 7⋅7k −2⋅2k = 5⋅7k 2⋅7k−2⋅2k = 5⋅7k  27k−2k  = 5⋅7k  25m= 57k2m ,</p><p>o que mostra que o número 7k1−2k1 é um múltiplo de 5, como queríamos demonstrar.</p><p>Portanto, o Princípio da Indução nos garante que 7n−2n é divisível por 5 , ∀n∈ℕ . J</p><p>O Princípio da Indução já demonstrou que a sentença deste exercício, COM ABSOLUTA CERTEZA, é</p><p>verdadeira.</p><p>Mas, apenas para ilustrar (não serve como demonstração matemática), veja alguns cálculos da</p><p>expressão 7n−2n para certos valores de n .</p><p>n 7n−2n</p><p>0 1−1 = 0 = 0×5</p><p>1 7−2 = 5 = 1×5</p><p>2 49−4 = 45 = 9×5</p><p>3 343−8 = 335 = 67×5</p><p>4 2401−16= 2385 = 477×5</p><p>5 16807−32 = 16775 = 3355×5</p><p>Note que, de acordo com a demonstração feita por indução, para cada nova linha da tabela k1 o</p><p>múltiplo de 5 do resultado desta linha é sempre a potência de 7 da linha anterior 7k  mais duas vezes o</p><p>múltiplo de 5 da linha anterior m , onde 7k−2k=m⋅5 .</p><p>Por exemplo, o próximo número da tabela será 23517×5 , já que 16807 2⋅3355 = 23517 , onde</p><p>16807=75 (potência de 7 da última linha) e 3355 é o último múltiplo de 5 (o valor do m  .</p>