[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Eureka 01



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.