Lista 17 - recorrências

Prévia do material em texto

Relac¸o˜es de Recorreˆncia - Sec¸o˜es 7.1 e 7.2
1) Considere
{
a0 = 3
an = 2an−1 + 3
. Encontre uma fo´rmula fechada e prove por induc¸a˜o.
2) a) Considere um tabuleiro de xadrez com 2 linhas e n colunas. De quantas formas podemos
ladrilhar o tabuleiro com domino´s?
b) Considere um tabuleiro de xadrez com 2 linhas e n colunas. De quantas formas podemos ladri-
lhar o tabuleiro com domino´s?
3) Considere
{
E1 = 1
En = 2En−1 + 2n−1.
Prove por induc¸a˜o que En = n · 2n−1.
4) Considere
{
E0 = 1
En = 3(En−1)2.
Prove por induc¸a˜o que En = 3
2n−1.
5) Considere um investimento com retorno de 2% a.m. Sabendo que foram investidos inicialmente
$1000 e que sa˜o feitas aplicac¸o˜es mensais de $100, encontre uma relac¸a˜o de recorreˆncia e procure uma
fo´rmula fechada para S(n), onde S(n) e´ o saldo no n-esimo meˆs.
6) Encontre uma fo´rmula fechada para a sequeˆncia an:
a0 = 3
a1 = 4
an = 4an−1 − 4an−2 + 4n
7) Encontre uma fo´rmula fechada para a sequeˆncia an:
a0 = 3
a1 = 4
an = 4an−2 + 3n
8) Encontre uma fo´rmula fechada para a recorreˆncia:{
a0 = 3
an = 2an−1 + n2
9) Encontre uma fo´rmula fechada para a recorreˆncia:{
a0 = 1
an = 6an−1 − 9an−2 + 3n
10) Uma pessoa sai com uma quantia Q em reais a`s compras e gasta, na primeira loja que entra,
metade dessa quantia mais um real. Na segunda loja gasta metade do que sobrou e mais um real e
prossegue com exatamente essa dinaˆmica nas demais lojas que entra. Ao sair da de´cima e u´ltima loja,
a pessoa percebe que na˜o tem mais dinheiro algum. Seja xn a quantidade de dinheiro que a pessoa
tem ao sair da loja n.
a) Expresse xn+1 por uma fo´rmula recursiva e por uma fo´rmula fechada, em func¸ao˜ de Q.
b) Determine o valor de Q.
1
11) O Floco de Neve de Koch e´ uma figura que comec¸a a ser constru´ıda a partir de um triaˆngulo
equila´tero. O passo-a-passo para constru´ı-lo e´ o seguinte:
i) Dividir cada lado da figura em 3 segmentos de igual comprimento.
ii) Desenhar um triaˆngulo equila´tero em que o segmento central servira´ de base.
iii) Apagar o segmento que serviu de base para o triaˆngulo do passo ii.
iv) Repetir passo i.
Considerando um triaˆngulo equila´tero inicial de lado L:
a) Encontre relac¸o˜es de recorreˆncia e fo´rmulas fechadas a a´rea e per´ımetro da figura em cada passo
da construc¸a˜o.
b) Verifique que, no limite, a a´rea converge e o per´ımetro diverge.
12) Um mastro de 20 metros de comprimento sera´ totalmente coberto por bandeiras. Temos ban-
deiras vermelhas de 1 metro de largura, bandeiras verdes de 2 metros, e bandeiras azuis de 3 metros.
De quantas formas podemos cobrir o mastro?
13) Um mastro de 20 metros de comprimento sera´ totalmente coberto por bandeiras. Temos ban-
deiras vermelhas de 1 metro de largura, bandeiras verdes de 2 metros, e bandeiras azuis de 2 metros.
De quantas formas podemos cobrir o mastro?
14) Calcule
∏n
k=2
(
1 − 1n2
)
.
15) Calcule
∑n
k=0(2k + 1)
2.
16) Prove que 4
n
n+1 <
(
2n
n
)
para todo n > 1.
17) Seja F0 = 3 e Fn =
(∏n−1
k=0 Fk
)
+ 2. Encontre uma fo´rmula fechada para Fn.
18) Calcule o nu´mero de caminhos de A ate´ B que na˜o passam duas vezes pelo mesmo ponto.
2