relaciones de recurrencia

Relaciones de Recurrencian
OBJETIVO:
Encontrar la fórmula que se adecúe a un
proceso de la vida real; por medio y a partir
de una expresión general para la solución de
cualquier relación.

Relaciones de Recurrencia
Surge debido a que en muchos de los problemas
del cálculo, algunas veces es más fácil el obtener
la especificación de una función numérica en
términos de una relación derecurrencia, que
obtener una expresión general para el valor de
una función numérica
Y por lo tanto es obvio que en una relación de
recurrencia se puede llevar acabo un cálculo paso
por paso para de esta manera llegar a determinar
el valor.

Relaciones de Recurrencia
Una relación de recurrencia para una sucesión:

A = (a0 , a1 , a2 ,...., an ,...)
es una expresión que relaciona an conuno o más
términos precedentes a0 , a1 , a2 ,...., an-1 , para
cualquier n entero mayor o igual que un
entero inicial m.
Los valores de los primeros términos necesarios
para empezar a calcular se llaman condiciones
iniciales

Relaciones de Recurrencia
lineales y Homogéneas
Si
an = c1 an-1 +c2 an-2 + ... + cm an-m + g(n), V n≥m
Donde cm son constantes, se dice que la relación derecurrencia es lineal y de coeficientes constantes.
Si además g(n)=0 se dice que la relación es
homogénea.

Relaciones de Recurrencia
lineales y No Homogéneas
Si
an = c1 an-1 +c2 an-2 + ... + cm an-m + g(n)
Donde cm es constante, y g(n)≠0.

A la relación que resulta de eliminar g(n), es decir,
an = c1 an-1 +c2 an-2 + ... + cm an-m se le llama relación
lineal homogénea asociada.Relaciones de Recurrencia
lineales y No Homogéneas
Si
an = c1 an-1 +c2 an-2 + ... + cm an-m + g(n)
Donde cm es constante, y g(n)≠0.

A la relación que resulta de eliminar g(n), es decir,
an = c1 an-1 +c2 an-2 + ... + cm an-m se le llama relación
lineal homogénea asociada.

Relaciones de Recurrencia
Ejemplo 1:
La sucesión de Fibonacci, se define mediante la
siguiente relación de recurrenciaCon la siguientes condiciones iniciales
y

Relaciones de Recurrencia
Ejemplo 2:
Una persona invierte $1000 a 12% compuesto
anualmente. Si An representa la cantidad al final
de n años, determinar una relación de recurrencia
y las condiciones iniciales que definan la
sucesión { An }.
Al final de n – 1 años, la cantidad es An-1 .
Después de un año más, tendremos la cantidad
An-1, máslos intereses. Así
An = An-1 + (0,12)An-1, n ≥ 1

Relaciones de Recurrencia
Ejemplo 2:
Para aplicar está relación de recurrencia a n = 1,
se necesita saber el valor de A0 . Como A0 es la
cantidad del principio, obtenemos la condición
inicial:
A0 = 1000
La condición inicial y la relación de recurrencia
de la ecuación, nos permiten calcular el valor de
An para cualquier n.

Relacionesde Recurrencia

Por Ejemplo:
A3= (1,12) A2 = (1,12)(1,12)A1 = (1,12)(1,12)(1,12)A0
= (1,12)3(1000) = 1.404,93

Relaciones de Recurrencia
Por Ejemplo:
A3= (1,12) A2 = (1,12)(1,12)A1 = (1,12)(1,12)(1,12)A0
= (1,12)3(1000) = 1.404,93
Se observa que en algunas ocasiones se puede
deducir una fórmula explícita a partir de una
relación de recurrencia y las condiciones
iniciales.Relaciones de Recurrencia
1.- ¿Cuáles son los tipos de relaciones de
recurrencia que existen?
Relaciones lineales y Relaciones No lineales.

2.- ¿A que tipo de relación se puede asociar una
relación de recurrencia No homogénea?
Se puede asociar a una relación Homogénea.

3.- ¿Qué elementos relaciona una relación de
recurrencia?
Relaciona el n-ésimo elemento de una sucesión con suspredecesores.

Relaciones de Recurrencia
5.- Determine una relación de recurrencia y las
condiciones iniciales que generan una nueva
sucesión que comience con los términos dados:

3, 7 , 11, 15
An = An-1 + 4 ; A1 = 3

Relaciones de Recurrencia

6- La siguiente sucesión S1, S2, …, Sn donde Sn
denota el número de cadenas de n-bits que no
contienen al patrón 010. Calcule S1, S2, S3 y S4.
S1...