Re: [obm-l] Eureka 01

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] Eureka 01

Sua duvida eh sobre equacoes de recorrencia. De uma olhada na Eureka 09.

De qualquer forma, a ideia eh a seguinte:
Dada a recorrencia: P(n) = P(n-1) + 2*P(n-2), parece ser bem razoavel que procuremos solucoes da forma P(n) = x^n, para algum x real.

Por que isso eh razoavel?
Porque se tivessemos, por exemplo, a recorrencia de 1a. ordem (ou seja, P(n) expresso apenas em funcao de P(n-1)) P(n) = k*P(n-1), a solucao seria obviamente da forma P(n) = A*k^n. Logo, talvez valha a pena tentar uma solucao da mesma forma para uma recorrencia de 2o. ordem onde P(n) eh expresso como funcao de P(n-1) e P(n-2))

Se uma tal solucao existir, entao vai valer x^n = x^(n-1) + 2*x^(n-2), certo?
Dividindo por x^(n-2) e passando tudo pro lado esquerdo, voce fica com:
x^2 - x - 2 = 0.
Isso significa que se existir x tal que P(n) = x^n, ele soh poderah ser -1 ou 2.

Jah que temos dois valores possiveis para x, que tal testar uma combinacao linear deles, justamente da forma P(n) = A*(-1)^n + B*2^n, onde A e B sao parametros reais a serem determinados. 
Por que uma combinacao linear?
Porque se (-1)^n e 2^n satisfazem a recorrencia P(n) = P(n-1) + 2*P(n-2), entao qualquer combinacao linear deles tambem vai satisfazer. Pode conferir.

E como determinar A e B? 
Simples: a partir das condicoes iniciais: P(3) = 6 e P(4) = 18.
Resolvendo o sisteminha resultante, achamos A = 2 e B = 1, donde:
P(n) = 2*(-1)^n + 2^n.

Repare que a argumentacao acima nao provou nada. Apenas apresentou uma forma plausivel de se "adivinhar" a solucao da equacao de recorrencia. No entanto, pode-se provar que esta eh "a" solucao, ou seja, que a solucao achada acima eh unica.

[]s,
Claudio.

on 18.06.04 13:20, Faelccmm@aol.com at Faelccmm@aol.com wrote:

> Claudio, 
>
> Algumas de minhas duvidas estao no corpo de sua resolucao. 
>
>
>
> Em uma mensagem de 16/6/2004 09:46:16 Hora padrão leste da Am. Sul, claudio.buffara@terra.com.br escreveu: 
>
> [...]
>
> Assim, temos a recorrencia: P(n) = P(n-1) + 2*P(n-2). 
> Juntamente com P(3) = 6 e P(4) = 18, podemos achar P(n) para qualquer n. 
>
> Equacao caracteristica: x^2 - x - 2 = 0 (De onde voce tirou esta equacao caracteristica ? *Equacao caracteristica* eh um conceito ou uma expressao utilizada por voce ?) ==> 
> raizes: -1  e  2 ==> 
> P(n) = A*(-1)^n + B*2^n. (Por que aqui voce fez A*[raiz_1]*(-1)^n + B*[raiz_2]^n ? Quem sao estes A´s e B´s ? Qual a logica desta equacao ? 
>
> P(3) = -A + 8B = 6 
> P(4) = A + 16B = 18 ==> A = 2  e  B = 1 ==> 
>
> P(n) = 2*(-1)^n + 2^n ==> 
>
> P(10) = 1026 ==> alternativa (c). 
>
> []s, 
> Claudio.