|
A recorrência saía mais fácil pensando assim, eu
percebi isso depois que cheguei em x(n + 2) = 2[x(n+1) + x(n)], mas resolvi não
jogar fora o caminho que usei pra chegar nesse resultado...
é bem legal essa técnica, se assumirmos que a
resposta é da forma:
x(n) = a.c^n + b.d^n
então
x(n+1) = c.a.c^n + d.b.d^n
x(n+2) = c².a.c^n + d².b.d^n
e como x(n+2) = 2x(n+1) + 2x(n) temos
c².a.c^n + d².b.d^n = 2c.a.c^n + 2d.b.d^n + 2a.c^n
+ 2b.d^n
agrupando, temos
a.c^n(c² - 2c - 2) + b.d^n(d² - 2d - 2) =
0
se tomarmos c e d como raízes de t² - 2t - 2 = 0
satisfazemos o sistema acima para todo n, depois basta encontrar os valores a e
b que satisfaçam os valores iniciais (base da recorrência).
obrigado pelos comentários, mas eu ainda assim
gostaria de saber como seria feito a análise do coef. de x^n na função geradora
dessa seqüência!
[ ]'d
Seguem alguns
comentarios rapidos sobre esse problema.. Eh provavel que eu tenha errado as
contas (nao conferi e fiz meio rapido), mas desse jeito foi bom que a resposta
ficou simpatica..
Chame de x(n) as palavras de n letras sem dois
A's adjacentes.
Quantas palavras x(n+2) existem?
Se a primeira letra for A, há
duas opções para a segunda letra (B ou C) e a partir daí temos x(n)
opções.
Caso contrário, há duas opções
para a primeira letra (B ou C) e a partir daí temos x(n+1)
opções.
Logo, x(n+2) = 2x(n+1) + 2x(n) (*)
Usar funções geratrizes em
geral não é uma boa técnica para resolver equações lineares de
coeficientes constantes pq nesse caso tem uma teoria mais prática, muito
parecida com a que voce usa para resolver EDOs..
Sem maiores explicacoes sobre
a teoria (qq coisa, de uma lida na Eureka ou mande um email que eu dou mais
detalhes):
Solucoes da
forma t^n: t^2 - 2t - 2 = 0 => t = 1 +- sqrt(3), logo x(n) =
a(1+sqrt(3))^n + b(1-sqrt(3))^n eh solucao de (*) qq que sejam
a,b.
No nosso caso porém, x(1)=3,
x(2)=8 (donde a recorrencia da x(0) = 1) e portanto a+b=1, (a+b) +
(a-b)sqrt(3) = 3 e então
a = (2+sqrt(3))/2sqrt(3) =
(1+sqrt(3))^2/8sqrt(3), b = (-2+sqrt(3))/2sqrt(3) =
-(1-sqrt(3))^2/8sqrt(3)
Logo, x(n) =
[(1+sqrt(3))^(n+2) - (1-sqrt(3))^(n+2)]/8sqrt(3)
Mais legal ainda é que, como
(1-sqrt(3))^(n+2) / 8sqrt(3) eh quase sempre muito pequeno, e x(n) eh inteiro,
voce pode concluir que:
n par: x(n) = Piso
{(1+sqrt(3))^(n+2)/8sqrt(3)}
n impar: x(n) = Teto
{(1+sqrt(3))^(n+2)/8sqrt(3)}
|