20 - Relações de Recorrência - Exercícios

Prévia do material em texto

16/27/2019 1Exercícios - Relações de Recorrência
Professor: Luiz Augusto Laranjeira
luiz.laranjeira@gmail.com
AULA 20
Matemática Discreta 1
Exercícios:
Relações de Recorrência
6/27/2019 2Exercícios - Relações de Recorrência
Exercício 1
Encontre a solução para a seguinte relação de recorrência usando um
dos métodos iterativos.
an = 2nan−1, a0 = 1
6/27/2019 3Exercícios - Relações de Recorrência
Exercício 1
Encontre a solução para a seguinte relação de recorrência usando um
dos métodos iterativos.
an = 2nan−1, a0 = 1
a1 = 2.1.a0 = 2.1.1 = 1.2
1 = 1!21 = 2
a2 = 2.2.a1 = 2.2.2 = 2.2
2 = 2!22 = 8
A3 = 2.3.a2 = 2.3.8 = 2.3.2
3 = 3!23 = 48
a4 = 2.4.a3 = 2.4.3.2
4 = 2.3.4.24 = 4!24 = 384
a5 = 2.5.a4 = 2.5.3.4.2
5 = 2.3.4.5.25 = 5!25 = 3840
a6 = 2.6.a5 = 2.6.3.4.5.2
6 = 2.3.4.5.6.26 = 6!26 = 46080
... ...
Fórmula fechada: 𝑎𝑛 = 𝑛! 2
𝑛
6/27/2019 4Exercícios - Relações de Recorrência
Exercício 2
Encontre a solução para a seguinte relação de recorrência usando um
dos métodos iterativos.
𝒂𝒏 = −𝒂𝒏−𝟏 + 𝒏 − 𝟏, 𝒂𝟎= 𝟕
6/27/2019 5Exercícios - Relações de Recorrência
Exercício 2
Encontre a solução para a seguinte relação de recorrência usando um
dos métodos iterativos.
𝒂𝒏 = −𝒂𝒏−𝟏 + 𝒏 − 𝟏, 𝒂𝟎= 𝟕
a1 = −a0 + 1 − 1 = −7 + 1 − 1 = −7 a2 = −a1 + 2 − 1 = 7 + 2 − 1 = 8
a3 = −a2 + 3 − 1 = −8 + 3 − 1 = −6 a4 = −a3 + 4 − 1 = 6 + 4 − 1 = 9
a5 = −a4 + 5 − 1 = −9 + 5 − 1 = −5 a6 = −a5 + 6 − 1 = 5 + 6 − 1 = 10
a7 = −a6 + 7 − 1 = −10 + 7 − 1 = −4 a8 = −a7 + 8 − 1 = 4 + 8 − 1 = 11
... ...
Para n ímpar : 𝑎𝑛 =
𝑛+1
2
− 8 Para n par : 𝑎𝑛 =
𝑛
2
+ 7
Fórmula única fechada: 𝑎𝑛 =
𝑛+1
2
+ 7 − 15(𝑛 𝑚𝑜𝑑 2)
6/27/2019 6Exercícios - Relações de Recorrência
Exercício 2a
Encontre a solução para a seguinte relação de recorrência usando o
método aplicado a relações de recorrência lineares não-homogêneas.
𝒂𝒏 = −𝒂𝒏−𝟏 + 𝒏 − 𝟏, 𝒂𝟎= 𝟕
6/27/2019 7Exercícios - Relações de Recorrência
Exercício 2a
Encontre a solução para a seguinte relação de recorrência usando o
método aplicado a relações de recorrência lineares não-homogêneas.
𝒂𝒏 = −𝒂𝒏−𝟏 + 𝒏 − 𝟏, 𝒂𝟎= 𝟕
Solução homogênea associada:
𝜶𝒏 = − 𝜶𝒏−𝟏 → 𝛼𝑛 + 𝛼𝑛−1 = 0 → 𝛼 + 1 = 0 → 𝛼 = −1
Daí: ℎ 𝑛 = 𝐵(−1)𝑛
Solução particular: (a raiz da equação característica de h (n) não é igual a 1)
𝒑(𝒏) = 𝑨𝟎 + 𝑨𝟏𝒏 Substituindo esta espressãona relação de recorrência original vem:
𝐴0 + 𝐴1𝑛 = −(𝐴0 + 𝐴1(𝑛 − 1)) + 𝑛 − 1 daqui vamos calcular os valores de A0 e A1
𝐴1 = −𝐴1 + 1 → 2𝐴1 = 1 → 𝐴1 =
1
2
𝐴0 = −𝐴0 + 𝐴1 − 1 → 2𝐴0 =
1
2
− 1 e 𝐴0 = −
1
4
𝑝 𝑛 = −
1
4
+
1
2
𝑛
6/27/2019 8Exercícios - Relações de Recorrência
Exercício 2a (cont.)
Encontre a solução para a seguinte relação de recorrência usando o
método aplicado a relações de recorrência lineares não-homogêneas.
𝒂𝒏 = −𝒂𝒏−𝟏 + 𝒏 − 𝟏, 𝒂𝟎= 𝟕
Já temos ℎ 𝑛 = 𝐵(−1)𝑛 e 𝑝 𝑛 = −
1
4
+
1
2
𝑛
Solução completa:
𝑆𝑐 𝑛 = 𝐵(−1)
𝑛 −
1
4
+
1
2
𝑛 Vamos usar a condição inicial para calcular o valor de B
𝑆𝑐 0 = 𝑎0 = 𝐵(−1)
0 −
1
4
+
1
2
× 0 = 7 → 𝐵 = 7 +
1
4
=
29
2
Finalmente:
𝑆𝑐 𝑛 = ℎ 𝑛 + 𝑝 𝑛 =
29
4
(−1)𝑛 −
1
4
+
1
2
𝑛 ou 𝒂𝒏 =
𝟐𝟗
𝟒
(−𝟏)𝒏 −
𝟏
𝟒
+
𝟏
𝟐
𝒏
6/27/2019 9Exercícios - Relações de Recorrência
Exercício 3
Encontre a solução para a seguinte relação de recorrência usando o
método aplicado a relações de recorrência lineares não-homogêneas.
𝒂𝒏 = 𝟑𝒂𝒏−𝟏 + 𝟐𝒏 − 𝟏 + 𝟐. 𝟓
𝒏−𝟏, 𝒂𝟎= 𝟎
6/27/2019 10Exercícios - Relações de Recorrência
Exercício 3
Encontre a solução para a seguinte relação de recorrência usando o
método aplicado a relações de recorrência lineares não-homogêneas.
𝒂𝒏 = 𝟑𝒂𝒏−𝟏 + 𝟐𝒏 − 𝟏 + 𝟐. 𝟓
𝒏−𝟏, 𝒂𝟎= 𝟎
Solução homogênea associada: 𝜶𝒏 = 𝟑𝜶𝒏−𝟏
𝛼𝑛 − 3𝛼𝑛−1 = 0 → 𝛼 − 3 = 0 → 𝛼 = 3 Daí: ℎ 𝑛 = 𝐵(3)𝑛
Solução particular: (5 não é raiz da equação característica de ℎ 𝑛 )
𝒑(𝒏) = 𝑨𝟐𝟓
𝒏 + 𝑨𝟏𝒏 + 𝑨𝟎 Substituindo esta expressão na relação de recorrência original vem:
𝐴25
𝑛 + 𝐴1𝑛 + 𝐴0 =
3
5
𝐴25
𝑛 + 3𝐴1 𝑛 − 1 + 3𝐴0 + 2𝑛 − 1 +
2
5
5𝑛
Daí calculamos os valores de A0 , A1 , A2 e 𝑝(𝑛)
𝐴2 =
3
5
𝐴2 +
2
5
→ 𝐴2= 1 𝐴1 = 3𝐴1 + 2 → 𝐴1 = −1 𝐴0 = 3𝐴0 − 3𝐴1 − 1 → 𝐴0 = −1
𝑝 𝑛 = 5𝑛 − 𝑛 − 1
6/27/2019 11Exercícios - Relações de Recorrência
Exercício 3 (cont.)
Encontre a solução para a seguinte relação de recorrência usando o
método aplicado a relações de recorrência lineares não-homogêneas.
𝒂𝒏 = 𝟑𝒂𝒏−𝟏 + 𝟐𝒏 − 𝟏 + 𝟐. 𝟓
𝒏−𝟏, 𝒂𝟎= 𝟎
Solução particular: 𝑝 𝑛 = 5𝑛 − 𝑛 − 1
Solução completa:
𝑆𝑐 𝑛 = 𝑎 𝑛 = 𝐵(3)
𝑛 + 5𝑛 − 𝑛 − 1 𝑎 𝑛 = 0
𝐵 + 1 − 1 = 0 → 𝐵 = 0
Finalmente temos:
𝑎 𝑛 = 5𝑛 −𝑛 − 1
6/27/2019 12Exercícios - Relações de Recorrência
Exercício 4
Encontre a solução para a seguinte relação de recorrência usando o
método aplicado a relações de recorrência lineares não-homogêneas.
an = 4an −1 − 3an −2 + 2
n + n + 3, a0 = 1, a1 = 4
6/27/2019 13Exercícios - Relações de Recorrência
Exercício 4
Encontre a solução para a seguinte relação de recorrência usando o
método aplicado a relações de recorrência lineares não-homogêneas.
an = 4an −1 − 3an −2 + 2
n + n + 3, a0 = 1, a1 = 4
Solução homogênea associada: 𝜶𝒏 = 𝟒𝜶𝒏−𝟏 − 𝟑𝜶𝒏−𝟐
𝛼𝑛 − 4𝛼𝑛−1 + 3𝛼𝑛−2 = 0 → 𝛼2 − 4𝛼 + 3 = 0 → 𝛼1 = 3 𝛼2 = 1
Daí: ℎ 𝑛 = 𝐴(3)𝑛+𝐵(1)𝑛 ou ℎ 𝑛 = 𝐴(3)𝑛+ 𝐵
Solução particular: (uma das raizesda equação característica de h (n) é igual a 1)
𝒑(𝒏) = 𝑨𝟎𝟐
𝒏 + 𝒏(𝑨𝟏𝒏 + 𝑨𝟐) Substituindo esta expressão na relação de recorrência original vem:
𝐴02
𝑛 + 𝐴1𝑛
𝟐 + 𝐴2𝑛 = 4 𝐴02
𝑛−1 + 𝐴1 𝑛 − 1
𝟐 + 𝐴2 𝑛 − 1 +
−3 𝐴02
𝑛−2 + 𝐴1 𝑛 − 2
𝟐 + 𝐴2(𝑛 − 2) + 2
𝑛 + 𝑛 + 3
Daí calculamos valores de A0 , A1 , A2 e 𝑝(𝑛)
𝐴0 = −4 𝐴1 = −
1
4
𝐴2 = −
5
2
𝑝 𝑛 = −4. 2𝑛 −
1
4
𝑛𝟐 −
5
2
𝑛
6/27/2019 14Exercícios - Relações de Recorrência
Exercício 4 (cont.)
Encontre a solução para a seguinte relação de recorrência usando o
método aplicado a relações de recorrência lineares não-homogêneas.
an = 4an −1 − 3an −2 + 2
n + n + 3, a0 = 1, a1 = 4 
Já temos ℎ 𝑛 = 𝐴(3)𝑛+ 𝐵 e 𝑝 𝑛 = −4. 2𝑛 −
1
4
𝑛𝟐 −
5
2
𝑛
Solução completa: 𝑆𝑐 𝑛 = ℎ 𝑛 + 𝑝 𝑛 = 𝐴(3)
𝑛+ 𝐵 − 4. 2𝑛 −
1
4
𝑛𝟐 −
5
2
𝑛
Usamos as condições iniciais para calcular A e B
𝑆𝑐 0 = 𝑎0 = 𝐴 + 𝐵 − 4 = 1 𝑆𝑐 1 = 𝑎1 = 3𝐴 + 𝐵 − 8 −
1
4
−
5
2
= 4
Daí vem que: 𝐴 =
39
8
𝐵 =
1
8
Finalmente: 𝑆𝑐 𝑛 = ℎ 𝑛 + 𝑝 𝑛 =
39
8
3𝑛 − 4. 2𝑛 −
1
4
𝑛𝟐 −
5
2
𝑛 +
1
8
ou
𝒂𝒏 =
𝟑𝟗
𝟖
𝟑 𝒏 − 𝟒. 𝟐𝒏 −
𝟏
𝟒
𝒏𝟐 −
𝟓
𝟐
𝒏 +
𝟏
𝟖
6/27/2019 15Exercícios - Relações de Recorrência
Exercício 5
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham a cadeia 01. b) Quais são as condições iniciais?
c) Quantas cadeias de 7 bits existem contendo a cadeia 01?
6/27/2019 16Exercícios - Relações de Recorrência
Exercício 5
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham a cadeia 01. b) Quais são as condições iniciais?c) Quantas cadeias de 7 bits existem contendo a cadeia 01?
a) Sendo ano n
o de cadeias de 𝑛 bits contendo a cadeia 01 e 
observando a tabela ao lado podemos escrever a relação
de recorrência para 𝑛 ≥ 2:
𝑎𝑛 = 𝑎𝑛−1 + σ𝑘=0
𝑛−2 2𝑘
O somatório na expressão acima denota uma PG com
termo inicial 1 (20), termo final 2𝑛−2 e razão 2. O
valor do somatório é (2𝑛−1−1) e a expressão fica:
𝒂𝒏 = 𝒂𝒏−𝟏 + 𝟐
𝒏−𝟏 − 𝟏
b) As condições iniciais são: 𝑎0 = 𝑎1 = 0. 
1 ******* 𝒂𝒏−𝟏
0 1 ****** 𝟐𝒏−𝟐
0 01 ***** 𝟐𝒏−𝟑
0 001 **** 𝟐𝒏−𝟒
...
0 0000...01 𝟐𝟎
Notar que os casos listados na
tabela acima precisam:
a) Ser mutuamente exclusivos;
b) Abranger todas as diferentes
situações que satisfazem os
requisitos do enunciado.
6/27/2019 17Exercícios - Relações de Recorrência
Exercício 5
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham a cadeia 01. b) Quais são as condições iniciais?
c) Quantas cadeias de 7 bits existem contendo a cadeia 01?
a) Sendo ano n
o de cadeias de 𝑛 bits contendo a cadeia 01 e 
observando a tabela ao lado podemos escrever a relação
de recorrência para 𝑛 ≥ 2:
𝑎𝑛 = 𝑎𝑛−1 + σ𝑘=0
𝑛−2 2𝑘 𝒂𝒏 = 𝒂𝒏−𝟏 + 𝟐
𝒏−𝟏 − 𝟏
b) As condições iniciais são: 𝑎0 = 𝑎1 = 0. 
c) Podemos calcular de 𝑎2 a 𝑎7 usando a relação de recorrência: 
𝑎2 = 𝑎1 + 2
1 − 1 = 0 + 2 − 1 = 1 𝑎3 = 𝑎2 + 2
2 − 1 = 1 + 4 − 1 = 4
𝑎4 = 𝑎3 + 2
3 − 1 = 4 + 8 − 1 = 11 𝑎5 = 𝑎4 + 2
4 − 1 = 11 + 16 − 1 = 26
𝑎6 = 𝑎5 + 2
5 − 1 = 26 + 32 − 1 = 57 𝑎7 = 𝑎6 + 2
6 − 1 = 57 + 64 − 1 = 120
𝑎7 = 120
1 ******* 𝒂𝒏−𝟏
0 1 ****** 𝟐𝒏−𝟐
0 01 ***** 𝟐𝒏−𝟑
0 001 **** 𝟐𝒏−𝟒
...
6/27/2019 18Exercícios - Relações de Recorrência
Exercício 6
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham dois 0’s consecutivos. b) Quais são as condições iniciais?
c) Quantas cadeias de 7 bits existem que contêm dois 0’s consecutivos?
6/27/2019 19Exercícios - Relações de Recorrência
Exercício 6
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham dois 0’s consecutivos. b) Quais são as condições iniciais?
c) Quantas cadeias de 7 bits existem que contêm dois 0’s consecutivos?
a) Sendo ano n
o de cadeias de 𝑛 bits contendo dois 0’s 
consecutivos e observando a tabela ao lado podemos
escrever a relação de recorrência para 𝑛 ≥ 2:
𝒂𝒏 = 𝒂𝒏−𝟏 + 𝒂𝒏−𝟐 + 𝟐
𝒏−𝟐
b) As condições iniciais são: 𝑎0 = 𝑎1 = 0. 
1 ****** 𝒂𝒏−𝟏
0 1 ***** 𝒂𝒏−𝟐
0 0 ***** 𝟐𝒏−𝟐
Notar que os casos listados na
tabela acima precisam:
a) Ser mutuamente exclusivos;
b) Abranger todas as diferentes
situações que satisfazem os
requisitos do enunciado.
6/27/2019 20Exercícios - Relações de Recorrência
Exercício 6
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham dois 0’s consecutivos. b) Quais são as condições iniciais?
c) Quantas cadeias de 7 bits existem que contêm dois 0’s consecutivos?
a) Sendo ano n
o de cadeias de 𝑛 bits contendo dois 0’s 
consecutivos e observando a tabela ao lado podemos
escrever a relação de recorrência para 𝑛 ≥ 2:
𝒂𝒏 = 𝒂𝒏−𝟏 + 𝒂𝒏−𝟐 + 𝟐
𝒏−𝟐
b) As condições iniciais são: 𝑎0 = 𝑎1 = 0. 
c) Podemos calcular de 𝑎2 a 𝑎7 usando a relação de recorrência: 
𝑎2 = 𝑎1 + 𝑎0 + 2
0 = 0 + 0 + 1 = 1 𝑎3 = 𝑎2 + 𝑎1 + 2
1 = 1 + 0 + 2 = 3
𝑎4 = 𝑎3 + 𝑎2 + 2
2 = 3 + 1 + 4 = 8 𝑎5 = 𝑎4 + 𝑎3 + 2
3 = 8 + 3 + 8 = 19
𝑎6 = 𝑎5 + 𝑎4 + 2
4 = 19 + 8 + 16 = 43 𝑎7 = 𝑎6 + 𝑎5 + 2
5 = 43 + 19 + 32 = 94
𝑎7 = 94
1 ****** 𝒂𝒏−𝟏
0 1 ***** 𝒂𝒏−𝟐
0 0 ***** 𝟐𝒏−𝟐
6/27/2019 21Exercícios - Relações de Recorrência
Exercício 7
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham três 0’s consecutivos. b) Quais são as condições iniciais?
c) Quantas cadeias de 7 bits existem que contêm três 0’s consecutivos?
6/27/2019 22Exercícios - Relações de Recorrência
Exercício 7
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham três 0’s consecutivos. b) Quais são as condições iniciais?
c) Quantas cadeias de 7 bits existem que contêm três 0’s consecutivos?
a) Sendo ano n
o de cadeias de 𝑛 bits contendo três 0’s 
consecutivos e observando a tabela ao lado podemos
escrever a relação de recorrência para 𝑛 ≥ 3:
𝒂𝒏 = 𝒂𝒏−𝟏 + 𝒂𝒏−𝟐 + 𝒂𝒏−𝟑 + 𝟐
𝒏−𝟑
b) As condições iniciais são: 𝑎0 = 𝑎1 = 𝑎2 = 0. 
1 ****** 𝒂𝒏−𝟏
0 1 ***** 𝒂𝒏−𝟐
0 01 **** 𝒂𝒏−𝟑
0 00 **** 𝟐𝒏−𝟑
Notar que os casos listados na
tabela acima precisam:
a) Ser mutuamente exclusivos;
b) Abranger todas as diferentes
situações que satisfazem os
requisitos do enunciado.
6/27/2019 23Exercícios - Relações de Recorrência
Exercício 7
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham três 0’s consecutivos. b) Quais são as condições iniciais?
c) Quantas cadeias de 7 bits existem que contêm três 0’s consecutivos?
a) Sendo ano n
o de cadeias de 𝑛 bits contendo três 0’s 
consecutivos e observando a tabela ao lado podemos
escrever a relação de recorrência para 𝑛 ≥ 3:
𝒂𝒏 = 𝒂𝒏−𝟏 + 𝒂𝒏−𝟐 + 𝒂𝒏−𝟑 + 𝟐
𝒏−𝟑
b) As condições iniciais são: 𝑎0 = 𝑎1 = 𝑎2 = 0. 
c) Podemos calcular de 𝑎3 a 𝑎7 usando a relação de recorrência: 
𝑎3 = 𝑎2 + 𝑎1 + 𝑎0 + 2
0 = 0 + 0 + 0 + 1 = 1 𝑎4 = 𝑎3 + 𝑎2 + 𝑎1 + 2
1 = 1 + 0 + 0 + 2 = 3
𝑎5 = 𝑎4 + 𝑎3 + 𝑎2 + 2
2 = 3 + 1 + 0 + 4 = 8 𝑎6 = 𝑎5 + 𝑎4 + 𝑎3 + 2
3 = 8 + 3 + 1 + 8 = 20
𝑎7 = 𝑎6 + 𝑎5 + 𝑎4 + 2
4 = 20 + 8 + 3 + 16 = 47
𝑎7 = 47
1 ****** 𝒂𝒏−𝟏
0 1 ***** 𝒂𝒏−𝟐
0 01 **** 𝒂𝒏−𝟑
0 00 **** 𝟐𝒏−𝟑
6/27/2019 24Exercícios - Relações de Recorrência
Exercício 8
a) Encontre uma relação de recorrência para o número de maneiras de se subir
𝒏 degraus se a pessoa pode subir 1, 2 ou 3 degraus de cada vez. b) Quais são
as condições iniciais? c) De quantas maneiras a pessoa pode subir 8 degraus?
6/27/2019 25Exercícios - Relações de Recorrência
Exercício 8
a) Encontre uma relação de recorrência para o número de maneiras de se subir
𝒏 degraus se a pessoa pode subir 1, 2 ou 3 degraus de cada vez. b) Quais são
as condições iniciais? c) De quantas maneiras a pessoa pode subir 8 degraus?
a) Sendo ano n
o de maneiras de se subir 𝑛 degraus e
observando a tabela ao lado podemos escrever a
relação de recorrência para 𝑛 ≥ 3:
𝒂𝒏 = 𝒂𝒏−𝟏 + 𝒂𝒏−𝟐 + 𝒂𝒏−𝟑
b) As condições iniciais são: 𝑎0 = 1, 𝑎1 = 1, 𝑎2 = 2. (considerando 1 modo de subir 0 degraus)
1 ****** 𝒂𝒏−𝟏
2 ***** 𝒂𝒏−𝟐
3 **** 𝒂𝒏−𝟑
Notar que os casos listados na
tabela acima precisam:
a) Ser mutuamente exclusivos;
b) Abranger todas as diferentes
situações que satisfazem os
requisitos do enunciado.
6/27/2019 26Exercícios - Relações de Recorrência
Exercício 8
a) Encontre uma relação de recorrência para o número de maneiras de se subir
𝒏 degraus se a pessoa pode subir 1, 2 ou 3 degraus de cada vez. b) Quais são
as condições iniciais? c) De quantas maneiras a pessoa pode subir 8 degraus?
a) Sendo ano n
o de maneiras de se subir 𝑛 degraus e
observando a tabela ao lado podemos escrever a
relação de recorrência para 𝑛 ≥ 3:
𝒂𝒏 = 𝒂𝒏−𝟏 + 𝒂𝒏−𝟐 + 𝒂𝒏−𝟑
b) As condições iniciais são: 𝑎0 = 1, 𝑎1 = 1, 𝑎2 = 2. (𝑎0 = 1, há 1 modo de subir 0 degraus:
não subir nenhum degrau)
c) Podemos calcular de 𝑎3 a 𝑎8 usando a relação de recorrência: 
𝑎3 = 𝑎2 + 𝑎1 + 𝑎0 = 2 + 1 + 1 = 4 𝑎4 = 𝑎3 + 𝑎2 + 𝑎1 = 4 + 2 + 1 = 7
𝑎5 = 𝑎4 + 𝑎3 + 𝑎2 = 7 + 4 + 2 = 13 𝑎6 = 𝑎5 + 𝑎4 + 𝑎3 = 13 + 7 + 4 = 24
𝑎7 = 𝑎6+ 𝑎5 + 𝑎4 = 24 + 13 + 7 = 44 𝑎8 = 𝑎7 + 𝑎6 + 𝑎5 = 44 + 24 + 13 = 81
𝑎7 = 81
1 ****** 𝒂𝒏−𝟏
2 ***** 𝒂𝒏−𝟐
3 **** 𝒂𝒏−𝟑
6/27/2019 27Exercícios - Relações de Recorrência
Exercício 9
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham a cadeia 101. b) Quais são as condições iniciais?
c) Quantas cadeias de 7 bits existem contendo a cadeia 101?
6/27/2019 28Exercícios - Relações de Recorrência
Exercício 9
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham a cadeia 101. b) Quais são as condições iniciais?
c) Quantas cadeias de 7 bits existem contendo a cadeia 101?
a) Seja ano n
o de cadeias de 𝑛 bits contendo a cadeia 101. 
Observando a tabela ao lado podemos escrever a relação
de recorrência para 𝑛 ≥ 3:
𝑎𝑛 = 𝑎𝑛−1 + 𝑎0 + 𝑎1 + ⋯+ 𝑎𝑛−3 + (2
0 + 21+…+ 2𝑛−3)
𝑎𝑛 = 𝑎𝑛−1 + σ𝑘=0
𝑛−3 𝑎𝑘 + σ𝑘=0
𝑛−3 2𝑘 (este último somatório é uma PG)
𝒂𝒏 = 𝒂𝒏−𝟏 + 𝒂𝟎 + 𝒂𝟏 + ⋯ + 𝒂𝒏−𝟑 + (𝟐
𝒏−𝟐 − 𝟏)
b) As condições iniciais são: 
𝑎0 = 𝑎1 = 𝑎2 = 0. 
0 ******* 𝒂𝒏−𝟏
100 ****** 𝒂𝒏−𝟑
101 ****** 𝟐𝒏−𝟑
1100 ***** 𝒂𝒏−𝟒
1101 ***** 𝟐𝒏−𝟒
11100 **** 𝒂𝒏−𝟓
11101 **** 𝟐𝒏−𝟓
... ...
Notar que os casos listados na tabela acima precisam:
a) Ser mutuamente exclusivos;
b) Abranger todas as diferentes situações que 
satisfazem os requisitos do enunciado.
6/27/2019 29Exercícios - Relações de Recorrência
Exercício 9 (cont.)
a) Encontre uma relação de recorrência para o número de cadeias 𝒂𝒏 de 𝒏
bits que contenham a cadeia 101. b) Quais são as condições iniciais?
c) Quantas cadeias de 7 bits existem contendo a cadeia 101?
a) e b) A relação de recorrência e as condições iniciais são: 𝒂𝟎= 𝒂𝟏 = 𝒂𝟐 = 𝟎
𝒂𝒏 = 𝒂𝒏−𝟏 + 𝒂𝟎 + 𝒂𝟏 + ⋯ + 𝒂𝒏−𝟑 + (𝟐
𝒏−𝟐 − 𝟏)
c) Podemos calcular de 𝑎3 a 𝑎7 usando a relação de recorrência: 
𝑎3 = 𝑎2 + 𝑎0 + (2
3−2 − 1) = 0 + 0 + 1 = 1
𝑎4 = 𝑎3 + 𝑎0 + 𝑎1 + (2
4−2 − 1) = 1 + 0 + 0 + 3 = 4
𝑎5 = 𝑎4 + 𝑎0 + 𝑎1 + 𝑎2 + (2
5−2 − 1) = 4 + 0 + 0 + 0 + 7 = 11
𝑎6 = 𝑎5 + 𝑎0 + 𝑎1 + 𝑎2 + 𝑎3 + (2
6−2 − 1) = 11 + 0 + 0 + 0 + 1 + 15 = 27
𝑎7 = 𝑎6 + 𝑎0 + 𝑎1 + 𝑎2 + 𝑎3 + 𝑎4 + (2
7−2 − 1) = 27 + 0 + 0 + 0 + 1 + 4 + 31 = 63
𝑎7 = 63
6/27/2019 30Exercícios - Relações de Recorrência
Exercício 10
a) Encontre uma relação de recorrência para o saldo devedor 𝑫𝒏 ao fim de 𝒏
meses de um empréstimo de 𝑳 reais com taxa de juros mensal de r se for feito
um pagamento de valor P a cada mes. 
b) Determine o valor de P para que o empréstimo seja pago em T meses.
6/27/2019 31Exercícios - Relações de Recorrência
Exercício 10
a) Encontre uma relação de recorrência para o saldo devedor 𝑫𝒏 ao fim de 𝒏
meses de um empréstimo de 𝑳 reais com taxa de juros mensal de r se for feito
um pagamento de valor P a cada mes. 
A relação de recorrência é 𝐷𝑘 = (1 + 𝑟)𝐷𝑛−1−𝑃
b) Determine o valor de P para que o empréstimo seja pago em T meses.
Vamos resolver a equação de recorrência:
Solução Homogênea
𝛼𝑛 = (1 + 𝑟)𝛼𝑛−1 → 𝛼𝑛 − 1 + 𝑟 𝛼𝑛−1 = 0 → 𝛼 = (1 + 𝑟)
ℎ 𝑘 = 𝐵0 1 + 𝑟
𝑛
Solução Particular
𝑝 𝑘 = 𝐴0 𝐴0 = 𝐴0 1 + 𝑟 − 𝑃 → 𝐴0 =
𝑃
𝑟
𝑝 𝑘 =
𝑃
𝑟
Solução Completa (com 𝐷 1 = 𝐿) 
𝐷 𝑛 = 𝐵0 1 + 𝑟
𝑛 +
𝑃
𝑟
𝐷 1 = 𝐵0 1 + 𝑟
1 +
𝑃
𝑟
= 𝐿 → 𝐵0 =
𝐿𝑟−𝑃
𝑟(1+𝑟)
𝐷 𝑛 =
𝐿𝑟 − 𝑃
𝑟(1 + 𝑟)
1 + 𝑟 𝑛 +
𝑃
𝑟
=
𝐿𝑟 − 𝑃
𝑟
1 + 𝑟 𝑛−1 +
𝑃
𝑟
= 𝐿 1 + 𝑟 𝑛−1 − 𝑃
1 + 𝑟 𝑛−1 − 1
𝑟
𝐷 𝑛 =
𝐿𝑟−𝑃
𝑟
1 + 𝑟 𝑛−1 +
𝑃
𝑟
Assumimos que o devedor começaria a pagar a partir do 2o mês. Queremos:
𝐷 𝑇 =
𝐿𝑟−𝑃
𝑟
1 + 𝑟 𝑇−1 +
𝑃
𝑟
= 0
1 + 𝑟 𝑇−1 − 𝑃
1+𝑟 𝑇−1−1
𝑟
= 0 → 𝐿 1 + 𝑟 𝑇−1 = 𝑃
1+𝑟 𝑇−1−1
𝑟
𝑃 =
𝑟 1+𝑟 𝑇−1
1+𝑟 𝑇−1−1
𝐿
6/27/2019 32Exercícios - Relações de Recorrência
Exercício 10 (cont.)
6/27/2019 33Exercícios - Relações de Recorrência
Exercício 11
Variação do Problema da Torre de Hanói com 4 pinos e n discos (algoritmo
de Frame-Steward). Mover os n discos do pino 1 para o pino 4 (usando os 4
pinos) sem que nenhum disco maior fique sobre um disco menor.
Este algoritmo depende da escolha de um inteiro k, tal que 1 ≤ k ≤ n. Se há
somente um disco mova-o do pino 1 para o pino 4 (e pronto!). Se n > 1,
execute os três passos seguintes:
1) Mova recursivamente n − k discos do pino1para o pino2 (usandoos4 pinos).
2) Mova recursivamente os k discos restantes no pino 1 para o pino 4 usando
o algoritmo do problema da Torre de Hanói original (usando pinos 1, 3 e 4).
3) Mova recursivamenteosn − k discos do pino2 para o pino4 (usandoos4 pinos).
Determine a relaçao de recorrência para este algoritmo.
6/27/2019 34Exercícios - Relações de Recorrência
Exercício 11
Variação do Problema da Torre de Hanói com 4 pinos e n discos (algoritmo
de Frame-Steward). Mover os n discos do pino 1 para o pino 4 (usando os 4
pinos) sem que nenhum disco maior fique sobre um disco menor.
Este algoritmo depende da escolha de um inteiro k, tal que 1 ≤ k ≤ n. Se há somente um disco
mova-o do pino 1 para o pino 4 (e pronto!). Se n > 1, execute os três passos seguintes:
1) Mova recursivamente n − k discos do pino 1 para o pino 2 (usando os 4 pinos).
2) Mova recursivamente os k discos restantes no pino 1 para o pino 4 usando o 
algoritmo do problema da Torre de Hanói original (usando pinos 1, 3 e 4).
3) Mova recursivamente os n − k discos do pino 2 para o pino 4 (usando os 4 pinos).
Determine a relaçao de recorrência para este algoritmo.
Resolução: Queremos encontrar a relação de recorrência Hn = f (Hn , Hn-1 , …, H2, H1) + g(n).
A operação do item 1 custa Hn-k movimentos. Aoperação do item 2 custa 2
k – 1 movimentos
(soluçãodo problema original). Finalmente, a operação do item 3 custa outros Hn-k movimentos.
Assim temos: Hn = 2Hn-k + 2
k – 1
6/27/2019 35Exercícios - Relações de Recorrência
Exercício 11a
Resolver a relação de recorrência linear não-homogênea: Hn = 2Hn – k + 2
k – 1
Solução homogênea associada:
𝜶𝒏 = 𝟐𝜶𝒏−𝒌 → 𝛼𝑛 − 2𝛼𝑛−𝑘 = 0 → 𝛼𝑘 − 2 = 0 → 𝛼 = 2
1
𝑘
Daí: ℎ 𝑛 = 𝐵2
𝑛
𝑘
Solução particular: (a raiz da equação característica de h(n) não é igual a 1)
𝒑(𝒏) = 𝑨 Substituindo esta expressão na relação de recorrência original vem:
𝐴 = 2𝐴 + 2𝑘 − 1 Vamos calcular os valores de A e de p(n)
−𝐴 = 2𝑘 − 1 → 𝐴 = 1 − 2𝑘 𝑝 𝑛 = 1 − 2𝑘
Agora usamos a condição inicial (H1 = 1) para calcular a constante B
𝑆𝑐 𝑛 = 𝐻𝑛= ℎ 𝑛 + 𝑝 𝑛 = 𝐵2
𝑛
𝑘 + 1 − 2𝑘 → 𝐻1= 1 = 𝐵2
1
𝑘 + 1 − 2𝑘 → 𝐵 = 2
𝑘2−1
𝑘
𝑆𝑐 𝑛 = ℎ 𝑛 + 𝑝 𝑛 = 2
𝑘2−1
𝑘 2
𝑛
𝑘 + 1 − 2𝑘 (para n ≥ 1) ou 𝑯𝒏 = 𝟐
𝒏+(𝒌𝟐−𝟏)
𝒌 + 𝟏 − 𝟐𝒌
6/27/2019 36Exercícios - Relações de Recorrência
Exercício 11b
Este algoritmo depende da escolha de um inteiro 𝑘, tal que 1 ≤ 𝑘 ≤ 𝑛. 
Pode ser demonstrado que o menor número de movimentos para este 
algoritmo é obtido quando k é igual ao menor inteiro tal que 𝒏 ≤
𝒌(𝒌+𝟏)
𝟐
.
Qual o menor número de movimentos que podem ser realizados para 
implementar este algoritmo se 𝒏 = 𝟑𝟑? 
Para 𝑛 = 33 temos que 
𝑘(𝑘+1)
2
≥ 33 → 𝑘 = 8
𝑯(𝒏) = 𝟐
𝒏+(𝒌𝟐−𝟏)
𝒌 + 𝟏 − 𝟐𝒌
𝑯𝒎𝒊𝒏 𝟑𝟑 = 𝟐
𝟑𝟑+(𝟖𝟐−𝟏)
𝟖 + 𝟏 − 𝟐𝟖 = 𝟐
𝟗𝟔
𝟖 − 𝟓𝟏𝟏 = 𝟐𝟏𝟐 − 𝟓𝟏𝟏
𝑯𝒎𝒊𝒏 𝟑𝟑 = 𝟑𝟖𝟒𝟏