Resolução Prova Matemátic Discreta

Prévia do material em texto

INSTITUTO FEDERAL DO ESPÍRITO SANTO
MATEMÁTICA DISCRETA
Aluno: Matheus Teixeira de Aguiar
Matrícula: 20202BSI0336
Professor(a): Leandro Colombi Resendo
Data: 01/06/2021
1-
a)
𝐻(1) = 1
𝐻(𝑛) = 2𝐻(𝑛 − 1) + 1 , 𝑛 > 2
b) Podemos realizar uma expansão.
𝐻(𝑛) = 2𝐻(𝑛 − 1) + 1 = 2(2𝐻(𝑛 − 2) + 1) + 1
𝐻(𝑛) = 2 * 2𝐻(𝑛 − 2) + 2 + 1 = 2 * 2 * (2 * 𝐻(𝑛 − 3) + 2 + 1
𝐻(𝑛) = 2 * 2 * 2𝐻(𝑛 − 3) + 2 * 2 + 2 + 1
.:
SOMA DE UMA P.G.2𝑛−1 +... + 23 + 22 + 21 + 20
𝑆
𝑛
=
𝑎
1
(𝑞𝑛−1)
𝑞−1
𝑆
𝑛
= 1(2
𝑛−1)
2−1
𝑆
𝑛
= 2
𝑛−1
1
𝑆
𝑛
= 2𝑛 − 1
CASO BASE:
𝑛 = 1
ℎ(1) = 21 − 1
1 = 21 − 1
VERIFICADO1
n>= 2𝐻(1) = 2𝐻(𝑛 − 1) + 1
Através da Hipótese de Indução: para pertence𝐻(𝑘) = 2𝑘 − 1 𝑘 𝑍 
e 𝑘 >= 1
Através do passo indutivo: 𝐻(𝑘 + 1) = 2𝑘+1 + 1
𝐻(𝑘 + 1) = 2 * 𝐻(𝑘 + 1 − 1) + 1 = 2 * 𝐻(𝑘) + 1 = 2(2𝑘 − 1) + 1
2 * 2𝑘 − 2 + 1 = 2𝑘+1 − 1
CQD𝐻(𝑘 + 1) = 2𝑘+1 − 1
2-
13 + 23 + 33 +... + 𝑛3 = 𝑛
2(𝑛+1)2
4
Prova por indução:
CASO BASE: = OK!1
3(13+1)2
4
1(2)2
4 =
1*4
4 = 1 = 1
SUPOR QUE: 13+ 23 + 33 +... + 𝑘3 = 𝑘
2(𝑘+1)2
4
PROVAR QUE: 13+ 23 + 33 +... + 𝑘3 + (𝑘 + 1)3 = (𝑘+1)
2(𝑘+2)2
4
𝑘2(𝑘+1)2
4 + (𝑘 + 1)
3 = (𝑘+1)
2(𝑘+2)2
4
𝑘2(𝑘+1)2+4(𝑘+1)3
4 =
(𝑘+1)2(𝑘+2)2
4
𝑘2(𝑘 + 1)2 + 4(𝑘 + 1)3 = (𝑘 + 1)
2
(𝑘 + 2)2
(𝑘 + 1)2(𝑘2 + 4(𝑘 + 1) = (𝑘 + 1)
2
(𝑘 + 2)2
(𝑘 + 1)2(𝑘2 + 4𝑘 + 4) = (𝑘 + 1)
2
(𝑘 + 2)2
CQD(𝑘 + 1)2(𝑘2 + 2) = (𝑘 + 1)
2
(𝑘 + 2)2
3-
a) Teste de Mesa
𝑘 = 0
𝑖
0
= 1
𝑗
0
= 1
𝑘 = 1
𝑗
 1
= 𝑗
0
+ (𝑖
0
+ 1) = 𝑎 + 1(1 + 1) = 𝑎 + 3
𝑖
1
= 𝑖
0
+ 1 = 1 + 1 = 2
𝑘 = 2
𝑗
 2
= 𝑗
1
+ (𝑖
1
+ 1) = 𝑎 + 3 + (2 + 1) = 𝑎 + 6
𝑖
2
= 𝑖
1
+ 1 = 2 + 1 = 3
𝑘 = 3
𝑗
 3
= 𝑗
2
+ (𝑖
2
+ 1) = 𝑎 + 6 + (3 + 1) = 𝑎 + 10
𝑖
3
= 𝑖
2
+ 1 = 3 + 1 = 4
𝑘 = 4
𝑗
 4
= 𝑗
3
+ (𝑖
3
+ 1) = 𝑎 + 10 + (4 + 1) = 𝑎 + 15
𝑖
4
= 𝑖
3
+ 1 = 4 + 1 = 5
.:
Conjectura: 𝐽 = 𝑎 + 𝑖(𝑖+1)2
b) Verificação por indução
BASE:
𝑗
0
= 𝑎 +
𝑖
0 
(𝑖
0
+1)
2 𝑎 + 1 = 𝑎 +
1(1+1)
2
OK!𝑎 + 1 = 𝑎 + 22 = 𝑎 + 1 = 𝑎 + 1
SUPOR QUE: 𝑗
𝑘
= 𝑎 +
𝑖
𝑘 
(𝑖
𝑘
+1)
2
MOSTRAR QUE: 𝑗
𝑘+1
= 𝑎 +
𝑖
𝑘+1 
(𝑖
𝑘+1
+1)
2
𝑗
𝑘+1
= 𝑗
𝑘
+ (𝑖
𝑘
+ 1)
= 𝑗
𝑘
+ (𝑖
𝑘
+ 1)
= 𝑎 +
𝑖
𝑘 
(𝑖
𝑘
+1)
2 + (𝑖𝑘 + 1)
= 𝑎 +
𝑖
𝑘 
(𝑖
𝑘
+1)+2(𝑖
𝑘
+1)
2
 = 𝑎 +
(𝑖
𝑘
+1)(𝑖
𝑘
+2)
2
= 𝑎 +
𝑖
𝑘+1
(𝑖
𝑘+1
−1+2)
2
CQD= 𝑎 +
𝑖
𝑘+1
(𝑖
𝑘+1
+1)
2
4-
a)T(1)=3
T(n)=T( )+n𝑛2
c = 1 e g(n) = n
𝑇(𝑛) = 1𝑙𝑜𝑔𝑛𝑇(1) +
𝑖=1
𝑙𝑜𝑔𝑛
∑ 1𝑙𝑜𝑔𝑛−𝑖𝑔(2𝑖)
𝑇(𝑛) = 3 +
𝑖=1
𝑙𝑜𝑔𝑛
∑ 2𝑖
𝑇(𝑛) = 3 + (21 + 22 + 23 +... + 2𝑙𝑜𝑔𝑛)
𝑞 = 2 𝑎
1 
= 2 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 = 𝑙𝑜𝑔𝑛
𝑇(𝑛) = 3 + 𝑆
𝑛
=
𝑎
1
(𝑞𝑛−1)
𝑞−1
𝑇(𝑛) = 3 + 𝑆
𝑛
= 2(2
𝑙𝑜𝑔𝑛−1)
2−1
𝑇(𝑛) = 3 + 𝑆
𝑛
= 2(𝑛−1)2−1
𝑇(𝑛) = 3 + 2(𝑛−1)1
𝑇(𝑛) = 3 + 2𝑛 − 2
.:
𝑇(𝑛) = 2𝑛 + 1
b)A(1)=1
A(n)=A( )+n𝑛 − 1
c = 1 e g(n) = n
𝐴(𝑛) = 1𝑛−1𝐴(1) +
𝑖=2
𝑛
∑ 1𝑛−𝑖𝑔(𝑖)
𝐴(𝑛) = 1 +
𝑖=2
𝑛
∑ 𝑖
𝐴(𝑛) = 1 + 2 + 3 + 4 +... + 𝑛
𝐴(𝑛) = (1+𝑛)𝑛2
.:
𝐴(𝑛) = 𝑛
2+𝑛
2
c)S(1)=1
S(n)=2S( )+1𝑛2
c = 2 e g(n) = 1
𝑇(𝑛) = 2𝑙𝑜𝑔𝑛𝑆(1) +
𝑖=1
𝑙𝑜𝑔𝑛
∑ 2𝑙𝑜𝑔𝑛−𝑖𝑔(2𝑖)
𝑇(𝑛) = 𝑛 +
𝑖=1
𝑙𝑜𝑔𝑛
∑ 2𝑙𝑜𝑔𝑛2−𝑖1
𝑇(𝑛) = 𝑛 +
𝑖=1
𝑙𝑜𝑔𝑛
∑ 𝑛 * 𝑖2
𝑇(𝑛) = 𝑛 + 𝑛
𝑖=1
𝑙𝑜𝑔𝑛
∑ * ( 12 +
1
22
+ 1
23
+... + 1𝑙𝑜𝑔𝑛 )
𝑞 = 1/2 𝑎
1 
= 1/2 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 = 𝑙𝑜𝑔𝑛
𝑇(𝑛) = 𝑛 + 𝑆
𝑛
= 1/2(1/2
𝑙𝑜𝑔𝑛−1)
1/2−1
𝑇(𝑛) = 𝑛 + 𝑆
𝑛
= 1/4
𝑙𝑜𝑔𝑛−1/2
−1/2
𝑇(𝑛) = 𝑛 + 𝑆
𝑛
= 1/4
𝑙𝑜𝑔𝑛
−1/2 + 1
𝑇(𝑛) = 𝑛 + 𝑆
𝑛
= 1
4𝑙𝑜𝑔𝑛
*− 2 + 1
𝑇(𝑛) = 𝑛 + 𝑆
𝑛
= 1
−2𝑙𝑜𝑔𝑛
+ 1
𝑇(𝑛) = 𝑛 + 𝑆
𝑛
= 1−𝑛 + 1
𝑇(𝑛) = 𝑛 + 1−𝑛 + 1
.:
𝑇(𝑛) = −𝑛
2+1
−𝑛 + 1
5-
a)𝐿(1) = 1
𝐿(2) = 3
𝐿(𝑛) = 𝐿(𝑛 − 1) + 𝐿(𝑛 − 2)
𝐿(1) = 1
𝐿(2) = 3
𝐿(3) = 𝐿(3 − 1) + 𝐿(3 − 2) = 𝐿(2) + 𝐿(1) = 3 + 1 = 4
𝐿(4) = 𝐿(4 − 1) + 𝐿(4 − 2) = 𝐿(3) + 𝐿(2) = 4 + 1 = 5
𝐿(5) = 𝐿(5 − 1) + 𝐿(5 − 2) = 𝐿(4) + 𝐿(3) = 5 + 1 = 6
b)
BASE:
OK!𝐿(2) = 𝐹(2) + 𝐹(0) = 3
Supor que para 3 <= 𝑟 <= 𝑘
𝐿(𝑟) = 𝐹(𝑟) + 𝐹(𝑟 − 2)
Mostrar que: 𝐿(𝑟 + 1) = 𝐹(𝑟 + 1) + 𝐹(𝑟 − 1)
𝐿(𝑟 + 1) = 𝐹(𝑟) + 𝐹(𝑟 − 1)
𝐿(𝑟) = 𝐹(𝑟) + 𝐹(𝑟 − 2)
𝐿(𝑟 − 1) = 𝐹(𝑟 − 1) + 𝐹(𝑟 − 3)
𝐿(𝑟 + 1) = 𝐹(𝑟) + 𝐹(𝑟 − 2) + 𝐹(𝑟 − 1) + 𝐹(𝑟 − 3)
𝐿(𝑟 + 1) = 𝐹(𝑟 + 1) + 𝐹(𝑟 − 1)