Lista de Exercícios Resolvidos - Técnicas de Demonstração em Matemática Discreta

MINISTÉRIO DA EDUCAÇÃO SECRETARIA DE EDUCAÇÃO PROFISSIONAL E TECNOLÓGICA INSTITUTO FEDERAL DO NORTE DE MINAS GERAIS IFNMG Criado pela Lei no 11892 de 29122008 Campus Pirapora Sistemas de Informação 3º Período Disciplina Matemática Discreta 012023 Profª Renata Fernandes Pereira Lista 4 Técnicas de Demonstração Data de Entrega 14072023 FORMATO FÍSICO Valor 20 pontos Alunoa 1 Mostre por indução que para qualquer n N a 0² 1² 2² n² 2n1n1n6 b 1 8 27 n³ 1 2 n² Dica Note que a segunda parte da igualdade do item b é constituída pelo quadrado de uma Progressão Aritmética de razão r 1 assim podemos escrever 1 2 n n1n2 Você deverá utilizar esta fórmula para resolver este exercício c 112 123 134 1nn1 nn1 2 Considere a função f Q Q definida por fx 1x A função f está bem definida Justifique sua resposta 3 Mostre que se x R e 2x 7 1 então x 4 4 Prove que se um triângulo tiver um ângulo medindo 100 graus então os outros dois ângulos são agudos 5 Prove que a soma de dois números racionais é um número racional 6 Suponha o conjunto universo 1 2 3 4 5 6 7 8101213 Determine o valorverdade V ou F de cada uma das seguintes proposições Dê exemplos para os casos verdadeiros e justifique os casos falsos com um contraexemplo a xyx 8 y 7 b xyx y é primo c yxx² y d xyx y 18 e x x² x f x x² x 7 Uma conjectura é uma ideia fórmula ou frase a qual não foi provada ser verdadeira baseada em suposições ou ideias com fundamento não verificado A conjectura a seguir é falsa ou verdadeira Se for verdadeira demonstrea Se for falsa dê um contraexemplo Conjectura A soma de dois números pares é um número par 1 Mostre por indução que para qualquer n N a 0² 1² 2² n² 2n1n1n6 Precisamos do Caso Base e do Caso indutivo Base Se n 0 temos 0² 2010106 Vale para n0 Se n 1 temos 0² 1² 1 21 11116 66 Vale para n1 Temos a base Vale para n0 e n1 Indução Suponha que vale para algum k N 0² 1² 2² k² 16 2k1k1k Somar k1² em ambos lados 0² 1² 2² k² k1² 16 2k1k1k k1² 16 k2k1k1 6k1² 16k1 2k1k 6k1 16 k1 2 k² 7k 6 16 k1 2k3k2 16 2k11 k11k1 Assim se vale para um k N vale para k1 conclui o passo indutivo Por indução finita vale para todo n N b 1 8 27 n³ 1 2 n² Usar que 1 2 3 n nn12 Base Se n1 1³ 1² OK Se n2 1³ 2³ 1 8 9 3² 12² OK Vale para n1 e para n2 Indução Suponha que vale para algum k N que 1³ 2³ 3³ k³ 1 2 3 k² então somar k1³ 1³ 2³ 3³ k³ k1³ kk12² k1³ k²k1² 4 k1³ k1² k²4 k1 k1² k² 4k 44 k1² k2² 2² k1 k11 2 ² 1 2 3 4 k k1² Assim se vale para um k N vale para k1 Por indução finita vale para todo k N 3 Mostre que se x R e 2x 7 1 então x 4 2x 7 1 2x 7 7 1 7 Propriedade a b a c b c abc R 2x 8 2x2 82 Propriedade a b ac bc ab R c 0 x 4 O conjunto dos racionais forma uma estrutura de corpo onde qualquer número tem inverso multiplicativo exceto o zero O zero é o único elemento não inversível e tentar definir um valor para a divisão por zero quebra a estrutura de corpo e de inverso 5 Prove que a soma de dois números racionais é um número racional Sejam xy Q Então existem ac Z e bd N com b 0 d 0 Tal que x ab e y cd Então x y ab cd ad bc bd Note que ad bc Z e bd N bd 0 pois b 0 e d 0 Assim ad bc bd Q logo x y Q Precisamos usar de hipótese Na geometria euclideana comum a soma dos ângulos internos em medidas em graus é sempre igual a 180 c 112 123 134 1nn1 nn1 Base n 1 112 111 OK n 2 112 123 12 16 46 23 221 OK Vale para n 1 e para n 2 Indução Se suppose que vale para algum k N a igualdade 112 123 1kk1 kk1 Soma 1k1k2 112 123 1kk1 1k1k2 kk1 1k1k2 kk2 1 k1k2 k2 2k 1 k1k2 k1k1 k1k2 k1k2 Logo se vale para algum k N então vale para k 1 Por indução finita vale para todo k N 6 Suponha o conjunto universo 1 2 3 4 5 6 7 8101213 Determine o valorverdade V ou F de cada uma das seguintes proposições Dê exemplos para os casos verdadeiros e justifique os casos falsos com um contraexemplo a V xyx 8 y 7 b F xyx y é primo c V yxx² y d F xyx y 18 e F xx² x f V xx² x Vamos usar a definição de número inteiro PAR Um número inteiro é dito par se ele pode ser escrito por 2n para algum n inteiro Um inteiro é dito ímpar se ele pode ser escrito por 2n1 para algum n inteiro Todo inteiro é ímpar ou par