[obm-l] equações de recorrência
Alguem poderia me ensinar a solucionar equações homogêneas de primeira ordem com coeficientes constantes e equações não homogêneas de primeira ordem com coeficientes constantes . Eu não entendi muito bem na EUREKA! 9. Obrigado. Adriano. __ Quer ter seu próprio endereço na Internet? Garanta já o seu e ainda ganhe cinco e-mails personalizados. DomíniosBOL - http://dominios.bol.com.br = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: equações de recorrência
Sauda,c~oes,
Um livro motivador deste assunto - Recorrências - é o Progressões e Mat.
Financeira
do Morgado, Wagner e Zani, publicado pelo IMPA.
Falo também um pouco sobre isso nos meus livros de Progressão e Indução.
Para as aplicações nas Progressões Aritméticas de ordem k, podemos achar o
termo geral seguindo o exemplo do Fábio. Mas tem uma fórmula que facilita
bastante este cálculo.
Seja determinar o termo geral - a_i - da seqüência
6; 11;35;98;220; (não está em PA/façamos a diferença dos termos dois a
dois)
5,24,63,122 .(não está em PA/façamos a diferença dos termos dois a
dois) Delta a_i
19, 39,59...(PA de 3ª ordem com razão r=20)Delta^2 a_i
20, 20,20,.
Delta^3 a_i
Como é PA de 3ª ordem, vem (a notação assusta mas o exemplo vai esclarecer):
a_i = a_1 + Delta a_1 binom{i-1}{1} + Delta^2 a_1 binom{i-1}{2} + Delta^3
a_1 binom{i-1}{3}
a_i = 6 + 5(i-1) + 19(i-1)(i-2)/2 + 20(i-1)(i-2)(i-3)/6
Calculando a_5, resulta:
a_5 = 6 + 5*4 + 19*4*3/2 + 20*4*3*2/6 = 220.
E lembrando que podemos calcular a_0, vem:
a_0 = 6 - 5 + 19 - 20 = 0
[ ]'s
Lu'is
-Mensagem Original-
De: Fábio Arruda de Lima [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: Sexta-feira, 4 de Maio de 2001 10:02
Assunto: Re: equações de recorrência
Caro Henrique,
complementando o que o Eric colocou, diria que uma recorrência linear de
K-ésima ordem terá como função característica um polinômio de grau de K.
Seria interessante você procurar um livro específico sobre o assunto.
Certamente, tem no IMPA e nas edições da SBM.
Por exemplo, a(n+3) + a(n+2) + a(n+1) + a(n)=0 terá como termo geral da
seqüência algo do tipo A(n)=p*n^3+q*n^2+r*n+s. Lembrei-me de uma aplicação
interessante. Chamamos Prograssão Aritmética de ordem k, aquelas seqüências,
cuja diferença de seus termos está em algum momento (k-ésimo) em PA. Veja
bem, a seqüência não está em PA, somente a diferença de seus termos ou a
diferença da diferença,...Exemplificando, seja a seqüência abaixo:
6;11;35;98;220;(não está em PA/façamos a diferença dos termos dois a dois)
5,24,63,122 .(não está em PA/façamos a diferença dos termos dois a dois)
19,39,59...(PA de 3ª ordem com razão r=20)
Logo, o termo geral será da forma A(n)=a*n^3+b*n^2+c*n+d
A(1)=a+b+c+d=6 (substituindo n=1 e igualando o A1 da sequencia original)
A(2)=8a+4b+2c+d=11 (substituindo n=2 e.)
A(3)=27a+9b+3c+d=35 (n=3)
A(4)=64a+16b+4c+d=98 (n=4)
Resolvendo-se o sistema, temos:
a=20/6; b= - 63/6; c=79/6 ;d=0 = A(n)= 20/6*n^3 - 63/6*n^2+79/6*n
Se quisermos saber o A(5), substituindo n=5, encontramos A(5)=220.
Gostaria de fazer um alerta. Quando nos é dada a seqüência em termos de uma
equação linear envolvendo, em vez dos elementos da sequencia, na forma a
seguir: a(n+3);a(n+2);a(n+1);a(n);a(n-1). Basta observar a variação de
grau, neste caso é 4 (polinômio do 4º grau). No exemplo do Eric, Fibonacci,
foi 2 (polinômio do 2º grau).
Valeu Eric seu exemplo foi legal, um clássico.
Um abraço
Fábio
Re: equações de recorrência
Ola Pessoal,
Saudacoes !
Complementando a mensagem do colega Luis Lopes, e possivel provar facilmente
que se
(A1, A2, A3, A4, ... )
e uma Progressao Aritmetica qualquer de ordem 2 e representarmos por
BINOM(N,P) o numero binomial de numerador N e denominador P, isto e, se
BINOM(N,P)= N!/(P!*(N-P)!), entao :
O termo generico An da progressao sera :
An = A1*BINOM(N-1,0) + (A2-A1)*BINOM(N -1,1) + (A3-2*A2+A1)*BINOM(N-1,2)
Aplicando o Teorema das colunas, chegamos facilmente a formula da soma :
Sn = A1*BINOM(N,1)+ (A2-A1)*BINOM(N,2) + (A3-2*A2+A1)*BINOM(N,3)
Se a progressao for de ordem 3, sera :
An = A1*BINOM(N-1,0) + (A2-A1)*BINOM(N -1,1) + (A3-2*A2+A1)*BINOM(N-1,2)
+ (A4-3*A3+3*A2-A1)*BINOM(N-1,3)
Aplicando o Teorema das colunas, chegamos facilmente a formula da soma :
Sn = A1*BINOM(N,1)+ (A2-A1)*BINOM(N,2) + (A3-2*A2+A1)*BINOM(N,3)
+ (A4-3*A3+3*A2-A1)*BINOM(N,4)
E interessante perceber que a progressao aritmetica de 1 ordem, que sao
aquelas que todos nos vemos em todos os livros, tambem permitem serem
representada assim :
An = A1*BINOM(N-1,0) + (A2-A1)*BINOM(N-1,1)
Sn = A1*BINOM(N,1)+ (A2-A1)*BINOM(N,2)
Mas a maioria dos estudantes esta mais acostumado com as formulas :
An=A1 + (N-1)*Re Sn=( N*(A1 + An))/2
As formulas binomiais me parecem ser melhores porque permitem uma
interpretação dos coeficientes em termos dos termos iniciais da sequencia e
tambem permitem representarem as sequencias como produtos vetorias. Para ver
isso, seja o termo geral de uma PA de 1 ordem :
An= A1*BINOM(N-1,0) + (A2-A1)*BINOM(N-1,1)
Podemos coloca-lo como PRODUTO ESCALAR assim :
An = (A1,A2-A1)*( BINOM(N-1,0),BINOM(N-1,1) )
O vetor (A1,A2-A1) pode ser chamado VETOR CARACTERISTICO da sequencia. A
comparacao entre os vetores caracteristicos de sequencias distintas nos
permitem inferir propriedades de dificil percepcao com o trato canonica com
a qual sao apresentadas estas sequencias...
O estudante ganha tambem porque tem formulas prontas para abordar questoes
que, de sorte, consomem tempo. Exemplificando :
Quanto vale :
S = 2^2 + 5^2 + 8^2 + 11^2 + ... + 149^2 ?
Claramente e uma PA de 2 ordem ( se elevarmos a N todos os termos de uma PA
de ordem K teremos uma PA de ordem N*K ), pois e uma PA de primeira ordem
(2,5,8, ... ) com todos os seus termos elevados a 2. O termo 149 e o
50-esimo termo, logo :
S50=(2^2)*BINOM(50,1)+(5^2 - 2^2)*BINOM(50,2)+(8^2-2*(5^2)+2^2)BINOM(50,3)
S50=4*BINOM(50,1) + 19*BINOM(50,2) + 18*BINOM(50,3)
Agora, tenta calcular a soma acima usando os tecnicas tradicionais ...
Finalmente, uma outra vantagem desta maneira de ver as coisas e que voce nao
fica limitado a sequencias de ordem inteira positiva. So a titulo de
exemplificacao, a famosa sequencia harmonica e, em verdade, uma progressao
aritmetica de ordem -1. Para ver isso, note que :
1 - 1/2 + 1/3 -1/4 + 1/5 - 1/6 + 1/7 CONVERGE ! Converge para Logaritmo
neperiano de 2.
Bom, esse tema de series e sequencias e muitissimo interessante, mas eu nao
acho que se possa abordar isso de forma consistente e responsavel sem se
considerar o Triangulo Pascalino e as Formulas do Tio Euler.
Um Abraco a Todos
Paulo Santa Rita
3,1515,08052001
From: Luis Lopes [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Re: equações de recorrência
Date: Tue, 8 May 2001 14:06:02 -0300
Sauda,c~oes,
Um livro motivador deste assunto - Recorrências - é o Progressões e Mat.
Financeira
do Morgado, Wagner e Zani, publicado pelo IMPA.
Falo também um pouco sobre isso nos meus livros de Progressão e Indução.
Para as aplicações nas Progressões Aritméticas de ordem k, podemos achar o
termo geral seguindo o exemplo do Fábio. Mas tem uma fórmula que facilita
bastante este cálculo.
Seja determinar o termo geral - a_i - da seqüência
6; 11;35;98;220; (não está em PA/façamos a diferença dos termos dois a
dois)
5,24,63,122 .(não está em PA/façamos a diferença dos termos dois a
dois) Delta a_i
19, 39,59...(PA de 3ª ordem com razão r=20)Delta^2 a_i
20, 20,20,.
Delta^3 a_i
Como é PA de 3ª ordem, vem (a notação assusta mas o exemplo vai
esclarecer):
a_i = a_1 + Delta a_1 binom{i-1}{1} + Delta^2 a_1 binom{i-1}{2} + Delta^3
a_1 binom{i-1}{3}
a_i = 6 + 5(i-1) + 19(i-1)(i-2)/2 + 20(i-1)(i-2)(i-3)/6
Calculando a_5, resulta:
a_5 = 6 + 5*4 + 19*4*3/2 + 20*4*3*2/6 = 220.
E lembrando que podemos calcular a_0, vem:
a_0 = 6 - 5 + 19 - 20 = 0
[ ]'s
Lu'is
-Mensagem Original-
De: Fábio Arruda de Lima [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: Sexta-feira, 4 de Maio de 2001 10:02
Assunto: Re: equações de recorrência
Caro Henrique,
complementando o que o Eric colocou, diria que uma recorrência linear de
K-ésima ordem terá como função característica um polinômio de grau de K.
Seria interessante você procurar um livro específico sobre o assunto.
Certamente, tem no IMPA e nas edições da SBM.
Por exemplo, a(n+3) + a(n+2) + a(n+1) + a(n)=0 terá como termo
Re: equações de recorrência
Caro Henrique, complementando o que o Eric colocou, diria que uma recorrência linear de K-ésima ordem terá como função característica um polinômio de grau de K. Seria interessante você procurar um livro específico sobre o assunto. Certamente, tem no IMPA e nas edições da SBM. Por exemplo, a(n+3) + a(n+2) + a(n+1) + a(n)=0 terá como termo geral da seqüência algo do tipo A(n)=p*n^3+q*n^2+r*n+s. Lembrei-me de uma aplicação interessante. Chamamos Prograssão Aritmética de ordem k, aquelas seqüências, cuja diferença de seus termos está em algum momento (k-ésimo) em PA. Veja bem, a seqüência não está em PA, somente a diferença de seus termos ou a diferença da diferença,...Exemplificando, seja a seqüência abaixo: 6;11;35;98;220;(não está em PA/façamos a diferença dos termos dois a dois) 5,24,63,122 .(não está em PA/façamos a diferença dos termos dois a dois) 19,39,59...(PA de 3ª ordem com razão r=20) Logo, o termo geral será da forma A(n)=a*n^3+b*n^2+c*n+d A(1)=a+b+c+d=6 (substituindo n=1 e igualando o A1 da sequencia original) A(2)=8a+4b+2c+d=11 (substituindo n=2 e.) A(3)=27a+9b+3c+d=35 (n=3) A(4)=64a+16b+4c+d=98 (n=4) Resolvendo-se o sistema, temos: a=20/6; b= - 63/6; c=79/6 ;d=0 = A(n)= 20/6*n^3 - 63/6*n^2+79/6*n Se quisermos saber o A(5), substituindo n=5, encontramos A(5)=220. Gostaria de fazer um alerta. Quando nos é dada a seqüência em termos de uma equação linear envolvendo, em vez dos elementos da sequencia, na forma a seguir: a(n+3);a(n+2);a(n+1);a(n);a(n-1). Basta observar a variação de grau, neste caso é 4 (polinômio do 4º grau). No exemplo do Eric, Fibonacci, foi 2 (polinômio do 2º grau). Valeu Eric seu exemplo foi legal, um clássico. Um abraço Fábio Arruda - Original Message - From: Eric Campos Bastos Guedes [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Friday, May 04, 2001 12:06 PM Subject: RES: equações de recorrência serah q alguehm poderia falar um pouco sobre equações de recorrência, sequencias recorrentes? Saudações. Tenho algum material sobre isso. Dúvida: Seja uma recorrência linear de segunda ordem homogênea com coeficientes constantes do tipo Xn+2 + PXn+1 + QXn = 0, com Q diferente de zero. Porquê podemos associar uma equação do segundo grau, r^2 + Pr + Q = 0 (chamada equação característica) para solucionar esse tipo de recorrência ? Solução: suponha que r^2 + Pr + Q = 0 tenha raizes distintas. Sejam x e y essas raizes. Considere as sucessões [1]1,x,x^2,x^3,...,x^n,... [2]1,y,y^2,y^3,...,y^n,... estas sucessões satisfazem a equação de recorrência [3]X(n+2) + P.X(n+1) + Q.X(n) De fato, como x,y são raizes de r^2+Pr+Q=0, vale x^2 + Px + Q = 0 e y^2 + Py + Q = 0 multiplicando as igualdades acima por x^n e y^n, respectivamente, temos [4] x^(n+2) + Px^(n+1) + Qx^n = 0 [5] y^(n+2) + Py^(n+1) + Qy^n = 0 donde as sucessões [1] e [2] satisfazem a relação de recorrência [3]. Uma combinação linear das sucessões [1] e [2] também abedecerá à relação de recorrência [3], isto é, se z(n) = Ax^n + By^n então (z(n)) satisfaz [3]. De fato z(n+2) + Pz(n+1) + Qz(n) = = (Ax^(n+2)+By^(n+2)) + P(Ax^(n+1)+By^(n+1)) + Q(Ax^n+By^n) = = Ax^(n+2) + By^(n+2) + PAx^(n+1) + PBy^(n+1) + QAx^n + QBy^n = = A(x^(n+2) + Px^(n+1) + Qx^n) + B(y^(n+2) + Py^(n+1) + Qy^n) = (e lembrando [4] e [5]) = A.0 + B.0 = 0 + 0 = 0 donde z(n+2) + Pz(n+1) + Qz(n) = 0 e (z(n)) satisfaz [3]. Considere agora uma sucessão (w(n)) qualquer que obedeça a relação de recorrência [3]. Para determinarmos um termo qualquer w(n) em função de n basta determinarmos A e B fazendo w(0)=z(0)=Ax^0+By^0=A+B e w(1)=z(1)=Ax^1+By^1=Ax+By. Se w(0)=z(0) e w(1)=z(1) então w(n)=z(n), para todo n=0. Tomemos, por exemplo, a seqüência de Fibonacci (f(n)) (um termo qualquer é a soma dos dois anteriores, f(n+2)-f(n+1)-f(n)=0). A equação característica é r^2 - r - 1 = 0, cujas raizes são x=(1+raiz(5))/2 e y=(1-raiz(5))/2. Neste caso toda sucessão (z(n)) com z(n)=Ax^n+By^n (combinação linear das sucessões 1,x,x^2,x^3... e 1,y,y^2,y^3...), também satisfaz a equação r^2 - r - 1 = 0. Para certos valores de A e B teremos z(n)=Ax^n+By^n=f(n). Basta determinar A e B então. f(0)=0 = Ax^0+By^0 = A+B f(1)=1 = Ax^1+By^1 = Ax+By Portanto o sistema é [6] A + B = 0 [7] Ax + By = 1 onde as incógnitas são A e B. De [6] tiramos B = -A. Substituindo em [7] temos Ax - Ay = 1 A(x-y) = 1 A = 1/(x-y)=1/raiz(5) donde A=1/raiz(5) e B=-1/raiz(5). Assim f(n) = Ax^n+By^n f(n) = (x^n - y^n)/raiz(5) onde x=(1+raiz(5))/2 e y=(1-raiz(5))/2 Eric Campos Bastos Guedes
equações de recorrência
serah q alguehm poderia falar um pouco sobre equações de recorrência, sequencias recorrentes? _ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.
