Re: [obm-l] Contagem(tecnica legal...)

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2002@xxxxxxxxxxxx>]

"E bem legal esta tecnica" e pode ser achada na
Eureka!

 --- "Domingos Jr." <dopikas@uol.com.br>
escreveu: > 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)} 

_______________________________________________________________________
Desafio AntiZona: participe do jogo de perguntas e respostas que vai
dar um Renault Clio, computadores, câmeras digitais, videogames e muito
mais! www.cade.com.br/antizona
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================