Agueda Mata y Miguel Reyes, Dpto. de Matemtica Aplicada, FI-UPM.

5. RECURRENCIAS LINEALES 5.1. Recurrencias lineales homogneas e

Deniciones Una relacin o frmula de recurrencia de orden k 1 para una sucesin {a0 , a1 , a2 , . . . , an , . . .} es una o o o expresin que relaciona cada trmino con sus k trminos anteriores: o e e an = f (an1 , an2 , . . . , ank ) , para todo n k

Para poder hallar la sucesin a partir de la frmula de recurrencia es necesario conocer los k primeros trminos, o o e que se llaman condiciones iniciales. La frmula de recurrencia junto con las condiciones iniciales se llama o sucesin recurrente o de recurrencia. o Una relacin recurrencia de orden k se llama lineal cuando la frmula de recurrencia es lineal: o o an = c1 an1 + c2 an2 + . . . + ck ank + g(n) , para todo n k

Si g(n) 0, la relacin de recurrencia lineal se llama homognea. o e Resolver una sucesin de recurrencia consiste en obtener, a partir de la frmula de recurrencia y las condiciones o o iniciales, una frmula an = F (n), n 0, que proporcione los trminos de la sucesin en funcin del lugar que o e o o ocupan. Recurrencias lineales de primer orden La solucin de las sucesiones recurrentes lineales de primer orden se obtienen fcilmente por induccin: o a o n an = can1 + g(n) , n 1 = an = cn b0 + g(i)cni a0 = b0 i=1 Recurrencias lineales de segundo orden homogneas e an = c1 an1 + c2 an2 , n 2 Una sucesin recurrente lineal de segundo orden homognea es: () o e a0 = b0 , a1 = b1 2 = c x + c , y sus soluciones se llaman Se llama ecuacin caracter o stica de la recurrencia a la ecuacin x o 1 2 ra ces caracter sticas. Propiedades de la ecuacin y ra o ces caracter sticas 1. x = es ra caracter z stica si y slo si an = n es solucin de la frmula de recurrencia. o o o 2. Si x = es una ra caracter z stica doble, entonces nn es solucin de la frmula de recurrencia. o o 3. Si xn e yn son soluciones de la frmula de recurrencia, tambin lo son xn + yn y kxn , para todo k. o e Soluciones de las sucesiones recurrentes lineales de segundo orden Si = son dos ra ces caracter sticas, entonces la solucin a la sucesin recurrente () es: o o k1 + k2 = b0 an = k1 n + k2 n , donde k1 y k2 son las soluciones del sistema: k1 + k2 = b1 Si es una ra caracter z stica doble, entonces la solucin a la sucesin recurrente () es: o o k1 = b0 an = (k1 + k2 n)n , donde k1 y k2 son las soluciones del sistema: (k1 + k2 ) = b1

 Agueda Mata y Miguel Reyes, Dpto. de Matemtica Aplicada, FI-UPM. a Ejercicios 1. Encuentra el trmino general de las siguientes e an = 4an1 4an2 , n 2 (a) a0 = 6 , a1 = 8 an = 7an1 10an2 , n 2 (b) a0 = 2 , a1 = 1 an = 2an1 an2 , n 2 (c) a0 = 4 , a1 = 1 sucesiones recurrentes: an+2 = 4an+1 + 5an , n 0 (d) a0 = 2 , a1 = 8 an = 5an1 6an2 , n 2 (e) a0 = 1 , a1 = 0 an = 6an1 11an2 + 6an3 , n 3 (f ) a0 = 2 , a1 = 5 , a2 = 15

2. Una mquina expendedora slo acepta monedas de 1 dlar y 5 dlares. De cuntas formas se pueden a o o o a depositar n dlares. o 3. Cuntas cadenas con n s a mbolos 0s y 1s no contienen tres ceros consecutivos? 4. Cuntas cadenas con n s a mbolos 0s, 1s y 2s no contienen dos ceros consecutivos? 5. Cuntas cadenas con n s a mbolos 0s, 1s y 2s no contienen dos s mbolos iguales consecutivos? 6. Si en cada paso se pueden subir 1 o 2 peldaos, de cuntas formas se puede subir una escalera con n n a peldaos? n 7. Se trazan n rectas en el plano con la condicin de que cada una de ellas corte a todas las restantes y que o no haya tres coincidentes. Para cada n 0, sea an el nmero de regiones en que las n rectas dividen al u plano, y sea bn el nmero de esas regiones no acotadas. Encuentra expresiones para an y bn en funcin u o de n. 8. (Problema de las torres de Hanoi) Se dispone de 3 estacas y n discos, todos ellos de diferente tamao y n apilados en la estaca 1 ordenados de mayor a menor. El objetivo es cambiar todos los discos a otra estaca en la misma posicin y de tal manera que en cada movimiento slo se mueve un disco y nunca se puede o o colocar un disco sobre otro ms pequeo. Si an es el menor nmero de movimientos que se requieren para a n u hacerlo, encuentra su expresin en funcin de n. o o 9. Halla el nmero de sucesiones de longitud n que se pueden formar con as, bs y cs de tal manera que u todas las cadenas de as consecutivas tienen longitud par. 10. Se dispone de una cantidad ilimitada de cubos de lados 1, 2 y 4 para construir una torre de base 4 4 en la que cada capa est formada por cubos del mismo tamao. De cuntas formas distintas se puede a n a construir una torre de altura n. 2 1 0 0 0 1 2 1 0 0 0 1 2 1 0 11. Halla el determinante de la matriz: An = . 0 0 1 2 . , n 1. . . . . . .. . . . . . 1 . . . . 0 0 0 1 2 Soluciones y/o sugerencia a los ejercicios 1. (a) an = 2(3 n)2n ; (b) an = 3 2n 5n ; (c) an = 4 3n; (d) an = 3 (5)n ; (e) an = 3 2n 2 3n ; (f ) an = 1 2n + 2 3n . 2. n + 1. 5 an = 2an1 an4 , n 5 3. a1 = 2 , a2 = 4 , a3 = 7 , a4 = 13

 Agueda Mata y Miguel Reyes, Dpto. de Matemtica Aplicada, FI-UPM. a an = 3an1 2an3 , n 4 4. a1 = 3 , a2 = 9 , a3 = 23 5. an = 3 2n1 , n 1. an = an1 + an2 , n 3 6. a = 1 , a2 = 2 1 an = n + an1 , n 2 7. y bn = 2n. a1 = 2 8. = 2n 1, n 1. an an = 2an1 + an2 , n 3 9. a = 2 , a2 = 5 1 an = an1 + an2 + an4 , n 5 10. a1 = 1 , a2 = 2 , a3 = 3 , a4 = 6 11. an = 1 + n.

 Agueda Mata y Miguel Reyes, Dpto. de Matemtica Aplicada, FI-UPM. a

5. RECURRENCIAS LINEALES 5.2. Sucesin de Fibonacci o

Sucesin de Fibonacci o an = an1 + an2 , n 2 Es una de las ms importantes sucesiones recurrentes: a . Sus primeros trminos e a0 = a1 = 1 son: 1, 1, 2, 3, 5, 8, 13, 21, . . .. La ecuacin caracter o stica, ra ces caracter sticas y soluciones de la frmula de recurrencia son: o n n 1 5 1+ 5 1 5 2 x = x + 1 = x = = an = k1 + k2 2 2 2 Con las condiciones iniciales se hallan las constantes y se resuelve la sucesin recurrente: o k1 = 1+ 55 k1 + k2 = 1 a0 = k1 + k2 = 1 2 = = = 1 k1 k2 = 5 a1 = 1+2 5 k1 + 12 5 k2 = 1 k2 = 1 55 2 n+1 n+1 1 1+ 5 1 1 5 = an = 2 2 5 5 Propiedades La sucesin de Fibonacci {F1 , F2 , F3 , . . .}, denida por: o n n Fn = Fn1 + Fn2 , n 3 1 1+ 5 1 1 5 o Fn = 2 2 F1 = F2 = 1 5 5 verica: 1. F1 + F2 + F3 + . . . + Fn = Fn+2 1 2. F1 + F3 + F5 + . . . + F2n1 = F2n 3. F2 + F4 + F6 + . . . + F2n = F2n+1 1
2 2 2 2 4. F1 + F2 + F3 + . . . + Fn = Fn Fn+1 2 5. Fn+1 = Fn Fn+2 + (1)n 2 2 6. Fn+1 Fn1 = F2n

7. Fk es un divisor de Fkm . 8. Si mcd(n, m) = d, entonces mcd(Fn , Fm ) = Fd . 9. El cociente entre cada trmino y su anterior converge a la razn urea: e o a Fn+1 1+ 5 lim == = 1, 61803 . . . n Fn 2 que es la ra positiva de la ecuacin x2 x 1 = 0. z o Ejercicios 1. Demuestra cada una de las propiedades de la sucesin de Fibonacci. o

 Agueda Mata y Miguel Reyes, Dpto. de Matemtica Aplicada, FI-UPM. a

5. RECURRENCIAS LINEALES 5.3. Recurrencias lineales no homogneas e

Denicin o Una relacin de recurrencia lineal no homognea de orden k 1 es una relacin de la forma o e o an = c1 an1 + c2 an2 + . . . + ck ank + g(n) , an = c1 an1 + c2 an2 + . . . + ck ank , donde g(n) 0, y se llama relacin de recurrencia lineal homognea asociada a la relacin: o e o Cuando se trabaja con la relacin de recurrencia lineal homognea asociada, la relacin no homognea de la o e o e que procede se suele llamar relacin completa. o Propiedades 1. Si Xn ) e Yn son soluciones de la relacin completa, entonces Xn Yn es solucin de la relacin homognea o o o e asociada. 2. Si xn es solucin de la relacin homognea asociada y Xn es solucin de la relacin completa, entonces o o e o o xn + Xn es solucin de la relacin completa. o o 3. Todas las soluciones de la relacin completa son de la forma xn + Xn donde xn son todas las soluciones o de la relacin homognea asociada y Xn es una solucin particular de la relacin completa. o e o o Resolucin de las sucesiones recurrentes lineales completas de segundo orden o Para resolver la sucesin recurrente lineal completa de segundo orden () se considera la relacin homognea o o e asociada (). an = c1 an1 + c2 an2 + g(n) , n 2 () () an = c1 an1 + c2 an2 a0 = b0 , a1 = b1 Se hallan todas las soluciones de la relacin homognea (): xn (k1 , k2 ). o e Se busca una solucin particular Xn de la relacin completa teniendo en cuenta su forma en los siguientes o o casos particulares: Si Si Si Si g(n) es un polinomio de grado p, Xn es un polinomio de grado mayor o igual que p. g(n) = cbn y b no es ra caracter z stica, entonces Xn = kbn . g(n) = cbn con b ra caracter z stica simple, entonces Xn = knbn . g(n) = cbn con b ra caracter z stica doble, entonces Xn = kn2 bn . para todo n k para todo n k

Todas las soluciones de la relacin completa son de la forma an = xn (k1 , k2 ) + Xn . o Para hallar la solucin a la sucesin () se determinan las constantes k1 y k2 para que an general verique o o las condiciones iniciales. Ejercicios 1. Encuentra el trmino general de las siguientes sucesiones recurrentes no homogneas: e e an = an1 + 6an2 + 2n , n 2 an = 3an1 + 5 7n , n 1 (a) (d) a0 = 0 , a1 = 1 a0 = 2 an = 4an1 4an2 + n , n 2 an = 3an1 + 5 3n , n 1 (b) (e) a0 = 1 , a1 = 3 a0 = 2 an = an1 + 3n2 , n 1 an = 3an1 4an3 + n2 , n 3 (c) (f ) a0 = 7 a0 = 11 , a1 = 1 , a2 = 1

 Agueda Mata y Miguel Reyes, Dpto. de Matemtica Aplicada, FI-UPM. a Soluciones y/o sugerencia a los ejercicios 1. (a) an = 3n 2n ; (b) an = (2n 3)2n + n + 4; (c) an = n2 3n + 7; (d) an = 2 2 (f ) an = 3(1)n 5n+8 2n + n + 9n + 12. 2 2 2
357n 273n ; 4

(e) an = (5n + 2)3n ;

 Agueda Mata y Miguel Reyes, Dpto. de Matemtica Aplicada, FI-UPM. a

5. RECURRENCIAS LINEALES 5.4. Recurrencias no lineales. N meros de Catalan u

Se dice que una relacin o frmula de recurrencia de orden k 1 es no lineal cuando no es lineal la expresin o o o que relaciona cada trmino con sus k trminos anteriores: e e an = f (an1 , an2 , . . . , ank ) , para todo n k

Para la resolucin de recurrencias no lineales existen mtodos particulares que se aplican en cada caso. Una o e recurrencia no lineal muy importante es la que dene los nmeros de Catalan. u N meros de Catalan u Se llaman n meros de Catalan a los trminos de la sucesin recurrente: u e o an = a0 an1 + a1 an2 + a2 an3 + . . . + an1 a0 a0 = 1 cuya solucin es an = o
2n 1 n+1 n

Los nmeros de Catalan aparecen en multitud de problemas algor u tmicos como, por ejemplo, los siguientes: Nmero de caminos montonos que van en una malla desde (0, 0) hasta (n, n) sin sobrepasar la diagonal. u o Formas de colocar parntesis en un producto de n + 1 factores. e Triangulaciones de un pol gono convexo de n + 2 vrtices. e Sucesiones de longitud 2n con n signos + y n signos que comienzan con +. Arboles planos binarios con n + 1 hojas.

, n 0. Los primeros nmeros son: 1, 1, 2, 5, 14, 42, 139, 429, . . .. u