Matemática Discreta - Aplicações e Exercícios Resolvidos do Capítulo 4

ROSEN KH Matemática Discreta e Suas Aplicações 6ª Edição McGrawHill 2009 Capítulo 4 Seções 41 Exercícios propostos da Seção 41 28 m2 7m 12 0 Pm m4 P4 42 74 12 16 28 12 0 m k Pk k2 7k 12 0 m k1 Pk1 k12 7 k1 12 Pk1 k2 2k 1 7k 7 12 k2 5 k 6 Pk1 k2 7k 12 2k 6 Como assumimos Pk verdadeiro Pk1 0 2k 6 Pk1 0 2k 6 0 2k 6 é positivo para k 3 Pk1 0 Logo m2 7m 12 é mais negativo para m 3 30 Hm 1 12 13 1m m1 H1 H2 1 1 12 1 32 52 m1 Hm m 11 1 2 1 1 H1 H2 Hk k1 Hk k H1 H2 Hk Hk1 k1 Hk k Hk1 k1 Hk k 1 12 13 1k 1k1 k1 Hk Hk1 k k1 Hk k k1 k1 k1 Hk k 1 Usando o princípio de indução provamos que H1 H2 Hm m1 Hm é verdadeiro para todos os números inteiros m 32 m1 m3 2m 13 12 1 3 3 divide 3 Assumimos que 3 divide um m3 2m para algum número inteiro positivo k m3 2m 3m onde m é um número inteiro Demonstramos que 3 divide k13 2k1 k13 2k1 k3 3k2 3k 1 2k 2 k3 2k 3k2 3k 3 3m 3k2 3k 3 3m k2 k 1 m k2 k 1 é um inteiro portanto é divisível por 3 Mostramos que se 3 divide um m3 2m para m k então 3 também divide k13 2k1 Isso completa o passo da indução 34 m0 m3 m 03 0 0 m3 m 6m onde m é inteiro k13 k1 k13 k1 k3 3k2 3k 1 k 1 k3 3k2 2k 6m 3k2 2k 32m k2 2k 2m k2 2k é um inteiro portanto divisível por 3 6 divide um m3 m para m k então também divide k13 k1 Isso completa o passo da indução 36 m1 4m1 52m1 411 5211 42 51 16 5 21 4k1 52k1 21m onde m é um número inteiro 4k2 52k11 4 4k1 52k1 5 44k1 2552k1 421m 2521m 214m 25m 4m 25m é um número inteiro portanto divisível por 21 21 divide 4m1 52m1 para mk então 21 também divide 4k2 52k11 Isso completa o passo de indução 24 12m 1 3 5 2m12 4 6 2m Pm m1 P1 121 12 14 mk Pk 12k 1 3 5 2k12 4 6 2k m k1 Pk1 12k1 1 3 5 2k1 2 4 6 2k1 Pk1 Pk 2k12k2 Pk1 12k 1 3 5 2k1 2k1 2 4 6 2k 2k22k2 Pk1 é verdadeiro com base na suposição de indução Para qualquer n positivo 12n 1 3 5 2n12 4 6 2n é verdadeiro 26 am bm m am1 ab pm m1 a1 b1 1 a11 ab ab ab ab Pk ak bk k ak1 ab Pk1 ak1 bk1 k1 ak ab ak1 bk1 ab ak ak1 b ak2 b2 a bk1 bk ak1 bk1 ab k ak1 ab ak1 bk1 k ak 1 ak1 bk1 ab2 é crescente com a e b Como α b a podese substituir a por ab abk1 ab2 k abk1 abk ab k abk1 ak bk k abk1 Portanto m am1ab am bm 24 12m 135 2m1 246 2m Pm m 1 P1 121 12 14 m k Pk 12k 135 2k1 246 2k m k 1 Pk1 12k1 135 2k1 246 2k1 Pk1 Pk 2k1 2k2 Pk1 12k 135 2k1 246 2k 2k1 2k2 Pk1 é verdadeiro com base na suposição de indução Para qualquer m positivo 12m 135 2m1 246 2m é verdadeiro 26 am bm m am1 a b Pm m 1 a1 b1 1 a11 a b a b a b a b Pk ak bk k ak1 a b Pk1 ak1 bk1 k1 ak a b ak1 bk1 a b ak ak1 b ak2 b2 abk1 bk ak1 bk1 a b k ak1 a b ak1 bk1 k ak1 a b2 ak m bk1 a b2 é crescente com a e b Como ab a podese substituir a por a b a bk1 a b2 k a bk1 a bk a b k a bk1 ak bk k a bk1 Portanto m am1 a b am bm 28 m2 7m 12 0 Pm m 4 P4 42 74 12 16 28 12 0 m k Pk k2 7k 12 0 m k1 Pk1 k12 7k1 12 Pk1 k2 2k 1 7k 7 12 k2 5k 6 Pk1 k2 7k 12 2k 6 Como assumimos Pk verdadeiro Pk1 0 2k 6 Pk1 0 2k 6 0 2k 6 é positivo para k 3 Pk1 0 logo m2 7m 12 é mais negativo para m 3 30 Hm 1 12 13 1m m 1 H1 H2 1 1 12 1 32 52 m1Hm m 111 1 2 1 1 H1 H2 Hk k1Hk k H1 H2 Hk Hk1 k1Hk k Hk1 k1Hk k 1 12 13 1k 1k1 k1Hk Hk1 k k1Hk k k1 1k1 k1Hk k 1 Usando o principio de indução provamos que H1 H2 Hm m1Hm é verdadeiro para todos os números naturais m 32 m 1 m3 2m 13 21 3 3 divide 3 Assumimos que 3 divide um m3 2m para algum número inteiro positivo k m3 2m 3nm onde m é um número inteiro Demonstrando que 3 divide k13 2k1 k13 2k1 k3 3k2 3k 1 2k 2 k3 2k 3k2 3k 3 3nm 3k2 3k 3 3nm k2 k 1 nm k2 k 1 é um inteiro portanto é divisível por 3 Mostramos que se 3 divide um m3 2m para m k então 3 também divide k13 2k1 Isso completa os passos da indução 34 m 0 m3 m 03 0 0 m3 m 6m onde m é inteiro k13 k1 k3 3k2 3k 1 k 1 k3 3k2 2k 6m 3k2 2k 32m k2 2k 2m k2 2k é um inteiro portanto divisível por 3 6 divide m3 m para m k então também divide k13 k1 Isso completa os passos da indução 36 m 1 4m1 52m1 411 5211 42 51 16 5 21 4km 52k1 21nm onde m é um número inteiro 4k2 52k11 44k1 52k 15 44km 2552k15 421nm 2521nm 214nm 25nm 4nm 25nm é um número inteiro portanto divisível por 21 21 divide 4m1 52m1 para m k então 21 também divide 4k2 52k11 Isso completa os passos de indução