Trabalho 3 FMC

Prévia do material em texto

UFG - Instituto de Informática Fundamentos de Matemática para Computação
CC/ES/SI Prof.a Erika Coelho1 Prof. Julliano Nascimento2
3o Trabalho – 2017.2
Data de entrega: 06/12/2017
Ordens Parciais, Funções e Indução matemática
1. (a) Encontre uma fórmula para:
1
1 · 2
+
1
2 · 3
+ · · ·+
1
n · (n+ 1)
examinando os valores dessa expressão para pequenos valores de n.
Para encontrar a resposta, você deve testar para alguns valores de n, por exemplo:
• Para n = 1, temos que 11·2 =
1
2
• Para n = 2, temos que 11·2 +
1
2·3 =
1
2 +
1
6 =
4
6 =
2
3
• Para n = 3, temos que 11·2 +
1
2·3 +
1
3·4 =
1
2 +
1
6 +
1
12 =
9
12 =
3
4
• . . .
(b) Demonstre a fórmula que você conjecturou no item (a).
2. A partir de que inteiro positivo a desigualdade seguinte é válida?
2n ≤ n!
3. Usando a indução, mostre a validade do item anterior.
4. Use a indução matemática para demonstrar que as proposições abaixo são verdadeiras.
(a) 1 · 1! + 2 · 2! + · · ·+ n · n! = (n+ 1)!− 1, para todo n ≥ 1.
(b) n2 − 5 · n+ 3 > 0, para todo n ≥ 5.
(c)
n∑
i=1
1
(2·i−1)·(2·i+1) =
n
2·n+1 para todo n ∈ N∗.
(d) 42·n+1 + 3n+2 é divisível por 13 para todo n ∈ N.
5. Para que valores de n ≥ 0, 2n+1 ≥ n2 + 2? Se for válida para todo n, prove usando indução matemática. Se não
for, mostre um contraexemplo.
6. Demonstre, por indução matemática, 42n+1 + 3n+2 é divisível por 13 para todo n ∈ N.
7. Seja A = {0, 2, 3, 4, 6, 8, 9, 10, 25}. Considere o conjunto parcialmente ordenado (A, |). Responda as questões:
(a) Liste todos os pares ordenados da relação R.
(b) Desenhe o diagrama de Hasse para R no conjunto S.
(c) Encontre os elementos maximais.
(d) Encontre os elementos minimais.
(e) Indique, caso exista, o elemento máximo.
(f) Indique, caso exista, o elemento mínimo.
(g) Indique quais são os pares de elementos não comparáveis.
8. Mostre as seguintes afirmações:
(a) 5 · n3 − 32 · n2 + 3 · n− 7 é O(n3).
(b) 2 · n2 + 1 não é O(n).
(c) lgn é O(logn).
(d) Se f(n) é O(g(n)) e g(n) é O(h(n)), então f(n) é O(h(n)).
1e-mail: erikamorais@inf.ufg.br
2e-mail: julliano@inf.ufg.br