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

Re: [obm-l] RECORRENCIA

Ola Klaus. Eu nao domino muito a teoria de recorrencias, mas seu na pratica.
Quando temos uma recorrencia generica do tipo:  (A_n)=r(A_n-1)+p(A_n-2)
para resolvermos chamamos (A_n) de um numero x^n obtendo a equacao: x^n=rx^(n-1) + px^(n-2)
como x diferente de zero, sobra a equacao: x²-rx-p=0
As raizes(a,b) dessa equacao forma o termo geral da recorrencia da seguinte forma:
(A_n)=i(a)^n +j(b)^n
Sabendo (A_0) e (A_1) conseguimos determinar as constantes i e j, resolvendo entao a recorrencia!
 
No caso da questao, eu fiz o processo inverso. Como sabia que a equacao do termo geral era An=(5^n-3^n)/2  temos que as raizes a e b sao 5 e 3. Logo, montei a equacao cujas raizes sao 5 e 3:  (x-5)(x-3)=x²-8x+15=0   Logo (x²-8x+15)x^(n-2) =0
Substituindo (A_n)=x^n, chegamos à recorrencia A_n=8(A_n-1) -15(A_n-2).
 
 
espero ter ajudado! Renato Lira.


 
On 10/14/05, Klaus Ferraz <klausferraz@yahoo.com.br> wrote:
Claudio,
            como que vc partiu a(n-1)=5*a(n-1)+3^(n-1) e chegou na recorrencia
a(n) - 8*a(n-1) + 15*a(n-2) = 0. Nao entendi os passos q vc fez!

"claudio.buffara" < claudio.buffara@terra.com.br> escreveu:
Outra forma, chegando diretamente à recorrência, é a seguinte:
 
Dada uma sequência com n-1 termos, teremos 3 possibilidades:
 
1. A sequência obedece às condições do enunciado:
Existem a(n-1) tais sequências e o n-ésimo termo pode ser escolhido de 5 maneiras distintas.
Total = 5*a(n-1)
 
2. A sequência não obedece às condições do enunciado:
2a) A sequência não contém nenhum 2 nem nenhum 0:
Existem 3^(n-1) tais sequências e o n-ésimo termo tem que ser 2.
Total = 3^(n-1).
 
2b) A sequência não contém nenhum 2 mas contém algum 0:
Não importa qual seja o n-ésimo termo, esta sequência não dará origem a uma seqûencia válida.
Total = 0.
 
Assim,
a(n-1) = 5*a(n-1) + 3^(n-1) ==>
 
a(n-1) = 5*a(n-2) + 3^(n-2) ==>
3^(n-1) = a(n) - 5*a(n-1) = 3*a(n-1) - 15*a(n-2) ==>
a(n) - 8*a(n-1) + 15*a(n-2) = 0
 
Equação característica: t^2 - 8t + 15 = 0 ==>
raízes: t = 3  e  t = 5 ==>
a(n) = P*3^(n-1) + Q*5^(n-1)
 
Claramente, a(1) = 1  e  a(2) = 8 ==>
a(1) = P + Q = 1
a(2) = 3P + 5Q = 8 ==>
P =  -3/2   e   Q = 5/2 ==>
 
a(n) = (5^n - 3^n)/2
 
[]s,
Claudio.
 
Cópia:
Data: Thu, 13 Oct 2005 22:49:54 -0300
Assunto: Re: [obm-l] RECORRENCIA
> vamos faser o principio fundamental da contagem(PFC) separando em n casos.
O primeiro eh quando o primeiro 2 aparece logo no 1º digito. Apos ele, podem aparecer todos os outros numeros( 0,1,2,3 ou 4)
Logo há 5^(n-1) possibilidades.

No segundo eh quando o primeiro 2 aparece no 2º digito. Antes dele so pode aparecer (1, 3 e 4. o 2 nao pra evitar dupla contatem). Apos ele, podem aparecer todos os outros numeros( 0,1,2,3 ou 4)
Logo há 3.5^(n-2)
e assim por diante...
teremos que (A_n)=5^(n-1) + 3.5^(n-2) + 3².5^(n-3) + ... + 5².3^(n-3) + 5.3^(n-2) + 3^(n-1)
Note que eh uma PG de primeiro termo 5^(n-1) e razao 3/5

Resposta (i): (A_n)=(5^n - 3^n)/2

Se quiser deixar em termo de recorrencia:     (A_n)=8(A_n-1) -15(A_n-2)
com (A_0)=0 e (A_1)=1
>  
> Logo, se quisermos deixar em funcao de (A_n) n e (A_n-1):
> Resposta (ii): (A_n)=8(A_n-1) -15(5^(n-2) - 3^(n-2))/2
com (A_0)=0
>  
>  
> []'z   Renato Lira.
>  
>
 
> On 10/13/05, Adroaldo Munhoz <amunhoz@gmail.com > wrote:
Alguém resolveu esta?
Abraços,
Aldo
>
Danilo Nascimento wrote:
> Seja an o numero  de sequencias de n elementos, todos pertencentes ao conjunto {0,1,2,3,4} tais que:
> (i) há pelo menos um 2 na sequencia
> (ii) se houver um 0 na sequencia, deve haver pelo menos um 2 antes dele.
> Determine
> a) an em funcao de an-1 e n.
> b) an  apenas em funcao de n.

Promoção Yahoo! Acesso Grátis: a cada hora navegada você acumula cupons e concorre a mais de 500 prêmios! Participe!