Ecuaciones de recurrencia Introducción Comencemos con un ejemplo: Sucesión de Fibonacci: ( an ) = ( 1,1, 2,3,5,8,13,...) Cada término, a partir del tercero, se obtiene sumando los dos anteriores, o sea: an = an − 1 + an − 2 ( n ≥ 3) Una expresión de este tipo, en que el término general de la sucesión se escribe en función de algunos términos anteriores, recibe el nombre de relación de recurrencia, ecuación de recurrencia o ecuación en diferencias. Para obtener un término concreto de una sucesión dada en forma recurrente debemos ir obteniendo todos los anteriores, lo cual no siempre es práctico. ¿Cuál es el término a100 de la sucesión de Fibonacci? Encontrar una solución a la ecuación de recurrencia es determinar una expresión del tipo an = f (n ) en la que el término general dependa solo de la posición que ocupa y no de los anteriores. Para que la solución sea única es necesario conocer algunos términos de la sucesión, lo que llamaremos condiciones iniciales. En el ejemplo anterior a1 = 1 y a2 = 1 .

Ejemplo: Las sucesiones (1, 2, 4, 8, 16, ...) y (3, 6, 12, 24, 48, ...) satisfacen la misma relación de recurrencia an = 2an − 1 , si n ≥ 1 . Pero la condición inicial a0 = 1 junto con la relación de recurrencia determinan de forma única la primera de estas dos sucesiones. La condición inicial a0 = 3 junto con an = 2an − 1 para n ≥ 1 , determina la segunda.

Definición: Una ecuación de recurrencia lineal de orden k con coeficientes constantes es una relación cn an + cn − 1an − 1 + cn − 2 an − 2 + ... + cn − k an − k = bn , n ≥ k (I) donde cn , cn − 1 ,..., cn − k son constantes ( ≠ 0 ) y ( bn ) es una sucesión conocida. Diremos que (I) es homogénea si bn = 0 .

Matemática II- INET Profesora Patricia Echenique Viñas

-1-

Ecuación de recurrencia lineal homogénea Ecuación de recurrencia lineal de primer orden Sea ( an ) : an = 3an − 1 (esta expresión no define una única progresión geométrica, debemos dar las condiciones iniciales) Sea entonces ( an ) : an = 3an − 1 , con n ≥ 1 y a0 = 5 Esta ecuación de recurrencia an = 3an − 1 depende del elemento inmediato anterior, por eso decimos que es de primer orden. a0 = 5 a1 = 3a0 = 3 ⋅ 5 a2 = 3a1 = 3 ⋅ ( 3a0 ) = 3 ⋅ 3 ⋅ 5 = 32 ⋅ 5 a3 = 3a2 = 3 ⋅ ( 3 ⋅ ( 3a0 ) ) = 33 ⋅ 5 . . . an = 3n ⋅ 5 esta es la solución de la ec. de recurrencia Ejercicio 1: Encuentra la solución general de las siguientes ecuaciones de recurrencia a) bn = 6bn − 1 con n ≥ 1, b0 = 13 1 b) cn = cn − 1 con n ≥ 1, c0 = 7 5 En general: La solución de la ecuación de recurrencia

an = d ⋅ an − 1

con n ≥ 1, a0 = A

es

an = A ⋅ d n Ejemplo: Resolver an = 7 ⋅ an − 1 , n ≥ 1 y a2 = 98 an = 7 ⋅ a n − 1 ⇒ d = 7 an = A ⋅ d n a2 = A ⋅ 7n ⇒ 98 = A ⋅ 7 2 ⇒ A = 2 Por lo que la solución es:

an = 2 ⋅ 7 n

Matemática II- INET Profesora Patricia Echenique Viñas

-2-

Ejercicio 2: Encuentra la solución general de: n ≥ 0 a0 = 3 a) an + 1 = 1,5an n ≥ 0 a1 = 4 b) 3an + 1 − 4an = 0 2 2 Ejercicio 3: Determina an si an + 1 = 5an

an > 0, n ≥ 0 y a0 = 2

( Sugerencia: cambio de variable bn = a ) 2 n

Ejercicio 4: Un banco paga un interés (compuesto mensual) del 6% anual. Si se depositan U $ 1000 el 1º de abril, ¿cuánto dinero tendrá 3 meses después?

Ecuación de recurrencia lineal de segundo orden cn an + cn − 1an − 1 + cn − 2 an − 2 = 0

n ≥ 2 (homogénea)

Se busca una solución de la forma

a n = Ar n Sustituyendo en : cn an + cn − 1an − 1 + cn − 2 an − 2 = 0 cn Ar n + cn − 1 Ar n − 1 + cn − 2 Ar n − 2 = 0

n− 2 2 Factorizando se obtiene: r ( cn r + cn − 1r + cn − 2 ) = 0

⇔

(c r n

2

cn r 2 + cn − 1r + cn − 2 = 0 ( ya que r ≠ 0 )

+ cn − 1r + cn − 2 ) Se le llama POLINOMIO CARACTERÍSTICO

Según las raíces del polinomio característico las soluciones de las ecuaciones de recurrencia pueden ser de dos tipos: n n • 2 raíces distintas: r1 y r2 (reales o complejas), entonces la solución es an = α r1 + β r2 n n • Raíces repetidas, la solución es

an = α r + β ⋅ nr

Ejemplos: Resolver  an + an − 1 − 6an − 2 = 0 a)   a0 = 1, a1 = 2

n≥ 2

Matemática II- INET Profesora Patricia Echenique Viñas

-3-

El polinomio característico x 2 + x − 6 = 0 tiene dos raíces reales distintas que son 2 y –3, entonces la solución general es

an = α 2n + β ( − 3)

n

Para determinar α y β con las condiciones frontera a0 = 1, a1 = 2 obtenemos el sistema α + β = 1   2α − 3β = 2 cuya solución es α = 1 y β = 0 .Esto permite establecer que la solución única de la ecuación de n recurrencia dada es an = 2 .  an − 6an − 1 + 9an − 2 = 0, b)   a0 = 5, a1 = 12  an = 2an − 1 − 2an − 2 = 0, c)   a0 = 1, a1 = 1

n≥ 2

n≥ 2

d) Ahora puedes encontrar la solución general de la sucesión de Fibonacci an = a n − 1 + an − 2 , n ≥ 3 a1 = 1 y a2 = 1

Ecuación de recurrencia lineal no homogénea cn an + cn − 1an − 1 + cn − 2 an − 2 + ... + cn − k an − k = bn ,

n≥ k

con

( bn ) =

f (n) ≠ 0

............... (I)

Se le llama ecuación de recurrencia homogénea asociada a la anterior a la ecuación cn an + cn − 1an − 1 + cn − 2an − 2 + ... + cn − k an − k = 0, n ≥ k

Se aceptará sin demostración la siguiente propiedad: Cualquier solución an de la ecuación (I), se puede escribir de la forma a = p + h , donde pn es una solución particular de (I) y n

n

n

hn es la solución de la ecuación homogénea asociada.

Ya se vio en la parte anterior como hallar la solución de la ecuación de recurrencia homogénea. Para obtener una solución particular no hay un método general.

Matemática II- INET Profesora Patricia Echenique Viñas

-4-

Ejemplos de como hallar una solución particular en diferentes casos : 1º) an + 2an − 1 = 3 En este caso bn = 3 . Se puede “sospechar” que una solución particular de esta ecuación puede ser de la forma pn = A (siendo A una constante) Si sustituimos en la ecuación se obtiene : A + 2 A = 3 ⇒ 3 A = 3 ⇒ A = 1 . Por lo tanto pn = 1 es una solución particular. 2 2 2º) an + 2an − 1 = n − n − 1 En este caso bn = n − n − 1 . Se prueba si puede ser solución una 2 sucesión del mismo tipo, pn = An + Bn + C .

(

)

2 2 Para eso se sustituye en la ecuación An + Bn + C + 2 A ( n − 1) + B ( n − 1) + C = n − n − 1 .

Resolviendo un sistema se obtiene A = 1 3 , B = 1 9 , C = − 13 27 . 2 Por lo tanto pn = 1 3 n + 1 9 n − 13 27 es una solución particular.

2

n n 3º) an − 3an − 1 = 5 ( 7 ) . En este caso bn = 5 ( 7 ) , se prueba entonces con una sucesión de la forma

pn = A ( 7n ) . Sustituyendo en la ecuación se obtiene A ( 7n ) − 3 A ( 7n − 1 ) = 5 ( 7 n ) , de donde A = 35/4. n Por lo tanto pn = ( 35 4 ) 7 es una solución particular. En cada uno de los casos anteriores se ensayó una solución particular generalizando la expresión dada por bn . Se construyó una solución particular a partir de bn .

Los coeficientes (A, B, C, etc.) se determinan sustituyendo pn en la ecuación de recurrencia dada y resolviendo un sistema de ecuaciones. La técnica que se usó en los tres ejemplos de arriba es válida cuando bn , o algún término de bn no sea solución de la ecuación homogénea asociada. 4º) an − an − 1 = 2 . Si se prueba con una solución de la forma pn = A , al sustituir se obtiene una contradicción ya que A − A = 2 ⇒ 0 = 2 . Esto significa que no hay ninguna solución particular de esta forma (polinómica de grado 0) En estos casos se probará con soluciones polinómicas de grado superior al que tiene la sucesión bn . En este caso si se toma una solución particular del tipo pn = An , sustituyendo se obtiene A =2 . Por lo tanto una solución particular es pn = 2n n n n 5º) an − 3an − 1 = 5 ( 3 ) , n ≥ 1 y a0 = 2 . Se prueba con pn = A ( 3 ) . Al sustituir an por A ( 3 ) se llega otra vez a una contradicción (0 =5) . No existe entonces ninguna solución particular de la n n n forma pn = A ( 3 ) . Se ensaya con una de la forma pn = An ( 3 ) y se obtiene que pn = 5n ( 3 ) es

una solución particular. n Recordar que en este caso la solución de la homogénea asociada es hn = α ⋅ 3 ( α se determina aplicando las condiciones iniciales, en este caso al ser a0 = 2 se obtiene α = 2 ). n n n Entonces la solución general será de la forma an = 2 ⋅ 3 + 5n3 o an = ( 2 + 5n ) ( 3 )

Matemática II- INET Profesora Patricia Echenique Viñas

-5-

En resumen: 1) Si bn es un múltiplo constante de una de las formas de la primera columna de la tabla siguiente y no es solución de la ecuación homogénea asociada, entonces la solución particular pn tiene la forma que se muestra en la segunda columna. bn

pn

K n n2 rn n2rn

A An + B An 2 + Bn + C Ar n r n ( An 2 + Bn + C )

sin ( α n )

A sin ( α n ) + B cos ( α n )

cos ( α n )

A sin ( α n ) + B cos ( α n )

2) Cuando bn es una suma de múltiplos constantes de términos como los de la primer columna (y ninguno de estos es solución de la ecuación homogénea asociada), entonces la solución particular se forma como la suma de los términos correspondientes en la segunda columna. 3) Si bn (o algún término de bn ) es un múltiplo constante de una solución de la ecuación homogénea asociada, multiplicamos la solución particular correspondiente a ese sumando por la mínima potencia de n, n t para la que ningún sumando de la nueva expresión sea una solución de la ecuación homogénea asociada (Si pn se “solapa” con hn , multiplicamos pn por la menor potencia de n que evite dicho “solapamiento”).

Matemática II- INET Profesora Patricia Echenique Viñas

-6-

EJERCICIOS

1. Encuentre una relación de recurrencia, con una condición inicial, que determine de manera única cada una de las siguientes progresiones geométricas:

2.

i. 2, 10, 250, …

50,

iii. 1, …

1 3

,

1 9

ii. 6, -18, -162, …

54,

iv. 7, ,…

14 5

,

28 25

, ,

1 27

,

56 125

Resuelva las siguientes progresiones geométricas. i.

4an − 5an − 1 = 0 , n ≥ 1 , a 2 =

25 4

ii. 2an − 3an − 1 = 0 , n ≥ 1 , a 4 = 81 3. Si an , con n ≥ 1 , es una solución de la relación de a 5 = 1377 recurrencia an − dan − 1 = 0 , y a 3 = 153 ¿cuánto vale 49 , 2401 , d?. 4. El número de bacterias en un cultivo es de 800 (aproximadamente) y este número aumenta un 150% cada hora. Use una relación de recurrencia para determinar el número de bacterias presentes 3 horas después. 5. Un banco paga un interés (anual) del 6% para cuentas de ahorros, con un interés compuesto mensual. Utilice una ecuación de recurrencia para determinar cuánto dinero se tendrá depositado un año después si se realiza un depósito de $1000. 6. Resuelve las siguientes ecuaciones de recurrencia.  an = − 3an − 1 a)   a0 = 2

 a n = − 54 a n − 1 b)   a 2 = 25

7. Si a 2 = 2 y a 4 = 32 , satisfacen la ecuación de recurrencia an − ban − 1 = 0 , donde n ≥ 1 y b es constante, encuentre an . 8. Resuelve las siguientes ecuaciones de recurrencia. a) an = 6an − 1 − 8an − 2 , n ≥ 2, a0 = 1, a1 = 0 b) an = an − 1 + n, n ≥ 1, a0 = 0 Matemática II- INET Profesora Patricia Echenique Viñas

-7-

c) 2an = 7an − 1 − 3an − 2 , n ≥ 2, a0 = 1, a1 = 1 d) an = 5an − 1 + 6an − 2 , n ≥ 2, a0 = 1, a1 = 3 e) 2an + 2 − 11an + 1 + 5an = 0, n ≥ 0, a0 = 2, a1 = − 8 f) an = 2an − 1 + 5, n ≥ 1, a0 = 1 g) 3an + 1 = 2an + an − 1 = 0, n ≥ 1, a0 = 7, a1 = 3 h) an − 6an − 1 + 9an − 2 = 0, n ≥ 2, a0 = 5, a1 = 12 i)

an + 2an − 1 + 2an − 2 = 0, n ≥ 2, a0 = 1, a1 = 3

j)

 an = a n − 1 + 2 n , n ≥ 1   a0 = 1

k) an + 2 + 4an = 0, n ≥ 0, a0 = a1 = 1 l)

 an − an − 1 = 2n + 3, n ≥ 1   a0 = 1

 an − an − 1 = 3n 2 − n, n ≥ 1 m)   a0 = 3 9. Resuelve las siguientes ecuaciones de recurrencia. i.

 an + 3an − 1 + 2an − 2 = 3n , n ≥ 2   a0 = 0 a = 1  1

 an = 5an − 1 + 6an − 2 + 6n , n ≥ 2  ii.  a0 = 0 a = 1  1  an + 4an − 1 + 4an − 2 = 7, n ≥ 2  iii.  a0 = 1 a = 2  1 Bibliografía:  GRIMALDI, Ralph P. “Matemáticas discreta y combinatoria”. Tercera edición. Editorial Addison-Wesley Iberoamericana  ROSEN, Kenneth H. “Matemática discreta y sus aplicaciones”. Quinta edición. Editorial Mc Graw Hill

Matemática II- INET Profesora Patricia Echenique Viñas

-8-