Lista de Exercícios Resolvida: Sequências e Indução Matemática - UFMG

Lista de Exercícios 4 Soluções Sequências e Indução Matemática UFMGICExDCC DCC111 Matemática Discreta Ciências Exatas Engenharias 2o Semestre de 2014 1 O conjunto dos números racionais Q é enumerável ou seja é possível atribuir associar a cada número racional um número natural Abaixo os números racionais positivos estão representados na forma de um par ordenado onde o primeiro número representa o numerador e o segundo o denominador Começando do número racional 1 par ordenado 1 1 é possível associar o número natural 1 e seguindo o sentido das setas atribuir o próximo número natural definindo assim uma sequência de enumeração Dado o número racional positivo p q qual é o número natural correspondente 1 6 2 6 3 6 4 6 5 6 6 6 1 5 2 5 3 5 4 5 5 5 6 5 1 4 2 4 3 4 4 4 5 4 6 4 1 3 2 3 3 3 4 3 5 3 6 3 1 2 2 2 3 2 4 2 5 2 6 2 1 12 1 3 14 1 5 16 1 Resposta De acordo com o enunciado acima a enumeração dos números racionais irá ocorrer da forma apresentada a seguir o número natural associado a cada número racional está entre colchetes 1 6 2 6 3 6 4 6 5 6 6 6 21 1 5 2 5 3 5 4 5 5 5 6 5 11 20 1 4 2 4 3 4 4 4 5 4 6 4 10 12 19 1 3 2 3 3 3 4 3 5 3 6 3 4 9 13 18 1 2 2 2 3 2 4 2 5 2 6 2 3 5 8 14 17 1 12 1 3 14 1 5 16 1 1 2 6 7 15 16 1a 2a 3a 4a 5a 6a Diagonais Pontos a observar O número racional positivo p q é representado pelo par ordenado p q 1 A soma dos índices p e q dos pares ordenados ao longo de cada diagonal é a mesma Na primeira diagonal temos apenas um par ordenado ie 1 1 e a soma vale 2 A partir da segunda diagonal as somas dos índices valem 3 4 5 etc Na primeira diagonal temos um par ordenado na segunda dois na terceira três e assim sucessivamente Isso significa que em cada diagonal temos p q 1 pares ordenados Quando a soma p q é um número ímpar a enumeração ocorre de baixo para cima e quando é par ocorre de cima para baixo Para calcular o número natural k associado ao número racional p q temos que saber quantos pares ordenados existem nas diagonais anteriores à diagonal onde se encontra o par p q Essa é a soma de 1 a p q 2 representada por S S p q 2 p q 1 2 Finalmente devese determinar o sentido da enumeração de baixo para cima ou viceversa para o par p q se p q mod 2 0 p q é um número par ie a diagonal é de descida então k S p Sim devemos somar a S o valor de p que é o termo que cresce senão k S q Não devemos somar a S o valor de q que é o termo que cresce fimse Observe que quando o sentido da enumeração é de cima para baixo ao longo da diagonal o número p deve ser somado a S para determinar a posição correta da enumeração Quando o sentido da enumeração for o contrário o número q deve ser somado 2 Prove por indução matemática que 12 22 n2 nn 12n 1 6 n 1 Resposta Prova por indução matemática a Passo base Para n 1 12 1 e nn12n1 6 123 6 1 O passo base é verdadeiro b Passo indutivo se a fórmula é verdadeira para n k k 1 então deve ser verdadeira para n k1 Hipótese indutiva 12 22 k2 kk 12k 1 6 k 1 Devese mostrar que 12 22 k2 k 12 k 1k 22k 3 6 Sabese que 12 22 k2 k 12 kk 12k 1 6 k 12 kk 12k 1 6k 12 6 k 1k2k 1 6k 1 6 k 12k2 k 6k 6 6 k 12k2 7k 6 6 k 1k 22k 3 6 2 3 Prove por indução matemática que 1 3 5 2n 1 n2 n 1 Resposta Prova por indução matemática a Passo base Para n 1 1 12 O passo base é verdadeiro b Passo indutivo se a fórmula é verdadeira para n k k 1 então deve ser verdadeira para n k1 Hipótese indutiva 1 3 5 2k 1 k2 k 1 Devese mostrar que 1 3 5 2k 1 2k 1 k 12 k 1 Sabese que 1 3 5 2k 1 2k 1 k2 2k 1 k 12 4 Prove por indução matemática que 13 23 n3 1 2 n2 n 1 Resposta Essa prova pode ser dividida em duas partes i prova do somatório do lado direito e substituição pela fórmula fechada e ii prova do somatório do lado esquerdo Sabese que a soma 1 2 n n 1 vale nn1 2 esta prova pode ser obtida por indução matemática Assim temos que 13 23 n3 n2n 12 4 n 1 Prova por indução matemática a Passo base Para n 1 13 12112 4 O passo base é verdadeiro b Passo indutivo se a fórmula é verdadeira para n k k 1 então deve ser verdadeira para n k1 Hipótese indutiva 13 23 k3 k2k 12 4 k 1 Devese mostrar que 13 23 k3 k 13 k 12k 22 4 k 1 Sabese que 13 23 k3 k 13 k2k 12 4 k 13 k2k 12 4 k 1k 12 k2k 12 4 4k 1k 12 4 k 12k2 4k 4 4 k 12k 22 4 3 5 Prove por indução matemática que 2122232n n²n n 1 Resposta Prova por indução matemática a Passo base Para n 1 21 2 e 1² 1 2 O passo base é verdadeiro b Passo indutivo se a fórmula é verdadeira para n k k 1 então deve ser verdadeira para n k1 Hipótese indutiva 2122232k k²k kk1 k 1 Devese mostrar que 21222k2k1 k1²k1 k1k11 k1k2 k 1 Sabese que 21222k2k1 kk12k1 k²k2k2 k²3k2 k1k2 6 Prove por indução matemática que Σi1 n1 ii1 nn1n13 inteiros n 2 Resposta Prova por indução matemática a Passo base Para n 2 Σi1 n1 ii1 Σi1 1 ii1 111 2 e nn1n13 2133 2 O passo base é verdadeiro b Passo indutivo se a fórmula é verdadeira para n k k 2 então deve ser verdadeira para n k1 Hipótese indutiva Σi1 k1 ii1 kk1k13 Devese mostrar que Σi1 k ii1 kk1k23 Sabese que Σi1 k ii1 Σi1 k1 ii1 kk1 kk1k13 kk1 kk1k1 3kk13 kk1k133 kk1k23 7 Ache a fórmula fechada para a soma 112 123 134 1nn1 inteiros n 1 e prove o seu resultado por indução matemática Resposta Prova por indução matemática Somando os primeiros termos e simplificando temos que 112 123 23 112 123 134 34 112 123 134 145 45 o que leva a conjectura que para todos os inteiros positivos n 112 123 134 1nn1 nn1 a Passo base Para n 1 112 12 que é o valor da fórmula fechada O passo base é verdadeiro b Passo indutivo se a fórmula é verdadeira para n k k 1 então deve ser verdadeira para n k1 Hipótese indutiva 112 123 134 1kk1 kk1 Devese mostrar que 112 123 134 1kk1 1k1k2 k1k2 Sabese que 112 123 134 1kk1 1k1k2 kk1 1k1k2 kk21k1k2 k²2k1k1k2 k1²k1k2 k1k2 8 Ache a fórmula fechada para o produto 1 121 131 141 1n inteiros n 2 e prove o seu resultado por indução matemática Resposta Seja a suposição que 1 121 131 141 1n Πi2 n1 1i 1n inteiros n 2 Devese provar que de fato essa suposição é verdadeira Prova por indução matemática a Passo base Para n 2 Πi2 21 1i 1 12 12 e a fórmula fechada vale 12 O passo base é verdadeiro b Passo indutivo se a fórmula é verdadeira para n k k 2 então deve ser verdadeira para n k1 Hipótese indutiva 1 121 131 141 1k Πi2 k1 1i 1k Devese mostrar que 1 121 131 141 1k1 1k1 Πi2 k11 1i 1k1 Sabese que Πi2 k11 1i Πi2 k1 1i1 1k1 1k1 1k1 1kk11k1 1k1 9 Ache a fórmula fechada para a soma 113 135 12n12n1 inteiros n 1 e prove o seu resultado por indução matemática Resposta Seja a suposição que 113 135 12n12n1 n2n1 inteiros n 1 Prova por indução matemática a Passo base Para n 1 12n12n1 1211211 13 13 e a fórmula fechada vale 1211 13 O passo base é verdadeiro b Passo indutivo se a fórmula é verdadeira para n k k 1 então deve ser verdadeira para n k1 Hipótese indutiva 113 135 12k12k1 k2k1 Devese mostrar que 113 135 12k112k11 k12k11 ou equivalentemente 113 135 12k12k3 k12k3 Sabese que 113 12k12k1 12k12k3 k2k1 12k12k3 k2k32k12k3 12k12k3 2k²3k12k12k3 2k1k12k12k3 k12k3 10 Ache a fórmula fechada para a soma Σi2 to n 1i1i inteiros n 2 e prove o seu resultado por indução matemática Resposta Seja a suposição que Σi2 to n 1i1i 1 1n inteiros n 2 Devese provar que de fato essa suposição é verdadeira Prova por indução matemática a Passo base Para n2 os dois lados da equação valem 12 O passo base é verdadeiro b Passo indutivo se a fórmula é verdadeira para nk k 2 então deve ser verdadeira para nk1 Hipótese indutiva Σi2 to k 1i1i 1 1k k 2 Devese mostrar que Σi2 to k1 1i1i 1 1k1 k 2 Sabese que Σi2 to k1 1i1i Σi2 to k 1i1i 1kk1 1 1k 1k 1k1 1 1k1 11 Prove o seguinte predicado Pn usando indução matemática Pn Qualquer número inteiro positivo n 8 pode ser escrito como a soma de 3s e 5s Resposta Prova por indução matemática fraca a Passo base Pn0 P8 Para n0 8 temos que 8 3 5 e o predicado P é verdadeiro b Passo indutivo se a fórmula é verdadeira para n k então deve ser verdadeira para n k 1 ie Pk Pk 1 Suponha que a fórmula seja verdadeira para n k ie Pk k 3a 5b para a 0 e b 0 hipótese indutiva Devese mostrar que Pk 1 k 1 3a 5b para a 0 e b 0 Dois casos a considerar para k 1 i b 0 É possível substituir um 5 por dois 3s quando é feita a soma de k 1 3a 5b 1 3a 5b 1 5 1 3a 23 5b 1 3a 5b ii b 0 Neste caso deve haver pelo menos três 3s para termos valores de n 9 Assim temos k 1 3a 1 3a 3 33 1 3a 25 3a 5b Isto era o que devia ser provado 12 Suponha que temos selos de 4 e 7 centavos Prove que é possível ter qualquer valor de postagem de 18 centavos ou mais usando somente esses selos Resposta Prova por indução matemática forte a Passo base Para os seguintes valores de postagem p é possível usar apenas selos de 4 e 7 centavos p Selos 18 7 7 4 19 7 4 4 4 20 4 4 4 4 4 21 7 7 7 Assim o passo base é verdadeiro b Passo indutivo Vamos supor que para todos inteiros p 18 p k p seja um valor de postagem que pode ser obtido apenas com selos de 4 e 7 centavos Vamos provar que a proposição também é verdadeira para k Ao dividirmos k por 4 temos um quociente q e um resto entre 0 e 3 Ao dividirmos os valores de postagem p 18 21 temos também como resto os valores entre 0 e 3 Ou seja k pode ser expresso como um valor de postagem p entre 18 e 21 somando de um fator múltiplo de 4 Formalmente temos que k p mod 4 para um valor de p 18 21 Isto é lido como k é congruente com p módulo 4 o que significa que existe um valor de p 18 21 que quando dividido por 4 deixa o mesmo resto que k quando dividido por 4 8 13 Prove por indução matemática que n2 2n para todos inteiros n 5 Resposta Prova por indução matemática a Passo base Para n 5 a desigualdade 52 25 é verdadeira Assim o passo base é verdadeiro b Passo indutivo se a afirmação é verdadeira para n k k 5 então deve ser verdadeira para n k 1 Hipótese indutiva k2 2k para todos inteiros k 5 Devese mostrar que k 12 2k1 para todos inteiros k 5 Sabese que k 12 k2 2k 1 2k 2k 1 pela hipótese indutiva Sabese também que 2k 1 2k para k 3 Colocando estas desigualdades juntas temos k 12 2k 2k 1 2k 2k 14 Seja a seqüência a1 a2 a3 definida como a1 3 ak 7ak1 inteiros k 2 Prove por indução matemática que an 3 7n1 para todos os inteiros n 1 Resposta Prova por indução matemática a Passo base Para n 1 an a1 3 711 3 1 3 O passo base é verdadeiro b Passo indutivo se a afirmação é verdadeira para n k k 1 então deve ser verdadeira para n k 1 Hipótese indutiva ak 3 7k1 para todos inteiros k 1 Devese mostrar que ak1 3 7k11 3 7k para todos inteiros k 1 Sabese que ak1 7ak inteiros k 2 7 3 7k1 Hipótese indutiva 3 7k 15 Seja a seqüência a1 a2 a3 definida como a1 1 a2 3 ak ak2 2ak1 inteiros k 3 Prove por indução matemática que an é ímpar para todos os inteiros n 1 Resposta Prova por indução matemática forte 9 a Passo base A propriedade é verdadeira para n 1 e n 2 já que a1 1 e a2 3 que são ímpares b Passo indutivo Se k 2 e a propriedade é verdadeira para todos i 1 i k então deve ser verdadeira para n k Hipótese indutiva Seja k 2 um inteiro e suponha que ai é ímpar para todos os inteiros i 1 i k Devese mostrar que ak é ímpar Sabese pela definição de a1 a2 a3 an ak2 2ak1 Sabese também que ak2 é ímpar pela hipótese indutiva já que 1 k 2 k e k 2 e 2ak1 é par pela definição de número par Assim ak2 2ak1 é a soma de um número ímpar e um número par que dá como resultado sempre um número ímpar 16 Seja a seqüência g0 g1 g2 definida como g0 12 g1 29 gk 5gk1 6gk2 inteiros k 2 Prove por indução matemática que gn 5 3n 7 2n para todos os inteiros n 0 Resposta Prova por indução matemática forte a Passo base Para n 0 temos que g0 5 30 7 20 5 1 7 1 12 e para n 1 temos que g1 5 31 7 21 5 3 7 2 29 Logo o passo base é verdadeiro b Passo indutivo Se k 1 e a propriedade é verdadeira para todos i 1 i k então deve ser verdadeira para n k Hipótese indutiva Seja k 1 um inteiro e suponha que gk 5 3k 7 2k para todos os inteiros i 1 i k Devese mostrar que gk 5 3k 7 2k para n k Sabese que gk 5gk1 6gk2 55 3k1 7 2k1 65 3k2 7 2k2 25 3k1 35 2k1 30 3k2 42 2k2 3k225 3 30 2k235 2 42 3k2 45 2k2 28 3k29 5 2k24 7 5 3k 7 2k 17 Seja a seqüência h0 h1 h2 definida como h0 1 h1 2 h2 3 hk hk1 hk2 hk3 inteiros k 3 Prove por indução matemática que hn 3n para todos os inteiros n 0 Resposta Prova por indução matemática forte 10 a Passo base A propriedade é verdadeira para n hn 3n 0 h0 1 30 1 1 h1 2 31 3 2 h2 3 32 9 b Passo indutivo Se k 2 e a propriedade é verdadeira para todos i 1 i k então deve ser verdadeira para n k Hipótese indutiva Seja k 2 um inteiro e suponha que hi 3i para todos os inteiros i 1 i k Devese mostrar que hk 3k Sabese pela definição de hk hk1 hk2 hk3 Sabese também que hk1 3k1 hk2 3k2 hk3 3k3 Logo hk hk1 hk2 hk3 3k1 3k2 3k3 3k332 31 1 3k33 4 4 3k2 3k já que 4 32 18 Seja a seqüência x0 x1 x2 definida como x0 0 x1 1 xk 5x3 k1 7xk2 inteiros k 2 Prove por indução matemática que se k é múltiplo de 3 então xk é par Resposta Prova por indução matemática forte a Passo base Ao observarmos essa sequência temos i xi Número 0 0 par 1 1 ímpar 2 5 13 7 1 5 ímpar 3 5 53 7 0 632 par Para os índices 0 e 3 múltiplos de 3 a proposição está correta e assim o passo base é verdadeiro Se continuarmos a calcular os próximos valores de xi veremos que ambos x4 e x5 sáo números ímpares e x6 é par b Passo indutivo Se k 2 e a propriedade é verdadeira para todos i 1 i k então deve ser verdadeira para n k 11 Hipótese indutiva seja k 3k ou seja k é um múltiplo de 3 Os números x3k1 e x3k2 são ímpares Devese mostrar que x3k é par Sabese que x3k 5x3k1³ 7x3k2 O primeiro termo terá como resultado um número ímpar já que x3k1 é ímpar que quando elevado a uma potência cúbica multiplicado por um fator ímpar fornece um número ímpar O segundo termo terá como resultado um número ímpar já que x3k2 é ímpar que quando multiplicado por um fator ímpar fornece um número ímpar Assim como x3k é o resultado da soma de dois números ímpares temos que x3k é par 19 Seja a sequência a₀ a₁ a₂ definida como a₀ 0 a₁ 0 ak ak1 3k k1 inteiros k 2 Ache a fórmula fechada para o késimo termo e prove por indução matemática Resposta Ao observarmos essa sequência temos i ai 0 0 1 0 2 013² 3 13²23³ 4 13²23³33⁴ ou seja o termo ak Σi2 to k i13i Σi2 to k i3i Σi2 to k 3i Calcule essa soma sabendo que Σi0 to n1 ixi x nxn n1xn11x² Dica transforme a soma Σi0 to n1 ixi em uma soma Σi2 to n ixi ou seja acrescente o termo para in e remova os termos para i0 e i1 20 Seja a sequência a₀ a₁ a₂ definida como a₀ 0 a₁ 1 ak k ak1 inteiros k 1 Ache a fórmula fechada para o késimo termo e prove por indução matemática Resposta Ao observarmos essa sequência temos i ai 0 0 1 1 2 211 3 312 4 422 5 523 6 633 7 734 8 844 ou seja o termo ak k2 Se k é par então ak k2 se k é ímpar então ak k12 Prova por indução matemática forte a Passo base A propriedade é verdadeira para i08 b Passo indutivo Se k 2 e a propriedade é verdadeira para todos i 0 i k então deve ser verdadeira para n k Hipótese indutiva Se i é par então ai i2 se i é ímpar então ai i12 para 0 i k Devese mostrar que essa proposição é verdadeira para k Sabese que ak k ak1 Temos dois casos i k é par ak k ak1 k k2 já que k1 é ímpar e ak1 k112 ii k é ímpar ak k ak1 k k2 k12 já que k1 é par e ak1 k2 21 Prove por indução matemática que n 1 3n 2 é ímpar Resposta Prova por indução matemática a Passo base Para n1 3¹ 2 1 é ímpar O passo base é verdadeiro b Passo indutivo se a afirmação é verdadeira para nk k 1 então deve ser verdadeira para n k1 Hipótese indutiva k 1 3k 2 é ímpar Devese mostrar que 3k1 2 é ímpar Sabese que 3k1 2 3 3k 2 3 3k 6 4 33k 2 4 Pela hipótese indutiva 3k 2 é um número ímpar que quando multiplicado por 3 e somado com 4 continua sendo um número ímpar