Re: [obm-l] Recorrência

[Júnior <jssouza1@xxxxxxxxx>]

Comecei a estudar isso a pouco tempo, seguindo pequenas anotaçoes
feitas pelo meu prof de um pequeno  curso que estou fazendo. Quais
são os bons livros q tratam disso ?

Júnior.

Em 01/10/05, Carlos Yuzo Shine <cyshine@yahoo.com> escreveu:

Oi gente,

Bom, primeiro, pelo que entendi, a equação de
recorrência é
   a_n = 2*a_{n-1}*cos(b) - a_{n-2}.
Certo?

Tem uma maneira mais sistemática para resolver essas
recorrências, mas esse em particular dá para fazer por
indução.

O meu chute é que a_n = cos(nb). De fato, supondo por
indução que tal fato é verdadeiro para n=k-1 e n=k,
temos
  a_{k+1} = 2*a_k*cos(b) - a_{k-1}
          = 2*cos(kb)*cos(b) - cos((k-1)b)

Lembrando que 2*cos(a)*cos(b) = cos(a+b) - cos(a-b),
temos
  a_{k+1} = cos(kb + b) + cos(kb - b) - cos(kb - b)
          = cos((k+1)b)

Observando ainda que a base de indução está nos
valores iniciais n=1 e n=2 (precisamos de dois valores
consecutivos para essa indução!), o resultado segue
por indução.

A maneira "canônica" de resolver recorrências desse
tipo (ou seja, a_n = c*a_{n-1} + d*a_{n-2}, sendo que
c e d não dependem de n), é a seguinte: a equação
característica da recorrência
   a_n = 2*a_{n-1}*cos(b) - a_{n-2}.
é obtida "trocando subscrito por expoente":
   x^n = 2*x^{n-1}*cos(b) - x^{n-2}

Soluções nulas dessa equação não nos interessam.
Assim, queremos na verdade as raízes da equação
   x^2 = 2*cos(b)*x - 1
<=>x^2 - 2*cos(b)*x + 1 = 0,
que são x_1 = cos(b)+i*sen(b) e x_2 = cos(b)-i*sen(b)
(sim, valem raízes complexas!). Assim, pode-se provar
que
   a_n = c_1(x_1)^n + c_2(x_2)^n,
sendo c_1 e c_2 constantes (nesse caso, algo que não
depende de n). Para achar tais constantes, basta
resolver o sistema linear obtido quando substituímos n
por 1 e 2, por exemplo:
   n=1: cos(b) = c_1(cos(b)+i*sen(b))
               + c_2(cos(b)-i*sen(b))
   n=2: cos(2b) = c_1(cos(2b)+i*sen(2b))
                + c_2(cos(2b)-i*sen(2b))

Aqui, utilizamos a fórmula de deMoivre: para n
inteiro,
   (cos(b)+i*sen(b))^n = cos(nb)+i*sen(nb),
de modo que
   a_n = c_1(cos(nb)+i*sen(nb))
       + c_2(cos(nb)-i*sen(nb))

Resolvendo o sistema chegamos em c_1 = c_2 = 1/2 e
fazendo as contas, chegamos em a_n = cos(nb).

[]'s
Shine

--- Júnior <jssouza1@gmail.com> wrote:

> Alguém poderia resolver essa recorrência ?
> a_n = 2(cos b)a_n-1 - a_n-2 , para n >= 3 , a_1=cos
> b , a_2 = cos 2b
>
> Júnior.
>





______________________________________________________
Yahoo! for Good
Donate to the Hurricane Katrina relief effort.
http://store.yahoo.com/redcross-donate3/

=========================================================================
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
=========================================================================