Exercícios de Indução em Matemática Discreta

Prévia do material em texto

Universidade Federal do Ceará - Campus de Quixadá 
Bacharelado em Engenharia de Software 
Matemática Discreta Prof. Wladimir Araújo Tavares 
Lista II – Indução 
1) Prove por indução que para n >= 0 e n  N, n2+ 3n é divisível por 2. 
2) Prove por indução que para n >=0 e n  N, n2+ n é divisível por 2. 
3) Demonstre por indução que 1*1! + 2*2! + ...+ n*n! = (n+1)! - 1 para todo n >=0. 
4) Demonstre por indução que para todo número inteiro positivo n, 
1*2 + 2*3 + 3*4+...+n(n+1) = n(n+1)(n+2)/3 
5) Encontre a falha da seguinte "demonstração"de que toda postagem de três centavos ou mais pode ser 
feita usando-se apenas selos de 3 e 4 centavos. 
Passo Base: Podemos fazer postagens de três centavos com apenas um selo de três centavos, e podemos 
fazer postagens de quatro centavos, usando um selo de quatro centavos. 
Passo de Indução: Assuma que podemos fazer postagens de j centavos para todos os números inteiros não 
negativos j com j <= k usando apenas selos de três e quatros centavos. Então, podemos fazer postagens de 
k+1 centavos substituindo um selo de três centavos por um selo de quatro centavos ou substituindo dois 
selos de quatro centavos por três selos de três centavos. 
6) Considere P(n) como a proposição que afirma que uma postagem de n centavos pode ser feita usando-
se apenas selos de 4 e 7 centavos. 
a) Mostre por indução matemática fraca que P(n) é verdadeira para n >= 18 
b) Mostre por indução matemática forte que P(n) é verdadeira para n >= 18 
7) Suponha que existe n pessoas em um grupo, cada um ciente de um escândalo que ninguém mais no 
grupo sabe. Essas pessoas comunicam-se por telefone; quando duas pessoas do grupo conversam, elas 
compartilham informações sobre todos os escândalos que cada uma sabe. Por exemplo, na primeira 
chamada, duas pessoas compartilham informações, assim, no final desta chamada, cada umas dessas 
pessoas sabe sobre dois escândalos. O problema da 
fofoca pergunta por G(n), o número mínimo de ligações telefônicas que são necessárias para que todas as 
n pessoas saibam sobre todos os escândalos. 
Use a indução para demonstrar que G(n) = 2n - 4 para n >= 4 
Caso Base n=4 
Inicialmente, cada pessoa sabe apenas um escândalo 
 
 
 
 
Com 4 ligações, todos podem saber os escândalos de todos. 
[Dica1: Faça n=5 e encontre as 6 ligações necessárias para compartilhar todos os escândalos] 
[Dica2: No passo de indução, coloque uma nova pessoa que liga para determinada pessoa no começo e no 
final] 
8) Dê um algoritmo recursivo para encontrar a soma dos primeiros n números inteiro positivos. 
9) Dê um algoritmo recursivo para encontrar o máximo de um conjunto finito de números inteiros, 
considerando o fato de que o máximo de n números inteiros é o maior entre o último inteiro da lista e o 
máximo dos primeiros n-1 números inteiros da lista. 
10) Desenvolva um algoritmo recursivo para computação de n
2
, em que n é um inteiro não negativo 
considerando o fato de que (n+1)
2
 = n
2
 + 2n + 1. Demonstre que esse algoritmo está correto