1-Encontre os termos seguintes em cada P.A: a)(x, -3x, ? , ? , ? , ? ) b)(a , a+1, ? , ? , ? )
Soluções para a tarefa
Resposta:
Nao sei foi mal desculpas :):):):)
Resposta:
ExplicGabarito da Lista de Exercícios sobre Recursão e
Relação de Recorrência
1. Encontre a fórmula fechada das seguintes relações de recorrência:
(a)
an = 3an−1
a0 = 1
(b)
an = −2an−1
a0 = 3
(c)
an = an−1 + n − 1 , para n ≥ 2.
a1 = 0
(d)
an = an−1 + 2n
a0 = 1
(e)
an = an−1 + 2(n − 1)
a0 = 1
(f)
T(n) = 2T(n − 1)
T(1) = 2
2. Considere n quadrados dispostos lado a lado, como mostra a figura:
Seja an = número de maneiras de colorir os quadrados de forma que não
fiquem dois quadrados vermelhos adjacentes. Encontre uma relação de
recorrência para an se cada quadrado pode ser colorido de vermelho ou
azul. Justifique.
Resposta: Uma fila de tamanho 1 pode conter ou um peça vermelha,
ou uma peça azul, portanto a1 = 2. Uma fila de tamanho 2 pode ter
qualquer um dos seguintes formatos: (Azul, azul) ou (azul, vermelho)
ou (vermelho, azul). Logo, a2 = 3.
A fila com n peças, para n ≥ 3, pode ser dividida em dois grupos, a que
termina com uma peça azul e a que termina com uma peça vermelha.
Se a última (n-ésima) peça da fila é azul, as demais n − 1 peças da fila
podem ter qualquer coloração desde que não existam peças vermelhas
consecutivas, este total de colorações é an−1. Se a última (n-ésima)
peça da fila é vermelha, obrigatoriamente, a penúltima peça deve ser
azul. Logo, as demais n − 2 peças da fila podem ter qualquer coloração desde que não existam peças vermelhas consecutivas, este total de
colorações é an−2.
Pelo princípio aditivo, an = an−1 + an−2 para n ≥ 3.
Logo,
an = an−1 + an−2 , para n ≥ 3
a1 = 2, a2 = 3
3. Suponha que uma moeda seja lançada até que apareçam 2 caras, quando
o experimento termina.
(a) Seja an o número de experimentos que terminam no n-’ésimo lançamento ou antes. Encontre uma relação de recorrência para an.
Justifique.
Observe por exemplo, que a3 é o número de experimentos que
terminam no segundo ou terceiro lançamento, ou seja, é a soma
de cc, cCc e Ccc onde c significa ‘cara’ e C ‘coroa’.
Resposta: Os experimentos contados em an dividem-se em dois
conjuntos disjuntos, experimentos onde as duas caras foram obtidas até o (n−1)-ésimo lançamento, onde existem an−1 experimentos deste tipo, e experimentos onde a segunda cara foi obtida no
n-ésimo lançamento, e nestes experimentos só foi obtida uma cara
até o (n − 1)-ésimo lançamento, logo existem n − 1 experimentos
deste tipo.
Pelo princípio aditivo, temos que an = an−1 + n − 1.
Observe que a1 = 0. Portanto, a relação de recorrência para an é:
an = an−1 + n − 1 , para n ≥ 2.
a1 = 0
(b) Calcule a fórmula fechada da relação de recorrência. Justifique.
Resposta: Temos que an = an−1 + n − 1, logo:
an = an−1 + n − 1 =
= an−2 + (n − 2) + (n − 1) =
= an−2 + 2n − (2 + 1) =
= an−3 + (n − 3) + 2n − (2 + 1) =
= an−3 + 3n − (3 + 2 + 1) =
= an−4 + (n − 4) + 3n − (3 + 2 + 1) =
= an−4 + 4n − (4 + 3 + 2 + 1) =
.
.
.
= an−i + in − (i + (i − 1) + (i − 2) + . . . + 3 + 2 + 1) =
= an−i + in −
Pi
k=1 k
Tomando n − i = 1, temos i=n-1 .
Logo, an = a1 + (n − 1)n −
Pn−1
k=1 k.
Como Pn
k=1 k =
n(n+1)
2
, então an = a1 + n(n − 1) −
(n−1)n
2 ⇒ an =
0 + 2n(n−1)−n(n−1)
2 =
n(n−1)
2
.
4. Um certo banco está cobrando 5% de juros ao mês. Tadeu tomou
emprestados 1000 reais, e deve pagar prestações mensais fixas de 100
reais (a primeira ao final do primeiro mês de empréstimo).
(a) Encontre uma relação de recorrência e condições iniciais para a
dívida de Tadeu ao final do n-ésimo mês. Justifique.
Resposta: Seja Mi a quantia que Tadeu deve ao banco no final do
i-ésimo mês, para i ≥ 1. A cada mês o banco cobra t = 5% de
juros e subtrai o valor da prestação paga por Tadeu no valor de
c = 100, 00. Portanto:
M0 = 1000
M1 = M0 + 0, 05M0 − 100
= (1 + 0, 05)M0 − 100
= 1, 05M0 − 100
M2 = M1 + 0, 05M1 − 100
= (1 + 0, 05)M1 − 100
= 1, 05M1 − 100
.
.
.
Mi = Mi−1 + 0, 05Mi−1 − 100
Mi = 1, 05Mi−1 − 100
Temos portanto a seguinte relação de recorrência para Mi
:
M0 = 1000
Mi = 1, 05Mi−1 − 100, para i ≥ 1.
(b) Resolva esta relação. Justifique.
Resposta: Dado i ≥ 1, temos:
Mi = 1, 05Mi−1 − 100 =
= 1, 05[1, 05Mi−2 − 100] − 100 =
= 1, 052Mi−2 − 1, 05 × 100 − 100 =
= 1, 052Mi−2 − 100[1, 05 + 1] =
= 1, 052
[1, 05Mi−3 − 100] − 100[1, 05 + 1] =
= 1, 053Mi−3 − 100[1, 052 + 1, 05 + 1] =
= 1, 053
[1, 05Mi−4 − 100] − 1, 05[1, 052 + 1, 05 + 1] =
= 1, 054Mi−4 − 100[1, 053 + 1, 052 + 1, 05 + 1] =
.
.
.
= 1, 05kMi−k − 100[1, 05k−1 + 1, 05k−2 + . . . + 1, 051 + 1, 050
] =
= 1, 05kMi−k − 100Pk−1
j=0 1, 05j
Como o valor inicial é M0 = 1000, então para escrever Mi em termos de M0 devemos tomar i−k = 0, isto é, k = i. Desta maneira,
obtemos a seguinte fórmula fechada para Mi
:
Mi = 1, 05kM0 − 100Pi−1
j=0 1, 05j =
= 1, 05i1000 − 100
1,050
[1,05i−1]
1,05−1
=
= 1, 05i1000 − 100
1,05i−1
1,05−1
Pois, Pi−1
j=0 1, 05j
é os primeiros i termos de uma progressão geométrica de razão 1, 05. Logo:
Mi = 1, 05i1000 − 2000 × [1, 05i − 1] =
= 1, 05i1000 − 2000 × 1, 05i + 2000 =
= 2000 − 1, 05i1000ação passo-a-passo: