Una relación de recurrencia para una sucesión {A0, A1, A2, ...} es una fórmula que expresa cada término An a partir de cierto n° E N , en función de uno o más de los términos que le preceden. Los valores de los términos necesarios para empezar a calcular se llaman condiciones iniciales. Se dice que una sucesión es una solución de la relación de recurrencia si su término general verifica dicha relación

La susesión tales como Hn, n=0,1,2,..., suelen darse recursivamente en la forma sigueinte: se enuncian explícitamente los valores iniciales H0,H1,...,Hc-1,

Hn = F(Hn-1, Hn-2, ..., Hn-c,n)

Las relaciones de este tipo se demoninan ecuaciones de recurrencia. Por ejemplo la secuencia de Fibonacci Fn, para n>=0, Los valores iniciales son F0=0 y F1=1 y para n>1, Fn esta dada por:

Fn=Fn-1 + Fn-2

RELACIONES DE RECURRENCIA HOMOGENEAS:

Si se nos da una ralacion de recurrencia para H que implica a Hn-1, Hn-2, ..., Hn-c, entonces siempre se puede hallar Hn directamente,puesto que se dispone de las condiciones iniciales H0,H1,...,Hc-1. Este metodo directo se aplicara acontinuacion para el caso de los numeros de Fibonacci.

EJEMPLO

Calcular los numeros de fibonacci de F2 al F6 utuilizar el hecho consiste en que F0 = 0 y F1 = 1

F2 = F1 + F0 = 1+0 =1

F3 = F2 + F1 = 1+1=2

F4 = F3 + F2 = 2 + 1=3

F5 = F4 + F3 = 3+ 2=5

F6 =F5 + F4 = 5 + 3=8

En la teoria de realciones de recurrencia, uno intenta hallar soluciones no recursivas o explicitas, esto es, soluciones que no exijan el calculo de todos los Hm, mHn,esto es, una formula que no implique a Hn-1, Hn-2, etc. A continuacion vamos a derivar esta formula para las relaciones de recurrencia homogeneas, esto es, para aqullas ecuaciones de recurrencia que se nos da en la formula.

Hn = a1 Hn-1 + a2 Hn-2 + ...+ ac Hn-c

EJEMPLO

1) Para resolver estas ecuaciones sustituimos, X1 y X2 por 1/2 (1+√5) y X2 = 1/2 (1-√5) respectivamente lo cual produce

b1 +b2 =0

b1 1/2 (1+√5) + b2 1/2 (1-√5) =1

2) L a solucion de esta ecuacion resulta ser

b1= 1/√5 b2= - 1/√5

ECUACIONES DE RECURRENCIA NO HOMOGENEAS

Una relacion de recurrencia se denomina no homogenea cuando tiene la forma

Hn= F(n) + a1Hn-1 + a2 Hn-2 + ... + ac Hn-c

Aqui, F(n) no debe ser igua a cero para todo n.Para el presente tratamineto,supondremos que f(n) es un polinomio.Para explorar las posibles soluciones, se supone que Hn crece exponencialmente con un crecimiento que es mayor que la unidad. E n este caso, Hn domina rapidamente al polinomio f(n), que se puede ignorar a partir de este momento. Esto de lugar a la siguiente relacion homogenea de recurrencia, que se domina realcion de recurrencia complementaria.

Hn = a1 Hn-1 + a2Hn-2 + ...+ac Hn-c

Esta relacion es ciertamente relevante cuando Hn alcanza valores elevados, pero es posible que tambien lo sea en otras circunstancias. esto sugiere que la solucion de la realcion complemetaria forma  parte de la solucion final. Ademas de esta solucion complemetaria es bien conocido que las ecuaciones de recurrencia no homogeneas tienen soluciones particulares. Estos comentarios como punto de partida para la forma que acontinuacion ofreceremos para H.

Hn = H p^n + b1 X1^n + b2x2^n + ... + bcxc^n

Aqui los X1, 1 ≤ i ≤ n, son las soluciones de la ecuacion caracteristica del problema complementario,y Hn-p es la solucion particular.Esto significa que HΛP,N tiene que satisfacer la relacion de la recurrencia.

Hn^p=f(n) + a1hn-1^p+a2hn-2^p+...+achn-c^p

Un ejemplo especifico es

Hn = c+ aHn-1

En donde Hθ esta dado.En primer lugar se halla la solucion particular H Λpn, que debe ser constante de acuerdo con lo dicho; esto es, Hn^p= d. Ahora hay que hallar la constante d. Sustituyendo Hn por d.

d= c+ad

Esto se puede resolver para d, y entonces se tinene

hn^p=d=c/(1-a)

Acontinuacion hay que dterminar el valor de x, resolviendo el sistema complemetario Hn = a H n-1. Si en esta expresion se sustituye el Hn por X^n se obtiene que x ^n =a x ^-1, lo cual nos lleva a la ecuacion caracteristica proporciona derectamente la solucion para x

Hn= c/(1-a)+ba^n

Aqui es preciso determinar b=b, a partir de la condicion incial H0.

H0 = c/ (1-a)+b

entonces b=H0 -c/(1-a)

consiguiente Hn =c/(1-a)+(H0-c/(1-a))a^n

                                                                                         FUENTE UPC

                                                                                   MATEMATICA DISCRETA Y LOGICA

                                                                                            

                                                                       

R E L A C I O N E S D E R E C U R R E N C I A

View more presentations from jhonricardo.