Lista 1 Resolvida-2022 2

Campus de Quixad´a Universidade Federal do Cear´a Trabalho Matem´atica Discreta Prof. Lucas Ismaily 1º Semestre de 2022 Aluno: [ ] Matr´ıcula: [ ] Informac¸˜oes importantes: • O trabalho vale 10 pontos; • Caso n˜ao saiba responder uma quest˜ao, se vocˆe escrever “n˜ao sei” ganhar´a 10% da quest˜ao. Por exemplo, se uma quest˜ao vale 2 pontos, vocˆe receber´a 0, 2 d´ecimos; • Trabalho individual. Sejam honestos com vocˆes e comigo, por favor. Se for detectado qualquer tipo de fraude, os envolvidos receber˜ao nota zero. Note: os envolvidos receber˜ao zero, n˜ao importa se vocˆe foi a origem ou o destino, ambos receber˜ao nota zero. • O prazo de entrega ´e 07/12/2022. O trabalho poder´a ser entregue em vers˜ao digital pelo SIPPA ou manuscrito. Quest˜oes: 1. (1,0 ponto) Suponha que a e b sejam n´umeros inteiros ´ımpares, com a ̸= b. Mostre que h´a um ´unico n´umero inteiro c, tal que |a − c| = |b − c|. 2. (2,0 pontos) Fac¸a o que se pede. (a) Encontre uma f´ormula para 1 2 + 1 4 + 1 8 + ... + 1 2n examinando os valores dessa express˜ao para pequenos valores de n. (b) Demonstre a f´ormula que vocˆe conjecturou no item (a). 3. (1,0 ponto) Mostre que se a, b, k e m s˜ao n´umeros inteiros, tal que k ≥ 1, m ≥ 2 e a ≡ b(mod m), ent˜ao ak ≡ bk(mod m) sempre que k for um n´umero inteiro positivo. 4. (1,0 ponto) Mostre que se 2n − 1 ´e primo, ent˜ao n ´e primo. Dica: Use a identidade 2ab − 1 = (2a − 1).(2a(b−1) + 2a(b−2) + ... + 2a + 1). 1 5. (1,0 ponto) A sequˆencia de Fibonacci pode ser definida da seguinte maneira: f1 = 1 f2 = 1 fn = fn−1 + fn−2, ∀n ≥ 3 Mostre que a sequˆencia de Fibonacci satisfaz `a seguinte identidade: f1+f2+. . .+fn = fn+2 − 1. Dica: Substitua cada termo fi por fi+2 − fi+1. 6. (2,0 pontos) Suponha que P(n) seja uma func¸˜ao proposicional. Determine se para cada n´umero inteiro positivo n, a proposic¸˜ao P(n) deve ser verdadeira, e justifique sua resposta, se (a) P(1) for verdadeira; para todos os n´umeros inteiros positivos n, se P(n) for verdadeira, ent˜ao P(n + 2) ´e verdadeira. (b) P(1) e P(2) forem verdadeiros; para todos os n´umeros inteiros positivos n, se P(n) e P(n + 1) forem verdadeiras, ent˜ao P(n + 2) ´e verdadeira. (c) P(1) for verdadeira; para todos os n´umeros inteiros positivos n, se P(n) for verdadeira, ent˜ao P(2n) ´e verdadeira. (d) P(1) for verdadeira; para todos os n´umeros inteiros positivos n, se P(n) for verdadeira, ent˜ao P(n + 1) ´e verdadeira. 7. (1,0 ponto) Defina trˆes relac¸˜oes de equivalˆencia no conjunto de pr´edios de um campus universit´ario. Determine as classes de equivalˆencia para cada uma dessas relac¸˜oes de equivalˆencia. 8. (1,0 ponto) Suponha que uma relac¸˜ao R em A seja irreflexiva. A relac¸˜ao R2 ´e necessariamente irreflexiva? Dˆe uma raz˜ao para sua resposta. Uma relac¸˜ao R em A ´e irreflexiva se n˜ao cont´em pares da forma (a, a), onde a ∈ A. QUESTÃO 1 - a, b ∈ ℤ ímpares, a ≠ b. ∃! c ∈ ℤ, t.q.: |a-c| = |b-c|. EXISTÊNCIA c = \frac{a+b}{2} = \frac{(2p+1) + (2q+1)}{2} = \frac{2(p+q+1)}{2} = p+q+1 ∈ ℤ. Para a = 2p+1 e b = 2q+1, com p, q ∈ ℤ. (são ímpares) UNICIDADE |a-c| = |b-c| ⇅ a-c = b-c ou -(a-c) = b-c a = b ➔ (Absurd, temos como hipótese a ≠ b). c-a = b-c ➔ 2c = a+b c = \frac{a+b}{2} QUESTÃO 2 - a) \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ⋯ + \frac{1}{2^n} \sum_{k=1}^{n} \frac{1}{2^k} \frac{1}{2} + \frac{1}{4} = \frac{2+1}{4} = \frac{3}{4} = \frac{2^2-1}{2^2} \frac{1}{2^2} \frac{1}{2} + \frac{1}{4} + \frac{1}{8} = \frac{4+2+1}{8} = \frac{7}{8} = \frac{2^3-1}{2^3} \sum_{k=1}^{n} \frac{1}{2^k} = \frac{2^n-1}{2^n}. b) Por indução em n, BASE : n = 1 \frac{1}{2} = \frac{2^1-1}{2} Ok! HIPÓTESE INDUTIVA: \sum_{k=1}^{n} \frac{1}{2^k} = \frac{2^n-1}{2^n}. PASSO INDUTIVO: \sum_{k=1}^{n+1} \frac{1}{2^k} = \sum_{k=1}^{n} \frac{1}{2^k} + \frac{1}{2^{n+1}} = \frac{2^n-1}{2^n} + \frac{1}{2^{n+1}} = = \frac{2^{n+1}-1}{2^{n+1}}. QUESTÃO 3 - a, b, k, m ∈ ℤ, k ≥ 1, m ≥ 2, a ≡ b (mod m). ⇒ a^k ≡ b^k (mod m) (se k for inteiro positivo). (a^k - b^k) = (a-b)(a^{k-1} + a^{k-2}b + ⋯ + ab^{k-2} + b^{k-1}) Como a ≡ b (mod m), por definição, m | a-b. Logo, por (*), m | a^k-b^k a^k ≡ b^k (mod m). QUESTÃO 4 - 2^n - 1 primo ⇒ n primo. Suponha, por absurdo, que n não é primo. Logo, existem a,b∈ℤ +.q. n=ab. Logo, 2^{ab} - 1 = (2^a - 1) (2^{a(b-1)} + 2^{a(b-2)} +...+ 2^a +1) Logo, como 2^a - 1 | 2^{ab} - 1, 2^{ab} - 1 não é primo. Absurdo! QUESTÃO 5 - f_1 = 1 f_2 = 1 f_n = f_{n-1} + f_{n-2}, ∀n≥3. Por indução em n, BASE: n = 1 f_1 = 1 f_{1+2} - 1 = f_3 - 1 = (f_2 + f_1) - 1 = (1 + 1) - 1 = 1. Ok! HIPÓTESE INDUTIVA: f_1 + f_2 +...+ f_n = f_{n+2} - 1. PASSO INDUTIVO: f_1 + f_2 +...+ f_n + f_{n+1} = (f_{n+2} - 1) + f_{n+1} = = (f_{n+2} - 1) + (f_{n+3} - f_{n+2}) = f_{n+3} - 1. ↓ Usando que: f_i = f_{i+2} - f_{i+1} em f_{n+1}. ↓ Por f_n = f_{n-1} + f_{n-2} , f_{n-2} = f_n - f_{n-1} . Sendo i = n-2, logo n = i+2: f_i = f_{i+2} - f_{i+1} . QUESTÃO 6 - P(n) função proposicional. a) P(1) é verdadeira. ∀n, P(n) verdadeira ⇒ P(n+2) verdadeira. P(1) verdadeira ⇒ P(3) verdadeira ⇒ P(5) verdadeira ⇒ ... É verdadeiro para todo n ímpar. {1,3,5,...,2n+1,...} b) P(1) e P(2) verdadeiras. ∀n, P(n) e P(n+1) verdadeiros ⇒ P(n+2) verdadeiro. P(1) e P(2) verdadeiras ⇒ P(3) verdadeiro. P(2) e P(3) verdadeiras ⇒ P(4) verdadeiro. ... É verdade para todo n natural. ℕ. c) P(1) verdadeira. ∀n∈ℕ, P(n) verdadeira ⇒ P(2n) verdadeira. P(1) verdadeira ⇒ P(2) verdadeira ⇒ P(4) verdadeira⇒ P(8) verdadeira⇒ P(16) verdadeira ⇒ ... É verdadeira para {1,2,4,8,16,...,2^n,...}. d) P(1) verdadeira. ∀n∈ℕ, P(n) verdadeira ⇒ P(n+1) verdadeira. Indução matemática. P(1) verdadeira ⇒ P(2) verdadeira ⇒ P(3) verdadeira ⇒ ... É verdade para todo n natural. N. QUESTÃO 7 - • ∼C : PRÉDIO A É EQUIVALENTE A PRÉDIO B SE ELES PERTENCEM AO MESMO CENTRO DE ENSINO. Exemplo: Prédio da Matemática ∼C Prédio da Física, pois Matemática e Física pertencem ao Centro de Ciências. ClASSES DE EQUIVALÊNCIA: [Ciências], [Tecnologia], [Humanidades], [Ciências Agrárias], [Cultura e Artes], [Educação]. • ∼P : PRÉDIO A É EQUIVALENTE A PRÉDIO B SE ELES SÃO DA MESMA COR. Exemplo: Prédio 331 ∼C Prédio 401, pois ambos são azul. ClASSES DE EQUIVALÊNCIA: AS CORES DOS PRÉDIOS. • ∼D : PRÉDIO A É EQUIVALENTE A PRÉDIO B SE OS PRÉDIO PERTEN- CEM AO MESMO CURSO. Exemplo: Prédio 408 ∼D Prédio 410, pois ambos são da Estatística. ClASSES DE EQUIVALÊNCIA: Os cursos do campus. QUESTÃO 8 - R em A relação irreflexiva. ∀a∈A, (a,a) ∉ R. Para R², não é necessariamente irreflexiva. Exemplo: A = {a,b,c}. R = {(a,b), (b,a)} R² = {(a,a), (b,b)} ↳ R² é reflexiva!