Gabarito-AV2-MatDisc-135-2021_1 (1)

Prévia do material em texto

MATEMÁTICA DISCRETA
TRABALHO ACADÊMICO DA AV2 – 2021.1
Prof. Milton Alexandre da Silva Jr.
GABARITO
Questão 1 (1,6 pontos)
Encontre uma relação de recorrência para a sequência:
1, a, a2, a3, a4, a5, …
onde a ∊ ℕ* e a > 1. 
Solução:
T(1) = 1
T(n+1) = aT(n), para n ≥ 1
Questão 2 (1,6 pontos)
Resolva a seguinte relação de recorrência:
S(1) = 5
S(n) = S(n - 1) + 5, para n ≥ 2
Solução:
A recorrência acima é da forma S(n) = c∙S(n-1) + g(n), com c = 1 e g(n) = 5.
Utilizando a solução geral para recorrências desse tipo, obtemos:
S (n)= cn−1 S(1)+∑
i=2
n
cn−i g(i) = 5+∑
2
n
5 = 5+(n−1)5 = 5n
Questão 3 (1,6 pontos)
Demonstre que, para qualquer inteiro positivo n, 2n > n.
Solução:
Questão 4 (1,6 pontos)
Prove que, para qualquer inteiro positivo n o número, 22n – 1 é divisível por
3.
Solução:
Questão 5 (1,6 pontos)
Prove que uma cerca de madeira com n estacas tem n – 1 seções (espaços
entre as estacas) para qualquer n ≥ 1.
Solução: