Re: equações de recorrência

[Fábio Arruda de Lima <fabioarruda@xxxxxxxxxxxxxxxx>]

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 <mathfire@ig.com.br>
To: <obm-l@mat.puc-rio.br>
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
>
>