Exercícios - Recorrência - 2022-1

Matemática Discreta 2022/1 Prof. Fabrício Carvalho Relações de Recorrência 1. Com base na sequência de Fibonacci, prove que: F(n + 1) + F(n – 2) = 2 F(n) para n ≥ 3 2 Relações de Recorrência 2. Com base na sequência de Fibonacci, prove que: F(n) = 5 F(n – 4) + 3 F(n – 5) para n ≥ 6 3 Relações de Recorrência 3. Com base na sequência de Fibonacci, prove que: F(2) + F(4) + ··· + F(2n) = F(2n + 1) – 1 para n ≥ 1 4 Relações de Recorrência 4. A sequência de Lucas é definida por ● L(1) = 1 ● L(2) = 3 ● L(n) = L(n – 1) + L(n – 2) para n ≥ 2 a. Escreva os cinco primeiros termos da sequência. b. Prove que L(n) = F(n + 1) + F(n – 1) para n ≥ 2, em que F é a sequência de Fibonacci. 5 Relações de Recorrência 5. Uma sequência é definida por recorrência por ● S(1) = 2 ● S(2) = 2 ● S(3) = 6 ● S(n) = 3 S(n – 3) para n ≥ 4 Prove que S(n) é um número par para n ≥ 1. 6 Relações de Recorrência 6. Uma sequência é definida por recorrência por ● T(5) = 6 ● T(6) = 10 ● T(n) = 2T(n – 2) + 2 para n ≥ 7 Prove que T(n) ≥ 2 n para n ≥ 7. 7 Relações de Recorrência 7. Em um experimento, determinada colônia de bactérias tem uma população inicial de 50.000. A população é contada a cada 2 horas, e, ao final de cada intervalo de 2 horas, a população triplica. a. Escreva uma definição recorrente para a sequência A(n), o número de bactérias presentes no início do n-ésimo período de tempo. b. No início de que intervalo haverá 1.350.000 bactérias presentes? 8 Relações de Recorrência 8. Resolva a seguinte relação de recorrência: ● F(1) = 1 ● F(n) = nF(n-1) para n ≥ 2 9 Relações de Recorrência 9. No início deste capítulo, o empreiteiro afirmou: O material a ser estocado no local de produtos químicos decai, tornando-se material inerte, a uma taxa de 5% ao ano. Portanto, ao final de 20 anos restará apenas aproximadamente um terço do material ativo original. a. Escreva uma relação de recorrência T(n) para a quantidade de material ativo no início do ano n. Suponha que T(1) = X, uma quantidade específica, mas desconhecida. b. Resolva essa relação de recorrência. c. Calcule T(21) para verificar a afirmação do empreiteiro; note que ao final de 20 anos começa o vigésimo primeiro ano. 10 Relações de Recorrência 10. Uma colônia de morcegos é contada a cada 2 meses. As quatro primeiras contagens foram de 1200, 1800, 2700 e 4050. a) Supondo que essa taxa de crescimento continue, escreva uma relação de recorrência para o número de morcegos na n-ésima contagem. b) Resolva essa relação de recorrência. c) Qual será a 20a contagem? 11 Relações de Recorrência 11. Uma mensagem contendo um vírus foi enviada a 1000 endereços de correio eletrônico. Depois de 1 segundo, uma máquina recipiente transmite 10 novas mensagens com vírus e depois disso o vírus desabilita a si mesmo naquela máquina. a) Escreva uma relação de recorrência para o número de mensagens com vírus enviadas no n-ésimo segundo. b) Resolva essa relação de recorrência. c) Quantas mensagens com vírus são enviadas no final de 20 segundos, ou seja, no início do 21º segundo? 12 Matem´atica Discreta Para os exerc´ıcios envolvendo a sequˆencia de Fibonacci, vamos lembrar que ´e ela ´e definida por recorrˆencia da seguinte forma: F(1) = 1, F(2) = 1, F(n) = F(n − 1) + F(n − 2), n ≥ 3 1. Quest˜ao 1 Usando a lei de formac¸ ˜ao da sequˆencia de Fibonacci, como n ≥ 3 ent˜ao podemos abrir os termos at´e n − 2, ent˜ao temos F(n+1)+F(n−2) = (F(n)+F(n−1))+F(n−2) = F(n)+(F(n−1)+F(n−2)) = F(n)+F(n) = 2F(n) 2. Quest˜ao 2 Usando a lei de formac¸ ˜ao da sequˆencia de Fibonacci, como n ≥ 6 podemos abrir os termos at´e n − 5, ent˜ao temos F(n) = F(n − 1) + F(n − 2) = (F(n − 2) + F(n − 3)) + F(n − 2) = 2F(n − 2) + F(n − 3) F(n) = 2(F(n−3)+F(n−4))+F(n−3) = 3F(n−3)+2F(n−4) = 3(F(n−4)+F(n−5))+2F(n−4) F(n) = 5F(n − 4) + 3F(n − 5) 3. Quest˜ao 3 Vamos fazer a demonstrac¸ ˜ao usando o Princ´ıpio de Induc¸ ˜ao Finita. Base da Induc¸ ˜ao: Se n = 1, a soma ´e formada apenas pelo F(2) = 1 e como F(2n+1) = F(3) = 2 ent˜ao temos F(2) = F(3) − 1 e a proposic¸ ˜ao ´e v´alida par n = 1. Hip´otese de Induc¸ ˜ao: Vamos supor que para todo n = k ≥ 1 vale a proposic¸ ˜ao, ou seja F(2) + F(4) + . . . + F(2k) = F(2k + 1) − 1 Passo de Induc¸ ˜ao: Aqui devemos ser capazes de provar que a proposic¸ ˜ao vale para n = k + 1, para tanto vamos usar a hip´otese de induc¸ ˜ao (em (1)) na soma at´e F(2k): F(2) + F(4) + . . . + F(2k) + F(2k + 2) 1= F(2k + 1) − 1 + F(2k + 2) Agora usando a lei de formac¸ ˜ao temos F(2) + /f(4) + . . . + F(2k + 2) = F(2k + 3) − 1 Assim, pelo Princ´ıpio da induc¸ ˜ao finita, a proposic¸ ˜ao ´e v´alida para todo n ≥ 1, n ∈ N, ou seja, F(2) + F(4) + . . . + F(2n) = F(2n + 1) − 1 1 Matem´atica Discreta 4. Quest˜ao 4 (a) L(1) = 1, L(2) = 3, L(3) = 3 + 1 = 4, L(4) = 4 + 3 = 7, L(5) = 7 + 4 = 11. (b) Usaremos novamente o Princ´ıpio da Induc¸ ˜ao Finita: Base da Induc¸ ˜ao: Para n = 2, temos L(2) = 3 e F(3) + F(1) = 2 + 1 = 3 ent˜ao temos L(2) = F(3) + F(1) e a proposic¸ ˜ao ´e v´alida para n = 2. Hip´otese de Induc¸ ˜ao: Vamos supor que para todo 2 < k ≤ n a proposic¸ ˜ao seja v´alida, ou seja L(k) = F(k + 1) + F(k − 1) Passo de Induc¸ ˜ao: Aqui devemos ser capazes de provar que a proposic¸ ˜ao ´e v´alida para n = k + 1, inicialmente usaremos a lei de formac¸ ˜ao da sequˆencia de Lucas: L(k + 1) = L(k) + L(k − 1) Como 2 ≤ k −1 < k ≤ n, podemos usar a Hip´otese de induc¸ ˜ao na express˜ao acima, obtendo L(k+1) = (F(k+1)+F(k−1))+(F(k)+F(k−2)) = (F(k+1)+F(k))+(F(k−1)+F(k−2)) E finalmente usando a lei de formac¸ ˜ao da sequˆencia de Fibonacci obtemos: L(k + 1) = F(k + 2) + F(k) = Assim, pelo Princ´ıpio da induc¸ ˜ao finita, a proposic¸ ˜ao ´e v´alida para todo n ≥ 2, n ∈ N, ou seja L(n) = F(n + 1) + F(n − 1). 5. Quest˜ao 5 Observemos inicialmente que S(1), S(2) e S(3) s˜ao n´umeros pares. Agora supondo S(n − 3) par, podemos escrever S(n − 3) = 2k com k ∈ N. Ent˜ao S(n) = 3 · 2k = 2(3k) que ´e um n´umero par. Como os trˆes primeiros termos da sequˆencia s˜ao pares e S(n) ´e par sempre que S(n − 3) ´e par, ent˜ao S(n) ser´a par para todo n ∈ N. 2 Matem´atica Discreta 6. Quest˜ao 6 Vamos proceder a prova usando induc¸ ˜ao finita. Base da induc¸ ˜ao: Se n = 7, ent˜ao T(7) = 2T(5) + 2 = 2 · 6 + 2 = 14 ≥ 14 = 2 · 7. Hip´otese de induc¸ ˜ao: Vamos supor que para todo k, 7 ≤ k ≤ n a proposic¸ ˜ao ´e v´alida, ou seja, T(k) ≥ 2k. Passo de induc¸ ˜ao: Suponha agora n = k + 1 ≥ 8, usando a lei de formac¸ ˜ao temos: T(k + 1) = 2T(k − 1) + 2 Aplicando a hip´otese de induc¸ ˜ao par T(k − 1), temos T(k −1) ≥ 2(k −1) = 2k −2 =⇒ 2T(k −1) ≥ 4k −4 =⇒ 2T(k −1)+2 ≥ 4k −4+2 = 4k −2 =⇒ T(k + 1) ≥ 4k − 2 = 2k + 2 + 2k − 4 Como k ≥ 7 temos ent˜ao 2k − 4 ≥ 14 − 4 = 10 e ent˜ao T(k + 1) ≥ 2k + 2 + 10 > 2k + 2 = 2(k + 1) Assim, pelo princ´ıpio de induc¸ ˜ao finita, T(n) ≥ 2n para todo n ≥ 7. 7. Quest˜ao 7 (a) Como queremos as bact´erias presentes no in´ıcio do per´ıodo de tempo, ent˜ao a quantidade inicial ´e A(1) = 50000. Como a cada per´ıodo de tempo de duas horas a populac¸ ˜ao triplica, podemos definir de forma recorrente A(n) = 3A(n − 1), A(1) = 50000. (b) Vamos Observar que A(2) = 3A(1), A(3) = 3A(2) = 3 · 3A(1) = 32A(1), A(4) = 3A(3) = 3 · 32A(1) = 33A(1). Observando o comportamento, vamos provar que A(n) = 3n−1A(1) para todo n ≥ 2. A base da induc¸ ˜ao est´a feita, pois A(2) = 31A(1) = 3A(1). Hip´otese de Hinduc¸ ˜ao: A(k) = 3k−1A(1). Temos ent˜ao A(k+1) = 3A(k) e usando a hip´otese de induc¸ ˜ao A(k+1) = 3·3k−1A(1) = 3kA(1) e pelo princ´ıpio da induc¸ ˜ao finita, temos A(n) = 3n−1A(1). Como A(1) = 50000, basta calcular para qual valor de n temos A(n) = 1350000. 3n−150000 = 1350000 =⇒ 3n−1 = 1350000 50000 = 27 =⇒ 3n−1 = 33 =⇒ n = 4 Portanto haver´a 1.350.000 bact´erias no in´ıcio do 4º intervalo de 2 horas. 8. Quest˜ao 8 Raciocinando de f´orma an´aloga `a quest˜ao anterior temos F(1) = 1, F(2) = 2F(1), . . . F(n) = nF(n−1). Multiplicando obtemos F(n) = n(n−1)F(n−1) = . . . = n(n−1) · · · 2F(1) = n!F(1), e como F(1) = 1, temos que F(n) = n!. 3 Matem´atica Discreta 9. Quest˜ao 9 (a) Temos T(1) = X, a quantidade inicial de material, presente no local no in´ıcio do ano 1. Como a cada ano o material decai 5%, temos que T(2) = T(1)−(0, 05)T(1) = (0, 95)T(1) e no in´ıcio do n-´esimo ano a quantidade de material ser´a T(n) = (0, 95)T(n − 1), T(1) = X. (b) Resolvendo a recorrˆencia, temos que T(1) = X, T(2) = (0, 95)T(1), . . . , T(n) = (0, 95)T(n − 1), multiplicando temos T(n) = (0, 95)T(n − 1) = (0, 95)2T(n − 2) = . . . = (0, 95)n−1T(1) = (0, 95)n−1X (c) T(21) = (0, 95)20X = 0, 35X. Como 1 3 ´e aproximadamente 0, 33, verificamos a afirmac¸ ˜ao do empreiteiro. 10. Quest˜ao 10 (a) Para encontrar a recorrˆencia, vamos observar que T(1) = 1200, T(2) = 1800 =⇒ T(2) − T(1) = 600 = T(1) 2 , logo T(2) = T(1) + (0, 5)T(1) = (1, 5)T(1). Verificando os demais casos, (1, 5)T(2) = 2700 = T(3) e (1, 5)T(3) = 4050 = T(4). Portanto a relac¸ ˜ao de recorrˆencia para o n´umero de morcegos na n-´esima contagem ´e T(n) = (1, 5)T(n − 1), T(1) = 1200. (b) Resolvendo a recorrˆencia como na quest˜ao anterior: T(n) = (1, 5)T(n − 1) = (1, 5)2T(n − 2) = . . . = (1, 5)n−1T(1) = (1, 5)n−11200 (c) A 20ª contagem ser´a T(20) = (1, 5)191200 ≈ 2660205, 38. Como a quantidade de morcegos deve ser um n´umero inteiro ent˜ao a 20ª contagem ser´a 2.660.205 morcegos. 11. Quest˜ao 11 (a) No primeiro segundo, ou seja, inicialmente, s˜ao enviadas T(1) = 1000 mensagens. Como cada m´aquina que recebeu a mensagem no primeiro segundo transmite 10 mensagens ap´os 1 segundo, temos que no 2º segundo s˜ao enviadas T(2) = 10T(1) mensagens e assim sucessivamente. Ent˜ao a relac¸ ˜ao de recorrˆencia para o n´umero de mensagens enviadas no n-´esimo segundo ´e T(n) = 10T(n − 1), T(1) = 1000. (b) T(n) = 10T(n − 1) = 102T(n − 2) = . . . 10n−1T(1) = 10n−1 · 1000 = 10n−1 · 103 = 10n+2 (a) No in´ıcio do 21º segundo ser˜ao enviadas T(21) = 1023 mensagens. 4