RES: equações de recorrência

["Eric Campos Bastos Guedes" <mathfire@xxxxxxxxx>]

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