Ytuy

Matemáticas Discretas II Capitulo III Relaciones de recurrencia

Relaciones de Recurrencia
Definición 1
Una relación de recurrencia para la secuencia {an} es una ecuación que expresa an en términos de uno o mas de los términos previos de la secuencia (a0, a1, ....., an-1), para todos los enteros n con n≥n0, donde n0 es un entero no negativo. Una secuencia es llamada una solución de unarelación de recurrencia si sus términos satisfacen la relación de recurrencia. Ejemplo1: Sea {an} una secuencia que satisface la relación de recurrencia an= an-1-an-2 para n=2, 3, 4, ... y suponga que a0=3 y a1=5. determinar a2 y a3. R// a2=2 y a3=-3 Ejemplo2: Determine si la secuencia {an} es una solución de la relación de recurrencia an= 2an-1-an-2 para n=2, 3, 4 ....., donde an= 3n para cada entero nno negativo. R// suponga que an= 3n para cada entero n no negativo. Entonces para n≥2 vemos que: 2an-1-an-2 = 2(3(n-1)) –(3(n-2)) = 6n-6-3n+6 = 3n = an , por lo tanto, {an}, donde an= 3n, es una solución de la relación de recurrencia. Ejemplo3: Determine si la secuencia {an} es una solución de la relación de recurrencia an= 2an-1-an-2 para n=2, 3, 4 ....., donde an= 2n para cada entero n nonegativo. R// suponga que an= 2n para cada entero n no negativo. Entonces para n≥2 vemos que: 2an-1-an-2 = 2(2n-1) –(2n-2) = 2(21)–(20) = 3 ≠ an = 4, por lo tanto, {an}, donde an= 2n, no es una solución de la relación de recurrencia. Ejemplo4: Cuales de las siguientes secuencias {an} son soluciones de la relación de recurrencia an=8an-1-16an-2 ? an= 0 (No) an= 2n (No) an= 4n (Si) an= n4n (Si) Lascondiciones iniciales para una secuencia especifican los términos que preceden al primer termino donde la relación de recurrencia se hace efectiva. Una relación de recurrencia junto con las condiciones iniciales proporcionan una definición recursiva de la secuencia. Ejemplo4: Interés compuesto Suponga que una persona deposita $ 10.000 en una cuenta de ahorros en un banco que produce rendimientos del 11%de interés compuesto anual. Cuánto se tendrá ahorrado al cabo de 30 años ? R// Sea Pn la cantidad de dinero luego de n años. Vemos que {Pn} satisface la relación de recurrencia Pn=(1.11)Pn-1 . En el caso anterior podemos calcular una formula iterativa que nos permita hallar Pn. Pues: P1 = (1.11)P0 P2 = (1.11)P1 = (1.11) (1.11)P0 = (1.11)2 P0 P3 = (1.11)P2 = (1.11) (1.11)2 P0 = (1.11)3 P0. Esfácil ver que Pn = (1.11)n P0. Luego para el problema en cuestión P30 = (1.11)30 (10.000) = $ 228.922,97.

Matemáticas Discretas II Capitulo III Relaciones de recurrencia Ejemplo5: Los conejos y la secuencia de fibonaci Una joven pareja de conejos es colocada en una isla. Un par de conejos no se reproduce hasta que tiene 2 meses de edad. Después que estos tienen los 2 meses de edad, cada par produceun nuevo par. Encuentre una relación de recurrencia para el numero de pares de conejos en la isla al cabo de n meses, asumiendo que ningún conejo muere. R// Denotaremos por fn el numero de conejos después de n meses. Notemos que al finalizar el primer mes el numero de pares es f1=1 Porque ? Igualmente al finalizar el segundo mes el numero de pares es f2=1 Porque ? Para encontrar el numero depares después de n meses adicione al numero de parejas en el mes previo fn-1 el numero pares recién nacidos el cual es equivalente a fn-2, puesto que cada par recién nacido viene de un par de al menos 3 meses de edad. Consecuentemente {fn} satisface la relación de recurrencia: fn = fn-1 + fn-2 para n≥3. (secuencia de fibonaci) Las relaciones de recurrencia pueden ser usadas para contar cadenas de bitsde una longitud especificada que tiene cierta propiedad Ejemplo6: Encuentre una relación de recurrencia y de valores de condición inicial para el numero de cadenas de n bits que no tienen 2 consecutivos 0s. Cuantas son de longitud 5 ?. R// Sea an quien denota el numero de cadenas de longitud n que no tienen 2 0’s consecutivos. Por la regla, este numero es igual a la suma de: Cadenas de...