Lista de Exercicios Resolvidos - Indução Matemática - Matemática Discreta

Material Obrigatório ROSEN KH Matemática Discreta e Suas Aplicações 6ª Edição McGrawHill 2009 Capítulos Capítulo 2 Seções 21 e 22 páginas 111 a 133 e Capítulo 4 Seções 41 e 42 páginas 263 a 288 12 Use a indução completa para mostrar que todo número inteiro positivo n pode ser escrito como uma soma de potências distintas de dois ou seja como uma soma de um subconjunto de números inteiros 20 1 21 2 22 4 e assim por diante Dica Para o passo de indução considere separadamente o caso em que k 1 é par e em que ele é ímpar Quando for par note que k 12 é um número inteiro 14 Suponha que você comece com uma pilha de n pedras e dividaa em n pilhas com uma pedra cada separando sucessivamente uma pilha de pedras em duas menores Cada vez que você faz a divisão multiplica o número de pedras em cada uma das pilhas menores formadas para que elas tenham r e s pedras respectivamente você computa rs Mostre que não importa como você separa as pilhas a soma dos produtos computados em cada etapa é igual a nn 12 29 O que há de errado com esta demonstração por indução completa Teorema Para todo número inteiro não negativo n 5n 0 Passo Base 5 0 0 Passo de Indução Suponha que 5j 0 para todos os números inteiros não negativos j com 0 j k Escreva k 1 i j em que i e j são números naturais menores que k 1 Pela hipótese indutiva 5k 1 5i j 5i 5j 0 0 0 33 Mostre que podemos demonstrar que Pn k é verdadeira para todos os pares de números inteiros positivos n e k se mostrarmos que a P1 1 é verdadeira e Pn k Pn 1 k Pn k 1 é verdadeira para todos os números inteiros positivos n e k b P1 k é verdadeira para todos os números inteiros positivos k e Pn k Pn 1 k é verdadeira para todos os números inteiros positivos n e k c Pn 1 é verdadeira para todos os números inteiros positivos n e Pn k Pn k 1 é verdadeira para todos os números inteiros positivos n e k 41 Mostre que a propriedade da boa ordenação pode ser demonstrada quando o princípio da indução matemática for tido como axioma 1 n 1 Você pode correr 1 km n 2 Você pode correr 2 km Supondo que pode correr um número de km K 1 e sempre pode correr mais 2 km então você pode correr k1 km apenas parando num passo anterior e também pode k2 km 3 a Para P8 um selos de 5 centavos e outro de 3 centavos Para P9 e selos de 3 centavos Para P10 2 selos de 5 centavos P8 P9 e P10 são verdadeiras b Assumindo que Pk é verdadeiro para algum valor k 10 Ou seja assumimos que é possível lançar k centavos usando apenas selos de 3 e 5 centavos c Precisamos mostrar que com base na hipótese indutiva podemos provar que Pk1 é verdadeiro d Passo de indução Se já usamos pelo menos um selo de 5 centavos na postagem de k centavos podemos substituir esse selo por dois selos de 3 centavos resultando em uma postagem de k1 centavos e A indução para k10 é verdadeira e P8 P9 e P10 foram verificadas no passo base 12 Quando n1 1 20 A afirmação é verdadeira Supondo agora que a afirmação seja verdadeira quando n j 1 j k 1 Caso k 1 é um inteiro positivo ímpar Pela suposição k pode ser escrito como soma de potências distintas de dois Então k1 pode ser escrito como que é a soma de distintos potências de dois 2 Caso k 1 é par é um número inteiro positivo par e Uma vez que todas as potências são distintas então todos as potências em também serão distintas 29 A suposição de que 5j0 é falsa pois j pode assumir valores que quando multiplicados por 5 não geram 0 Portanto a suposição está incorreta 33 P1 1 é verdadeiro Pn k Pn 1 k Pn k 1 é verdadeiro para todos os inteiros positivos n e k P1 k é verdadeiro para todos os inteiros positivos k Pn k Pn1 k é verdadeiro para todos os inteiros positivos n e k Pn 1 é verdadeiro para todos os inteiros positivos n Pn k Pn k 1 é verdadeiro para todos os inteiros positivos n e k Pn k é verdadeiro para todos os pares de inteiros positivos n e k quando n 1 ou k 1 Pn k é verdadeiro para qualquer par de inteiros positivos n e k então Pn k também é verdadeiro para todos os pares de inteiros positivos n1 e k1 Pn k é verdadeiro para todos os pares de inteiros positivos n e k 41 Qualquer subconjunto não vazio dos números naturais possui um elemento mínimo Considerando o subconjunto A de números naturais Assumindo o princípio da indução como axioma Considere um subconjunto A de números naturais Como o conjunto não está vazio ele deve conter pelo menos um número natural Portanto possui um elemento mínimo que é o menor número n pertencente a A Suponha que o princípio da boa ordenação seja válido para todos os subconjuntos que possuam menos do que k elementos onde k é um número fixo Considerando um subconjunto B com k elementos naturais há duas possibilidades O conjunto B contém o número 0 Nesse caso o elemento 0 é o menor elemento de B e o princípio de boa ordenação se aplica O conjunto B não contém o número 0 Podemos considerar o conjunto B 1 ou seja o conjunto B com o elemento 1 removido O conjunto resultante B 1 tem no máximo k 1 elementos Pela hipótese de indução o conjunto B 1 tem um elemento mínimo digamos m Então o elemento m é o menor elemento do conjunto B