Versión preliminar Algunos ejemplos. 382 Capítulo 6. Ecuaciones de recurrencia

382

Cap´ıtulo 6. Ecuaciones de recurrencia

6.1.

Algunos ejemplos

pr eli m in ar

Para convencernos de que las ecuaciones de recurrencia aparecen en muy diferentes contextos (y que muchas veces son la mejor respuesta a la que podemos llegar con las herramientas de que disponemos), veamos algunos ejemplos. Algunos de ellos hasta conseguiremos resolverlos con trucos ad hoc, mientras que la resoluci´on de otros habr´ a de esperar a disponer de t´ecnicas m´as generales. 1. En funci´ on del caso anterior

Las ecuaciones de recurrencia m´as sencillas son aqu´ellas en las que el valor de un cierto t´ermino de la sucesi´on depende u ´nicamente del valor del t´ermino anterior. Ejemplo 6.1.1 Queremos contar el n´ umero de listas de longitud n ≥ 1 formadas con ceros y unos. Llamemos an a la respuesta, para cada n.

Ve rs i´on

No parece ´este un ejemplo muy apasionante, dado que la regla del producto nos permite obtener directamente la respuesta: an = 2n , para cada n ≥ 1. Pero abordemos el problema desde otro punto de vista, planteando una relaci´ on de recurrencia entre los n´ umeros an . Para construir una lista de longitud n con ceros y unos construimos, primero, una lista de longitud n − 1 con las caracter´ısticas pedidas (lo podrenadimos un 0 o un 1 mos hacer de an−1 formas distintas). Y luego, a cada una de ellas, le a˜ (as´ı obtenemos todas las posibles listas de longitud n). Como a cada posible lista de longitud n − 1 le podemos asociar dos listas distintas de longitud n, el resultado total ser´ a que an = 2 an−1

Necesitamos, adem´as, un valor inicial, el n´ umero de listas de longitud 1 que hay: evidentemente, a1 = 2. Ya tenemos el problema solucionado en un cierto sentido: el conocimiento de a1 nos permite calcular a2 ; con a2 , evaluamos a3 , etc. En este caso, adem´as, podemos resolver la recurrencia y obtener una f´ormula expl´ıcita para los an : basta aplicar reiteradamente la regla para obtener que ♣

an = 2 an−1 = 2 (2an−2 ) = 22 an−2 = 23 an−3 = · · · = 2n−1 a1 = 2n .

umero de regiones en que n rectas dividen al plano. Deben Ejemplo 6.1.2 Llamemos an al n´ ser rectas tales que por cualquier punto del plano pasen a lo sumo dos de ellas; y tales que ninguna de ellas sea paralela a otra. Calculemos los primeros casos: para n = 1, tenemos una recta, que divide al plano en, obviamente, dos regiones. Para n = 2, n = 3 y n = 4 aparecen cuatro, siete y once regiones, respectivamente: n=3 n=4 n=2 VIII V

I III

IV II

I VI III

VII IV

II

IX V III

X

I VI II

XI

(versi´ on preliminar 23 de diciembre de 2003)

VII IV

6.1. Algunos ejemplos

383

Ya tenemos los primeros cuatro valores a1 = 2, a2 = 4, a3 = 7 y a4 = 11, pero el dibujo se va complicando, y corremos el riesgo de equivocarnos y olvidarnos de alguna regi´on. Toca pensar: ﬁj´emonos en c´omo pasamos de n = 2 1 a n = 3. Lo que hacemos es a˜ nadir una recta y como 2 las dos rectas “viejas” deben cortar a la “nueva”, lo que hacemos es a˜ nadir tres regiones del plano: ¿C´ omo pasamos 3 de n = 3 a n = 4? V´ e ase el dibujo: de nuevo a˜ nadimos 4 una recta, que corta a las tres existentes y crea cuatro regiones nuevas. Este argumento nos permite deducir que la regla de recurrencia es, para cada n ≥ 2, an = an−1 + n 2

3

pr eli m in ar

1

Como conocemos el valor del primero, a1 = 2, podremos calcularlos todos.

La ecuaci´on se puede resolver aplicando reiteradamente la regla de recursi´on. Pero es mejor entenderla de la siguiente manera: la recurrencia nos dice que la diferencia entre dos t´erminos consecutivos es justamente el valor del ´ındice, an − an−1 = n. Escribamos entonces todas estas relaciones y sum´emoslas:

Ve rs i´on

an − an−1 = an−1 − an−2 = .. .. . . = a2 − a 1 an − a 1

n n−1 .. . 2

= 2 + 3 + · · · + (n − 1) + n

Y, como sabemos sumar los n primeros n´ umeros naturales, llegamos a la soluci´on ﬁnal: an = 2 +

n

j =1+

j=2

n

j =1+

j=1

n(n + 1) . 2

♣

Ejemplo 6.1.3 Las torres de Hanoi.

Cuenta la leyenda1 que unos monjes de un monasterio de Hanoi miden el tiempo que falta para la llegada del ﬁn del mundo con el siguiente procedimiento: disponen de tres agujas de diamante, en una de las cuales se apilan 64 discos de oro distintos, ordenados seg´ un su tama˜ no. 1

2

3

1 En realidad, es un pasatiempo creado por el matem´ atico franc´es Lucas en 1883. Pero adornar estos problemas nunca est´ a de m´ as.

(versi´ on preliminar 23 de diciembre de 2003)

384

Cap´ıtulo 6. Ecuaciones de recurrencia

pr eli m in ar

Cada segundo mueven un disco de una aguja a otra, y su tarea ﬁnalizar´ a (y con ella el mundo) cuando logren transportarlos todos a otra aguja. Pero, ¡atenci´ on!, nunca se puede colocar un disco sobre otro de di´ametro m´as peque˜ no. ﬁn del mundo, o bien ponernos en plan matem´ atico y determinar cu´anto tiempo puede llevar a los monjes terminar su tarea. Y, como buenos matem´aticos, planteamos el problema en general: tenemos n discos y umero de movimientos necesario para transportar los n discos llamamos an al m´ınimo n´ desde una aguja a otra. Por ejemplo, a1 = 1, porque nos basta con un movimiento para pasar no argumento: una posible el disco a otra aguja. Para calcular a2 ya necesitamos un peque˜ estrategia es la de pasar el disco peque˜ no a otra aguja, luego el grande a la tercera, para ﬁnalmente pasar el peque˜ no a esta tercera aguja: -

-

-

Como en dos movimientos no se puede hacer, concluimos que la de antes es la mejor estrategia posible, y que, por tanto, a2 = 3. El lector podr´a comprobar que, si partimos de tres discos, una posible estrategia consiste en pasar los dos menores a una segunda aguja (con el procedimiento anterior, de tres movimientos), luego pasar el disco mayor a la tercera aguja, para ﬁnalmente llevar los dos discos menores sobre ese disco mayor (de nuevo necesitaremos tres movimientos). En total, siete movimientos. Pero ahora no est´ a claro si se puede hacer con menos.

Ve rs i´on

El procedimiento que sugerimos se puede generalizar: si tenemos n discos, pasamos n − 1 a una segunda aguja, luego el mayor disco a la aguja ﬁnal y, por u ´ltimo, pasamos los n − 1 discos a esa tercera aguja. Fij´emonos en que es un algoritmo recursivo: el procedimiento para mover n discos se apoya, dos veces, en el (ya conocido) m´etodo para mover n − 1. De esta digresi´on deducimos que el n´ umero m´ınimo de movimientos para transportar los n discos cumple la siguiente condici´on: an ≤ 2 an−1 + 1 ,

para cada n ≥ 2.

porque con 2an−1 + 1 movimientos lo sabemos hacer. No es una regla de recurrencia como las habituales: no tenemos una ecuaci´on, sino una desigualdad. A´ un as´ı, se podr´ıa obtener cierta informaci´on con ella sobre el comportamiento de los an (v´ease el ejercicio 6.1.1). Pero lo que nos gustar´ıa es comprobar que, en realidad, la relaci´on se cumple con un = en lugar de un ≤: deducir´ıamos as´ı que nuestra estrategia de movimientos es la mejor posible.

Esto requiere un argumento extra. Ve´ amoslo: si tenemos n discos, en alg´ un momento tendremos que mover el disco mayor. Y para poder hacerlo, tendr´ıamos que haber llevado el resto de los discos a otra aguja; esto requiere, como m´ınimo, an−1 movimientos. Supongamos que ya hemos movido el disco grande a una aguja; ahora tendremos que mover los restantes n − 1 discos sobre ´el, y esto exige, al menos, an−1 movimientos (sea cual sea la estrategia que empleemos). As´ı que an ≥ 2 an−1 + 1 , (versi´ on preliminar 23 de diciembre de 2003)

6.1. Algunos ejemplos

385

para n ≥ 2. Reuniendo ambas condiciones, ya podemos aﬁrmar que, para cada n ≥ 2, an = 2 an−1 + 1

pr eli m in ar

La condici´on inicial ya la hemos visto, es a1 = 1. La resolvemos, de nuevo, por simple iteraci´on:

an = 2 an−1 + 1 = 2 (2 an−2 + 1) + 1 = 22 an−2 + 2 + 1 = 22 (2 an−3 + 1) + 2 + 1

= 23 an−3 + 22 + 2 + 1 = 23 (2 an−4 + 1) 22 + 2 + 1 = 24 an−4 + 23 + 22 + 2 + 1 n−1 1 − 2n n−1 n−2 n−3 = ··· = 2 = 2n − 1 . a1 + 2 +2 + ··· + 2 + 1 = 2j = 1−2 j=0

Ya conocemos la soluci´on en general, que aplicamos al caso n = 64: el ﬁn del mundo llenos! Parece que la gar´a dentro de a64 = 264 − 1 segundos, esto es. . . ¡m´as de medio bill´on de a˜ profec´ıa de los monjes de Hanoi no debe preocuparnos mucho. ♣ Ejemplo 6.1.4 Calcular el valor de la siguiente aparentemente complicada integral2 ∞ Γ(n + 1) = tn e−t dt , para cada n ≥ 0. 0 ∞ ∞ El caso n = 0 es sencillo de calcular, Γ(1) = 0 e−t dt = −e−t 0 = 1 . Vamos a llegar ahora a una ecuaci´on de recurrencia para los n´ umeros Γ(n), pero no a trav´es de argumentos combinatorios, como hasta ahora, sino por medio de manipulaciones algebraicas. En este caso, integrando por partes. Estamos con n ≥ 1 y escogemos

Ve rs i´on

u = tn =⇒ du = n tn−1 dt

dv = e−t dt =⇒ v = −e−t

para la aplicaci´on de la habitual f´ ormula de integraci´on por partes: ∞ ∞ ∞ Γ(n + 1) = tn e−t dt = −tn e−t +n tn−1 e−t dt = n Γ(n) . 0 0 0 =0

Γ(n)

La ecuaci´on de recurrencia resulta ser

Γ(n + 1) = n Γ(n)

para n ≥ 1. Obs´ervese que ahora el coeﬁciente que acompa˜ na al t´ermino anterior no es una constante. Pero la resoluci´on es, de nuevo, sencilla, por iteraci´on: Γ(n + 1) = n Γ(n) = n(n − 1) Γ(n − 1) = · · · = n(n − 1) . . . 3 · 2 Γ(1) .

Como el valor inicial era Γ(1) = 1, concluimos que, sorprendentemente, ∞ Γ(n + 1) = tn e−t dt = n! . 0 2

♣

Esta integral es un caso particular de la llamada funci´ on gamma, la funci´ on de la variable compleja z deﬁnida mediante ∞ tz e−t dt para cada z con Re(z) > −1. Γ(z + 1) = 0

(versi´ on preliminar 23 de diciembre de 2003)

386

Cap´ıtulo 6. Ecuaciones de recurrencia

2. En funci´ on de los dos casos anteriores

pr eli m in ar

En muchas ocasiones, para determinar el valor de un t´ermino de la sucesi´on, bastar´a mirar el valor de los dos anteriores. Ser´an normalmente ejemplos en los que nos encontraremos con una disyuntiva: una opci´ on nos llevar´a al caso anterior, mientras que la otra se escribir´a en t´erminos del que est´ a dos posiciones m´as all´a. umero de listas de longitud n, formadas con ceros y unos, Ejemplo 6.1.5 Llamemos an al n´ que no tienen unos consecutivos. Nos ﬁjamos, por ejemplo, en la u ´ltima posici´on. Caben dos posibilidades, que la lista acabe en 0 ´o en 1. Las que acaban en 0 se construyen dando una de longitud n − 1 que cumpla las condiciones (ceros y unos, sin unos consecutivos) y a˜ nadi´endole un 0 al ﬁnal (compr´ uebese que es una biyecci´on). Las acabadas en 1 llevan, necesariamente, un 0 en la pen´ ultima posici´on; as´ı que habr´ a tantas como listas de longitud n − 2 que cumplan las condiciones:  ←→ an−1  0       an −→

una de longitud n − 1

      

0 1

una de n − 2

¡obligado!

←→ an−2

Ve rs i´on

Por tanto, la regla de recurrencia ser´a, para cada n ≥ 3, an = an−1 + an−2

´ Esta es una ecuaci´on muy especial, la ecuaci´ on de Fibonacci, que volver´a a aparecer en los siguientes ejemplos. Observemos que los valores iniciales, que permiten arrancar a la sucesi´on, son a1 = 2 y a2 = 3. ♣

Ejemplo 6.1.6 Tenemos una escalera con n pelda˜ nos y en cada paso se suben 1 o ´ 2 pelda˜ nos. umero de formas distintas de subir la escalera con ese tipo de pasos (dos Llamaremos an al n´ formas de subir ser´ an distintas si la secuencia de pasos seguida es distinta). Para contarlas, las clasiﬁcaremos (haremos una partici´on) atendiendo a c´ omo se llega al u ´ltimo pelda˜ no. S´ olo tenemos dos posibilidades: llegar al pelda˜ no n − 1 y luego dar un paso de un pelda˜ no, o llegar al n − 2 y luego un paso de dos pelda˜ nos.

Por tanto, la relaci´on de recurrencia ser´a, de nuevo, an = an−1 + an−2 para cada n ≥ 3. Pero ahora los valores iniciales no son los del ejemplo anterior, sino que a1 = 1 y a2 = 2. Como las condiciones iniciales son distintas, las sucesiones de n´ umeros no coincidir´an: a1 a2 a3 a4 a5 a6 · · · # listas del Ejemplo 6.1.5 −→ 2 3 5 8 13 21 · · · # caminos escalera −→ 1 2 3 5 8 13 · · · (versi´ on preliminar 23 de diciembre de 2003)

6.1. Algunos ejemplos

387

pr eli m in ar

Pero tienen un aire similar, claro; en este caso, una est´ a desplazada una posici´on de la otra. Veremos en un momento que su comportamiento asint´ otico (es decir, c´omo son los an cuando n es grande) no depende de los valores iniciales, sino que es el que dicta la ecuaci´ on. ♣ Ejemplo 6.1.7 Un modelo de cunicultura. Ya hemos mentado en un par de ocasiones la ecuaci´ on de Fibonacci. Fibonacci3 introdujo la sucesi´on que lleva su nombre4 como modelo ´ part´ıa de ciertas hip´ para la reproducci´on de conejos. El otesis, a saber, que (a) los conejos viven eternamente; (b) que cada mes, un par de adultos de distinto sexo da lugar a un nuevo par de conejos de distinto sexo; y (c) que cada conejo se hace adulto a los dos meses de vida, momento en el que comienza a tener descendencia. Designemos por Fn el n´ umero de pares de conejos al ﬁnal del mes n. Supongamos que partimos de un par de conejos que nacen en el primer mes; codiﬁcaremos esta informaci´on en el valor F1 = 1. Al cabo de un mes, seguiremos teniendo una pareja de conejos, todav´ıa no adultos: F2 = 1. En el tercer mes, ya tenemos una pareja de adultos, que da lugar a una pareja de reci´en Figura 6.1: Fibonacci nacidos: F3 = 2. En el cuarto mes, seguiremos teniendo una pareja de adultos, que tendr´ an descendencia. Y la pareja nacida en el mes anterior tendr´a ahora un mes. En total, habr´ a tres parejas de conejos: F4 = 3. Y as´ı, sucesivamente. La siguiente tabla recoge las distintas poblaciones al comienzo de cada mes: 1

2

3

4

5

6

7

···

Parejas de adultos

0

0

1

1

2

3

5

···

Parejas con un mes de edad

0

1

0

1

1

2

3

···

Parejas de reci´en nacidos

1

0

1

1

2

3

5

···

N´ umero total de parejas, Fk

1

1

2

3

5

8

13

···

Ve rs i´on

Mes

El n´ umero de parejas en el mes n es igual a la suma del n´ umero de parejas en el mes n−1 m´as las parejas que nacen en el propio mes n. Pero esta u ´ltima cantidad coincide con el n´ umero de parejas adultas en el mes n, que, a su vez, es igual al n´ umero total de parejas en el mes n − 2 (pues se tardan dos meses en ser adulto). En total, Fn = Fn−1 + Fn−2

3 Algunos datos biogr´ aﬁcos sobre Leonardo de Pisa (1170-1250), tambi´en llamado Fibonacci (hijo de los Bonacci) no est´ an nada claros, incluyendo las fechas de nacimiento y muerte. La ilustraci´on que aqu´ı reproducimos es la cabeza de la estatua que erigieron los ciudadanos de Pisa en su honor cerca del r´ıo Arno. Viaj´ o por todo el Mediterr´ aneo y en el curso de sus viajes tom´ o contacto con las Matem´ aticas que los ´ arabes hab´ıan recopilado. Su Liber Abaci de 1202 tuvo una enorme inﬂuencia en su tiempo. En ´el recog´ıa numerosos resultados sobre Geometr´ıa y Teor´ıa de N´ umeros, adem´ as de cuestiones pr´ acticas sobre problemas mercantiles, m´etodos de multiplicaci´ on, etc. El texto estableci´ o deﬁnitivamente en Occidente los numerales ar´ abigos y el sistema hind´ u de numeraci´ on. 4 Fue el matem´ atico franc´es Edouard Lucas (1842-1891) el que as´ı la bautiz´ o. En el ejemplo 6.3.1 veremos una sucesi´ on de n´ umeros que lleva su nombre y que est´ a muy relacionada con los de Fibonacci. Lucas trabaj´ o fundamentalmente en Teor´ıa de N´ umeros, con estudios sobre la sucesi´ on de Fibonacci o sobre criterios de primalidad (criterio de Lucas-Lehmer). Tambi´en gustaba de proponer juegos y acertijos matem´ aticos, como el de las torres de Hanoi que ve´ıamos en el ejemplo 6.1.3, que recogi´ o en sus R´ ecr´eations math´ ematiques de 1882.

(versi´ on preliminar 23 de diciembre de 2003)

388

Cap´ıtulo 6. Ecuaciones de recurrencia

pr eli m in ar

para cada n ≥ 3; de nuevo, la ecuaci´on de Fibonacci. Las condiciones iniciales son ahora F1 = 1, F2 = 1. Conviene deﬁnir F0 = 0 y as´ı la ecuaci´on de recurrencia es v´alida para cada n ≥ 2. En lo sucesivo reservaremos el nombre de Fn para los n´ umeros siguientes: on de la ecuaci´ on Definici´ on 6.1 La sucesi´ on de n´ umeros de Fibonacci Fn es la soluci´ de recurrencia para n ≥ 2 , Fn = Fn−1 + Fn−2 , junto con las condiciones iniciales F0 = 0, F1 = 1. Los primeros t´erminos de esta sucesi´ on son ···

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11

F12

0

144 · · ·

1

1

2

3

5

8

13

21

34

55

89

La resoluci´on de la ecuaci´on de Fibonacci ya no es tan inmediata; veremos c´ omo se puede hacer en la secci´on 6.2. Hagamos el siguiente experimento: calculamos las sucesivas razones de n´ umeros de Fibonacci consecutivos, 1/1 2/1 1

2

3/2

5/3

8/5

13/8

21/13

34/21

55/34

89/55

1,5000 1,6666 1,6000 1,6250 1,6153 1,6190 1,6176 1,6181

144/89 · · · 1,6179

···

Ve rs i´on

Este experimento num´erico sugiere que los n´ umeros de Fibonacci crecen, m´as o menos, con una tasa ﬁja. Es decir, que el cociente de dos n´ umeros de Fibonacci consecutivos Fn /Fn−1 es, aproximadamente, como una constante x > 1, al menos cuando n es muy grande. Ese cociente parece estar en torno a 1,61 “y pico”. Si fuera el caso, ¿qu´e condici´on habr´ıa de cumplir ese hipot´etico n´ umero x? Reescribamos la ecuaci´on de Fibonacci: Fn = Fn−1 + Fn−2

=⇒

Fn 1 =1+ . Fn−1 Fn−1 Fn−2

Si n es muy grande, los dos cocientes que aparecen ser´an, aproximadamente, como x; as´ı que x deber´ıa cumplir que x=1+

1 ; x

en otras palabras, que x2 − x − 1 = 0 .

Las soluciones de esta ecuaci´on de segundo grado son los n´ umeros √ √ 1− 5 1+ 5 y . 2 2 El de la izquierda es un n´ umero negativo, y no nos sirve como “candidato” a ser esa tasa ﬁja de crecimiento. La otra, la ra´ız positiva, es un n´ umero sobre el que ya hablamos en el cap´ıtulo 1: la raz´ on ´ aurea τ , a cuyas peculiaridades dedicaremos toda la secci´on 6.3. (versi´ on preliminar 23 de diciembre de 2003)

6.1. Algunos ejemplos

389

pr eli m in ar

Pero, ¿es cierto o no que Fn /Fn−1 tiende a τ cuando n → ∞? Comprob´emoslo, restando τ a ambos lados de la ecuaci´on de Fibonacci (y utilizando que τ = 1 + 1/τ ):

1 Fn−2 Fn−1 Fn−2 Fn−2 1 Fn −τ =1+ −τ = − =− −τ . Fn−1 Fn−1 Fn−1 τ τ Fn−1 Fn−2 Si tomamos valores absolutos, obtenemos que 1 Fn−2 Fn−1 Fn 1 Fn−1 Fn−1 − τ = τ Fn−1 Fn−2 − τ < τ Fn−2 − τ ,

donde hemos utilizado que los n´ umeros de Fibonacci forman una sucesi´on creciente y que, por tanto, Fn−2 /Fn−1 es menor que 1. Iterando esta desigualdad, llegamos a que 1 Fn−1 Fn 1 Fn−2 1 Fn−1 − τ < τ Fn−2 − τ < τ 2 Fn−3 − τ < · · · < τ n−2

F2 F1 − τ .

Y, como τ > 1, deducimos que, efectivamente, Fn /Fn−1 → τ cuando n → ∞. Ejemplo 6.1.8 Desbarajustes.

♣

Ve rs i´on

Llam´abamos Dn al n´ umero de desbarajustes de {1, . . . , n}, las permutaciones de {1, . . . , n} en las que ning´ un s´ımbolo ocupaba su posici´on. Ya obtuvimos (v´ease la subsecci´on 3.2.4) una f´ormula (un tanto complicada) que nos daba Dn en funci´on de n, utilizando el principio de inclusi´on/exclusi´on. Lo que aqu´ı buscamos es una relaci´on de recurrencia para estos n´ umeros. Los primeros valores son f´ aciles de calcular: D1 = 0, D2 = 1 y D3 = 2. Analicemos el caso n = 4, para hacernos una idea. Tomemos un desbarajuste de los que cuenta D3 ; por ejemplo, 1 2 3 . 3 1 2 Queremos construir un desbarajuste de cuatro posiciones a partir de ´el. El elemento 4 no puede ir en la cuarta posici´on (no ser´ıa desbarajuste), necesariamente ha de ir en una de las tres anteriores. Si va, por ejemplo, en la primera, lo que haremos ser´ a colocar en la cuarta posici´on el elemento que antes iba en la primera (para que siga siendo un desbarajuste); y lo mismo si va en la segunda o en la tercera: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 , , −→ 3 1 4 2 3 4 2 1 4 1 2 3 3 1 2 • Observemos que, para cada desbarajuste de tres posiciones podemos formar 3 desbarajustes de cuatro posiciones (uno por cada posible posible posici´on en la que colocar el 4). Sin embargo, hay unos desbarajustes de cuatro posiciones que no podemos construir de esta manera: por ejemplo, 1 2 3 4 , 4 3 2 1 (versi´ on preliminar 23 de diciembre de 2003)

390

Cap´ıtulo 6. Ecuaciones de recurrencia

pr eli m in ar

pues construir este desbarajuste con el procedimiento anterior requerir´ıa haber partido de una permutaci´on que no es un desbarajuste, la lista (1, 3, 2). Pero estos desbarajustes son muy especiales, son aqu´ellos en los que el 4 y otro elemento forman un ciclo. Centr´emonos en el caso de que sean 1 y 4 los que formen el ciclo: dada esa informaci´ on, basta decidir el resto de las posiciones (en este caso, dos). Y lo que hay que hacer ah´ı es un desbarajuste de dos posiciones. Fij´emonos en que pod´ıamos haber elegido como pareja que forma el ciclo el 2 y el 4, o el 3 y el 4. Y por cada elecci´on de ´estas, hay que hacer un desbarajuste del resto de las posiciones. En total, D4 = 3 D3 + 3 D2 . No es dif´ıcil generalizar este argumento al caso de Dn : por un lado, tendremos aquellos desbarajustes en los que n forme un ciclo con alg´ un otro elemento (en el esquema, el 1): 1 n

2

3

n

4

1

Desbarajuste de n − 2 posiciones

De ´estos tendremos (n − 1)Dn−2 , porque hay n − 1 candidatos a formar el ciclo.

Ve rs i´on

Y, por otro lado, tendremos los desbarajustes que se pueden formar a partir de uno de n − 1 posiciones, con el siguiente proceso: por cada desbarajuste de n − 1 posiciones, elegimos una posici´ on i para colocar el elemento n; en la posici´on n colocamos lo que hubiera en la posici´on i. 1

2

3

i

n−1 n

•

j

1

2

3

-

i

n−1 n

n

j

De ´estas habr´a (n − 1)Dn−1 . En total, si n ≥ 3, Dn = (n − 1)Dn−1 + (n − 1)Dn−2

Es una relaci´ on que involucra, para conocer el valor de un t´ermino, el valor de los dos anteriores. Pero, a diferencia de lo que ocurr´ıa con los ejemplos anteriores, los coeﬁcientes no son constantes, sino que dependen del paso en que estemos.

Pero, afortunadamente, podemos encontrar un truco que nos permite reducirla a una ecuaci´on que s´olo involucra el t´ermino anterior, que resolveremos por simple iteraci´on. La clave es observar que podemos reescribir la recurrencia como Dn − nDn−1 = −Dn−1 + (n − 1)Dn−2 = − [Dn−1 − (n − 1)Dn−2 ] . Y ahora reiteramos el argumento: Dn − nDn−1 = − [Dn−1 − (n − 1)Dn−2 ] = (−1)2 [Dn−2 − (n − 2)Dn−3 ] = = · · · = (−1)n−2 [D2 − 2D1 ] = (−1)n , (versi´ on preliminar 23 de diciembre de 2003)

6.1. Algunos ejemplos

391

donde hemos utilizado los valores iniciales D2 = 1 y D1 = 0. As´ı que, para cada n ≥ 2, Dn − nDn−1 = (−1)n ,

pr eli m in ar

que involucra s´olo el t´ermino anterior. Para resolverla, es mejor dividir toda la expresi´ on por n!: Dn−1 (−1)n Dn − = . n! (n − 1)! n! Y esta ecuaci´on se resuelve con el procedimiento (ya visto en el ejemplo 6.1.2) de sumar todas estas expresiones. As´ı obtenemos que Dn D1 (−1)j − = . n! 1! j! n

j=2

En otras palabras,

Dn = n!

n (−1)j j=2

j!

= n!

n (−1)j j=0

j!

,

porque los t´erminos j = 0 y j = 1 se cancelan entre s´ı. Es, claro, el mismo resultado que el que obten´ıamos con el principio de inclusi´ on/exclusi´on. ♣ Ejemplo 6.1.9 La ruina del jugador.

Ve rs i´on

En ocasiones, las “condiciones iniciales” que determinan, junto a la ecuaci´on de recurrencia, los valores de la sucesi´on, no son como las que hemos visto hasta aqu´ı. El t´ıtulo de este ejemplo inquieta; y m´as lo har´a cuando hagamos los c´alculos correspondientes y comprobemos que no est´a desencaminado. Es ´este un ejemplo cl´asico, que volveremos a estudiar a lo largo del cap´ıtulo y que revisaremos, en otro lenguaje, en la secci´on 16.2 dedicada al paseo aleatorio. Apelaremos aqu´ı a que el lector est´a familiarizado con ciertos conceptos probabil´ısticos, en particular, con la noci´ on de probabilidad condicionada (en caso contrario, puede consultarse el cap´ıtulo 7). Queremos apostar nuestro dinero en un cierto juego. En cada partida apostamos 1 euro; si ganamos, nos devuelven el euro apostado y uno m´as; si perdemos, nada, claro. La probabilidad de ganar cada partida es p, un n´ umero entre 0 y 1 (la de perder ser´a q = 1 − p). Fijamos a priori una cota de N euros, y s´olo abandonaremos el juego cuando la hayamos alcanzado o cuando nos hayamos arruinado5 . Supongamos que empezamos con n euros (0 ≤ n ≤ N ). La pregunta es: ¿cu´al es la probabilidad, que llamaremos a(n), de que nos arruinemos? Hay dos valores inmediatos: por un lado, a(0) = 1, porque no podr´ıamos ni empezar a jugar. Por otro, a(N ) = 0, porque si al principio tenemos N euros, nos retiramos. Como dec´ıamos antes, no son ´estas unas condiciones iniciales al uso, pero ser´an suﬁcientes; quiz´as fuera m´as adecuado llamarlas condiciones de contorno o de frontera. Asumamos que 0 < n < N . Para obtener la regla de recurrencia que cumplen los a(n), vamos a condicionar sobre el resultado de la primera partida. Llamemos G al suceso “ganar 5 ¿Acaso podr´ıamos estar jugando indeﬁnidamente? No es el caso: se puede demostrar, pero esto requiere cierto lenguaje probabil´ıstico, que el juego acaba, con uno u otro resultado, con probabilidad 1.

(versi´ on preliminar 23 de diciembre de 2003)

392

Cap´ıtulo 6. Ecuaciones de recurrencia

la primera” (cuya probabilidad es p) y P al suceso “perder la primera” (de probabilidad q = 1 − p). Entonces,

pr eli m in ar

P(ruina) = P(ruina|G) P(G) + P(ruina|P ) P(P ) .

Pero si hemos ganado la primera partida, tendremos n + 1 euros; y la probabilidad de arruinarnos es la misma que si hubi´eramos empezado a jugar con esos n + 1 euros. El mismo argumento, hecho para el caso de la p´erdida de la primera partida, nos lleva a que a(n) = p a(n + 1) + q a(n − 1)

para cada 1 ≤ n ≤ N .

Es c´omodo reescribir esta relaci´on como a(n + 2) =

q 1 a(n + 1) − a(n) p p

para cada 0 ≤ n ≤ N − 2,

que, junto a las condiciones a(0) = 1 y a(N ) = 0 completan la descripci´on del problema. Lo resolveremos en el ejemplo 6.2.2 y comprobaremos la importancia que tiene el que estemos ante un “juego equilibrado” (p = q = 0,5) o no (p = q). ♣ 3. En funci´ on de todos los casos anteriores

Ejemplo 6.1.10 Contemos el n´ umero de a ´rboles con ra´ız casi binarios que podemos formar con n v´ertices y en los que distinguiremos entre “derecha” e “izquierda”:

Ve rs i´on

◦

◦

◦

◦

=

◦

◦

◦

◦

Nos estamos adelantando un poco, que todav´ıa no hemos estudiado estos objetos, los ´arboles binarios con ra´ız (los veremos con detalle en la secci´on 9.3). Pero en ﬁn, el dibujo nos hace entender de qu´e estamos hablando: la ra´ız es el v´ertice que situamos (curiosamente) m´ as arriba, y que sea (casi)binario quiere decir que cada v´ertice puede tener hasta dos “descenumero de ´arboles con estas caracter´ısticas. Es claro que C1 = 1 y dientes”. Llamemos Cn al n´ C2 = 2. El lector deber´ıa intentar dibujar los 5 a´rboles con tres v´ertices y los 14 con cuatro que existen para comprobar que C3 = 5 y C4 = 14. ◦

Cualquier ´arbol de este tipo tendr´a k v´ertices a la izquierda de la ra´ız y n−1−k a la derecha, donde 0 ≤ k ≤ n−1, como en el dibujo. La elecci´on del ´arbol que va a la izquierda de la ra´ız (que tiene k v´ertices) y la del k n−k−1 que va a la derecha (con el resto de los v´ertices) son independientes, v´ ertices v´ ertices y para contar el n´ umero de posibles elecciones de ambos tendremos en cuenta la diferencia izquierda-derecha. Aplicando la regla de la suma y del producto y deﬁniendo, como resulta conveniente, C0 = 1, obtenemos, Cn = C0 Cn−1 + C1 Cn−2 + · · · + Cn−2 C1 + Cn−1 C0 =

n−1 k=0

(versi´ on preliminar 23 de diciembre de 2003)

Ck Cn−1−k

6.1. Algunos ejemplos

393

pr eli m in ar

Para calcular un cierto t´ermino Cn necesitamos conocer todos los anteriores. Esta recurrencia ya apareci´o en el ejemplo 2.3.3: era la que cumpl´ıan los n´ umeros de Catalan. As´ı que hemos encontrado otro problema combinatorio cuya respuesta est´a en estos n´ umeros. Recordemos que ya ten´ıamos una f´ ormula expl´ıcita para ellos (v´ease el ejemplo 3.1.3). La recurrencia que hemos obtenido aqu´ı la resolveremos utilizando las t´ecnicas de las funciones generatrices. ♣ Ejemplo 6.1.11 El problema de los montones de barriles.

Miramos, desde un lateral, la carga de un cami´on lleno de barriles de cerveza6 . Nos interesan las disposiciones de barriles en las que, en cada ﬁla, los barriles forman una tira continua; y los barriles, por una simple cuesti´ on de equilibrio, han de apoyarse en dos de la ﬁla inferior: S´ı es un mont´ on de 6 barriles

No lo es

Tampoco

distintos podemos formar que tengan n barriles en la ﬁla base. Por ejemplo, hay un u ´nico mont´on con 1 barril en la base y dos montones con 2 barriles en la base. Si n = 3, tenemos cinco posibles montones:

Conviene que el lector obtenga los 13 montones que se pueden formar con 4 barriles en la umero de montones con n barriles en la primera ﬁla. base. Llamemos Mn al n´

Ve rs i´on

Podemos construir un mont´ on de ´estos de la siguiente manera: hay n barriles en la ﬁla inferior, as´ı que lo que hay “encima” es un mont´on con una base de j barriles, donde 0 ≤ j ≤ n − 1. Una vez elegido el valor de j y decidido que tipo de mont´on es (de los Mj posibles), solo queda colocarlo: si j = 0, no tenemos elecci´on (y queda u ´nicamente la ﬁla original); pero si j = 0, el lector puede comprobar que hay n − j posibles posiciones. En conclusi´ on, para cada n ≥ 2, Mn = 1 +

n−1

(n − j)Mj

j=1

M´as adelante, ya con funciones generatrices, deduciremos que Mn es, simplemente, el n´ umero de Fibonacci F2n−1 , para cada n ≥ 1. ♣ Ejemplo 6.1.12 Los n´ umeros de Bell.

Los n´ umeros de Bell B(n) contaban, como ya vimos en la subsecci´on 3.3.1, el n´ umero total de particiones de {1, . . . , n} en bloques no vac´ıos. Los primeros casos son sencillos: B(1) = 1, B(2) = 2, B(3) = 5, etc. Queremos escribir una recurrencia para B(n+1) (algo que ped´ıamos hacer en el ejercicio 3.3.4). Fij´emonos en un bloque especial, el que contiene al elemento n+1. Este bloque estar´a formado, adem´as de por el n + 1, por un cierto subconjunto de {1, . . . , n}. Llamemos n − k al tama˜ no de ese subconjunto, donde 0 ≤ k ≤ n (obs´ervese que tanto k = 0 como k = n est´an 6

Dejamos al lector que imagine la marca, dependiendo de su “religi´ on” cervecera.

(versi´ on preliminar 23 de diciembre de 2003)

394

Cap´ıtulo 6. Ecuaciones de recurrencia

n maneras permitidos). Por supuesto, un subconjunto de ese tama˜ no puede ser elegido de n−k distintas. Una vez decididos qu´e elementos acompa˜ nan a n + 1 en su bloque, basta partir en bloques los k elementos restantes. De todo esto se deduce que, para cada n ≥ 1,

pr eli m in ar

n n B(k) B(n + 1) = 1 + n−k k=1

(el 1 corresponde al caso k = 0, en el que hay un s´ olo bloque). O, de manera m´as compacta, si convenimos en que B(0) = 1, que para cada n ≥ 1, n n B(n + 1) = B(k) n−k k=0

4. Mirando lejos

♣

En los ejemplos vistos hasta aqu´ı, el c´alculo de un t´ermino de la sucesi´on requiere el conocimiento del anterior, de los dos anteriores. . . e incluso de todos los anteriores. Pero a veces la recurrencia es m´as caprichosa, y exige buscar el t´ermino que est´e un cierto n´ umero de posiciones antes, o todas las de un cierto bloque anterior de la sucesi´on. Ejemplo 6.1.13 An´ alisis de un algoritmo que calcula el m´ aximo y el m´ınimo de una lista de n n´ umeros.

Ve rs i´on

umero de Un cierto algoritmo calcula el m´aximo y el m´ınimo de n n´ umeros. Llamemos Cn al n´ comparaciones que necesita el algoritmo para determinarlos. Partimos la lista de n n´ umeros por la mitad aproximadamente (si n es par, exactamente por la mitad; y si es impar, n = 2k + 1, en dos bloques de k y k + 1).

Consideremos el caso de n par, n = 2k. Para determinar el m´aximo y el m´ınimo de los n n´ umeros, debemos determinar el m´aximo y el m´ınimo de cada uno de los bloques, y luego comparar el m´aximo de los dos bloques (una comparaci´on) y el m´ınimo de los dos (otra comparaci´on). En total, Cn = C n2 + C n2 + 2 = 2 C n2 + 2.

En el caso de que n fuera impar, n = 2k + 1, Cn = Ck + Ck+1 + 2.

Reuniendo ambas en una sola f´ormula, Cn = C n + C n + 2. 2 2 A este tipo de ecuaciones de recurrencia se suele llegar al analizar el n´ umero de pasos que efect´ uan los algoritmos del tipo “divide y vencer´ as” (v´ease, por ejemplo, la multiplicaci´on r´apida que describ´ıamos en la secci´on 4.4). ♣ (versi´ on preliminar 23 de diciembre de 2003)

6.1. Algunos ejemplos

395

Ejemplo 6.1.14 Los n´ umeros de Leibniz. Escribimos los n´ umeros naturales en base 2, 2

3

4

5

6

7

8

9

10

11

12

13

14

15

pr eli m in ar

0 1

···

0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 · · · y sumamos los d´ıgitos de esos desarrollos binarios. Llamemos L(n) al resultado de esas sumas: n

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 · · ·

L(n) 0 1 1 2 1 2 2 3 1 2

2

3

2

3

3

4

···

Cuenta la leyenda que fue Leibniz7 el que primero se ﬁj´ o en la sucesi´on {L(n)} mientras esperaba una audiencia del Papa en la que iba a plantearle una propuesta para uniﬁcar las distintas iglesias cristianas (¡los matem´aticos de anta˜ no ten´ıan intereses muy diversos!). Obs´ervese que si, para un cierto k, n < 2k , entonces los desarrollos binarios de n y n + 2k coinciden excepto en la primera posici´on: n + 2k llevar´ıa un 1 y a n le podemos poner un 0. De manera que L(n + 2k ) = L(n) + 1

Ve rs i´on

si 0 ≤ n < 2k . As´ı que para calcular el valor de L(n + 2k ) necesitamos mirar al n´ umero L(n), que est´a mucho antes en la sucesi´on.

Figura 6.2: Leibniz

Veamos c´omo se generan recursivamente los valores de la sucesi´on: los vamos a agrupar dependiendo del bloque di´ adico [2k , 2k+1 ) al que pertenezcan. Empezamos con (L(0), L(1)) = (0, 1) y entonces

L(2), L(3) = L(0 + 2), L(1 + 2) = L(0) + 1, L(1) + 1 = 0, 1 + 1, 1 = 1, 2 .

El siguiente bloque se obtendr´ıa

L(4),L(5), L(6), L(7) = L(0 + 4), L(1 + 4), L(2 + 4), L(3 + 4) = L(0) + 1, L(1) + 1, L(2) + 1, L(3) + 1 = 0, 1, 1, 2 + 1, 1, 1, 1 = 1, 2, 2, 3 . 7

El matem´ atico y ﬁl´ osofo alem´ an Gottfried Leibniz (1646-1716) es considerado, junto con Newton, el inventor del C´ alculo. Leibniz invent´ o notaciones que han llegado a nuestros d´ıas, como dx o el s´ımbolo , y reglas (que hoy llevan su nombre) como la diferenciaci´ on de productos. Para 1676 hab´ıa completado su formulaci´ on del C´ alculo, incluyendo el Teorema Fundamental. Newton hab´ıa desarrollado su m´etodo de ﬂuxiones en 1671, aunque su trabajo no fue publicado hasta 1736. Una pol´emica hist´ orica: ¿qui´en fue antes? Newton acusar´ıa a Leibniz de plagio, desde luego. Fuera quien fuera, parece claro que ambos llegaron a sus conclusiones de manera independiente y que, por supuesto, ambos merecen una posici´ on destacada en el Olimpo matem´ atico.

(versi´ on preliminar 23 de diciembre de 2003)

396

Cap´ıtulo 6. Ecuaciones de recurrencia

El procedimiento es sencillo: para calcular los de un bloque di´ adico, tomamos la lista de todos los anteriores y les sumamos, a cada uno de ellos, 1. Por ejemplo, el siguiente bloque ser´ıa

pr eli m in ar

(L(8), L(9), L(10), L(11), L(12), L(13), L(14), L(15)) =

= (L(0), L(1), L(2), L(3), L(4), L(5), L(6), L(7)) + (1, 1, 1, 1, 1, 1, 1, 1) = (1, 2, 2, 3, 2, 3, 3, 4) Otra propiedad interesante (otra forma de entender la recurrencia que cumplen estos n´ umeros) es que L(2n) = L(n) , porque multiplicar por 2 signiﬁca rodar los coeﬁcientes del desarrollo binario de n una unidad, a˜ nadir un cero a la derecha: por ejemplo, 7 es (101)2 en binario, y su doble, 14, es (1010)2 ; 31 es (11111)2 y 62 es (111110)2 . ♣ 5. Ecuaciones con dos par´ ametros

En el cap´ıtulo 3 introdujimos toda una serie de cantidades que dependen de dos par´ ametros: coeﬁcientes bin´ omicos, n´ umeros de Stirling de primera y segunda especie, n´ umero de particiones de un entero en un cierto n´ umero de partes. Para cada uno de ellos, encontramos relaciones de recurrencia y valores iniciales que permit´ıan obtenerlos. Por recordarlos, veamos un par de casos. Ejemplo 6.1.15 Coeficientes bin´ omicos y n´ umeros de Stirling de segunda especie.

Ve rs i´on

El n´ umero de subconjuntos de tama˜ no k que se pueden extraer del conjunto {1, . . . , n}, C(n, k), satisface la recurrencia doble C(n, k) = C(n − 1, k) + C(n − 1, k − 1)

y las condiciones iniciales son las de los bordes del tri´ angulo de Tartaglia: C(n, 0) = 1, para todo n ≥ 0 y C(n, n) = 1, para todo n ≥ 0.

Cuando cont´ abamos el n´ umero de particiones en k bloques no vac´ıos del conjunto {1, . . . , n}, obten´ıamos los n´ umeros de Stirling de segunda especie, S(n, k), que satisfac´ıan la relaci´on S(n, k) = kS(n − 1, k) + S(n − 1, k − 1)

junto con los valores frontera S(n, n) = 1 y S(n, 1) = 1.

♣

6. Sistemas de ecuaciones A veces, asociado a un cierto par´ametro, digamos n, tenemos dos sucesiones de n´ umeros. Calcular un t´ermino de una de estas sucesiones puede involucrar, tanto a t´erminos de su propia sucesi´on, como a t´erminos de la otra. En estos casos, tendremos un sistema de ecuaciones de recurrencia. umero de listas de longitud n con ceros y unos con un Ejemplo 6.1.16 Calculemos an , el n´ n´ umero par (o cero) de ceros. (versi´ on preliminar 23 de diciembre de 2003)

6.1. Algunos ejemplos

397

pr eli m in ar

Intuitivamente, como es igualmente probable el que aparezca un n´ umero par o un n´ umero impar de ceros, uno esperar´ıa que an = 2n /2 = 2n−1 . Pero por ahora s´olo ha aparecido una sucesi´on, la de los an , en el problema. Pero veamos. Nos ﬁjamos en el s´ımbolo que puede aparecer en la u ´ltima posici´on: si es un 1, el resto de la lista no es sino una de longitud n − 1 con ceros y unos con un n´ umero par de ceros (de las que hay an−1 ). Pero si aparece un 0, lo que queda es una lista de longitud n−1 con un n´ umero impar de ceros. ¡Vaya!, mezclamos aqu´ı otro tipo de objetos. Inventemos un umero de n-listas nombre para ellos y veamos c´omo salimos del aprieto. Si llamamos bn , al n´ de ceros y unos con un n´ umero impar de ceros, podremos establecer una biyecci´on:   ←→ bn−1 0       n´ umero impar de ceros an −→  ←→ an−1  1      n´ umero par de ceros

es decir, que para n ≥ 1,

an = an−1 + bn−1 ,

Ve rs i´on

siendo los valores iniciales a1 = b1 = 1. Pero claro, como hemos introducido una nueva (sucesi´on) inc´ognita, parece necesario buscar una ecuaci´on para ella (lo que hacemos con un razonamiento an´ alogo al anterior). Las reunimos y obtenemos un sistema de ecuaciones de recurrencia, an−1 an 1 1 an = an−1 + bn−1 o bien = . 1 1 bn = an−1 + bn−1 . bn bn−1 A la derecha hemos escrito el sistema en forma matricial; como veremos en la subsecci´on 6.2.3, ´ las t´ecnicas del Algebra Lineal, como el c´alculo de autovalores y la diagonalizaci´on, son las herramientas adecuadas para la resoluci´on del problema. Obs´ervese, de todas formas, que este ejemplo tan sencillo se puede resolver “a mano” ♣ (utilizando, por ejemplo, que sabemos que an + bn = 2n para cada n). 7. Desdoblamiento

En ocasiones, una sucesi´on de n´ umeros obedece a varias ecuaciones de recurrencia; o, m´as bien, en la sucesi´on conviven varias subsucesiones (por ejemplo, los t´erminos de ´ındice par y los de ´ındice impar), cada una de las cuales tiene su propia ecuaci´ on. 1 n x √ , para cada entero n ≥ 0. Ejemplo 6.1.17 Queremos calcular la integral Jn = 1 − x2 0 Empecemos calculando los primeros valores: para J0 usamos el cambio de variables x = sen(t) para obtener que 1 π/2 π 1 cos(t) √ dt = . dx = J0 = cos(t) 2 1 − x2 0 0 (versi´ on preliminar 23 de diciembre de 2003)

398

Cap´ıtulo 6. Ecuaciones de recurrencia

pr eli m in ar

un m´as sencilla: La integral J1 es a´ 1 1 x 2 √ dx = − 1 − x = 1 . J1 = 2 0 1−x 0 La relaci´on de recurrencia la obtendremos integrando por partes, como en el ejemplo 6.1.4: elegimos  du = (n − 1) xn−2 ;  u = xn−1 , √ x  dv = √ dx , v = − 1 − x2 , 1 − x2 para obtener que, para n ≥ 2, 1 1 1 xn−2 1 − x2 dx = (n − 1) xn−2 1 − x2 dx . Jn = −xn−1 1 − x2 + (n − 1) 0

0

0

Parece que nos hemos salido de la familia de integrales Jk ; pero un sencillo truco nos permite volver a ella: 1 1 1 − x2 Jn = (n − 1) xn−2 1 − x2 dx = (n − 1) xn−2 √ dx 1 − x2 0 0 1 1 xn−2 xn √ √ dx −(n − 1) dx . = (n − 1) 1 − x2 1 − x2 0 0 Jn−2

Jn

Reordenando t´erminos llegamos a que

Ve rs i´on

n−1 Jn−2 , para cada n ≥ 2. n Esta recurrencia es f´acil de resolver, basta iterar. Observemos que los t´erminos pares y los impares forman dos sucesiones independientes. Por ejemplo, en el caso par, n = 2k, Jn =

J2k =

2k − 1 (2k − 1)(2k − 3) (2k − 1)(2k − 3) · · · 3 · 1 J2k−2 = J2k−4 = · · · = J0 . 2k (2k)(2k − 2) (2k)(2k − 2) · · · 4 · 2 π/2

Multiplicando numerador y denominador por los factores pares que faltan, llegamos a que (2k)! (2k)! (2k)! 2k π J2k = . 2 = 2 = 2 = 2k+1 k k 2 k (2k (2k − 2) · · · 4 · 2) (2 k (k − 1) · · · 2 · 1) (2 k!)

Una manipulaci´on parecida llev´ o a Wallis a una f´ ormula para estimar el valor de π (ver el ap´endice 2.4.4). Y en el caso impar, n = 2k + 1, J2k+1 =

2k (2k)(2k − 2) (2k)(2k − 2) · · · 4 · 2 J2k−1 = J2k−3 = · · · = J1 . 2k + 1 (2k + 1)(2k − 1) (2k + 1)(2k − 1) · · · 5 · 3 1

Reescribiendo adecuadamente los factores, obtenemos que k 2 2 k! 22k 1 . = J2k+1 = (2k + 1)! 2k + 1 2k k (versi´ on preliminar 23 de diciembre de 2003)

♣

6.1. Algunos ejemplos

399

8. Algunos modelos din´ amicos Ejemplo 6.1.18 Sobre tipos de inter´es y pr´estamos.

pr eli m in ar

¿Sabe el lector realmente c´omo se devuelve un pr´estamo o c´omo se amortiza una hipoteca? En la escritura de un pr´estamo hipotecario, all´a por las u ´ltimas p´aginas, aparece una f´ ormula algo misteriosa que determina, en funci´on de los par´ ametros del contrato (duraci´ on, tipo de inter´es, etc.), el pago mensual al que nos comprometemos. ¿De d´onde sale esa f´ormula? Por si el lector no est´a ducho en la materia, empezaremos con una peque˜ na introducci´on a las nociones de tipo de inter´es y capitalizaci´on. Empecemos deﬁniendo qu´e es el inter´ es: es la cantidad que se percibe por un pr´estamo de dinero en un periodo de tiempo. Tras ese periodo de tiempo, una unidad de dinero, digamos un euro, se transforma en 1

−→

1+I

(capital + intereses).

Si la cantidad inicial es de, por ejemplo, M euros, tras el periodo de tiempo, se tendr´ an M (1 + I) euros, claro. La cantidad I es el tipo de inter´ es, el inter´es percibido por un pr´estamo de 1 unidad de dinero8 . Hablemos ahora de lo que es la capitalizaci´ on: es un contrato que contiene unas reglas de acumulaci´on de pagos de intereses sobre un capital dado. Vamos a interesarnos en el caso de la llamada capitalizaci´on compuesta. Para especiﬁcar un tal contrato se requieren los siguientes datos:

Ve rs i´on

un periodo de tiempo ∆t (normalmente, un a˜ no), un tipo de inter´es R (en tantos por uno) asociado a ese periodo de tiempo; y una frecuencia de capitalizaci´on, m (generalmente, un divisor de 12 o incluso m = ∞).

Por ejemplo, podr´ıamos tener un contrato con un tipo de inter´es R anual y una frecuencia de capitalizaci´on mensual; esto corresponder´ıa a tomar ∆t = 1 a˜ no y m = 12. En un contrato as´ı, decimos que capitalizamos cada ∆t/m: 0

1 ∆t m

2 ∆t m

3 ∆t m

∆t m−1 ∆t m

(obs´ervese que hay m periodos de tiempo; en el ejemplo comentado antes, tendr´ıamos un a˜ no dividido en 12 periodos de un mes). La regla de capitalizaci´ on asociada a los tres datos del contrato signiﬁca lo siguiente: En tiempo 0, el capital es C.

R , el correspondiente al inter´es En tiempo ∆t/m, el capital acumulado ser´ıa C 1 + m producido por el tipo de inter´es (que est´a asociado a ∆t) durante ese periodo de tiempo. 8

Es conveniente se˜ nalar que el tipo de inter´es que consideraremos aqu´ı est´ a expresado en tantos por uno. Es frecuente que un tipo de inter´es se exprese tambi´en en tantos por ciento, as´ı que habr´ a que hacer la conversi´ on correspondiente. As´ı, por ejemplo, un tipo de inter´es I = 0,1 es lo mismo que uno del 10 %.

(versi´ on preliminar 23 de diciembre de 2003)

400

Cap´ıtulo 6. Ecuaciones de recurrencia R 2 En tiempo 2 ∆t/m, el capital acumulado ser´ıa C 1 + m , porque aplicamos la regla de inter´es al capital acumulado hasta el vencimiento anterior.

pr eli m in ar

As´ı calcular´ıamos elvalor del capital en cada instante intermedio. En tiempo ∆t, el valor R m del capital ser´ıa C 1 + m , como corresponde a haber efectuado m capitalizaciones sucesivas. Pero la capitalizaci´on podr´ıa ir m´as all´a. Por ejemplo, el capital en tiempo 2 ∆t = R 2m . En general, el valor en tiempo t, donde t es un m´ ultiplo 2m (∆t)/m ser´ıa C 1 + m de ∆t/m, R k ∆t , ser´ıa C 1 + . t=k m m Nos ofrecen dos contratos de capitalizaci´on distintos: para saber qu´e contrato es m´as beneﬁcioso, necesitamos compararlos. Por ejemplo, supongamos que tenemos dos reglas de capitalizaci´on con los siguientes datos: Regla 1

Regla 2

Semestral, ∆t = 1/2 a˜ no

Trimestral, ∆t = 1/4 a˜ no

frecuencia mensual, m = 6

frecuencia trimestral, m = 1

Tipo inter´es (semestral) R = 0,06

Tipo inter´es (trimestral) S = 0,08

Ve rs i´on

Para poder compararlos, escribimos ambas reglas en t´erminos homog´eneos. Por ejemplo, en qu´e se transforma un capital de 1 en un a˜ no: R 12 regla 1 regla 2 = 1 + TR , 1 −→ (1 + S)4 = 1 + TS . 1 −→ 1 + 6

Calcular los valores de TR y TS supone encontrar los tipos anuales efectivos, TAE, de ambas reglas. Con los valores de R = 0,06 y S = 0,08, obtendr´ıamos TR = 0,1268 y TS = 0,3604, de donde podr´ıamos deducir cu´al es el contrato m´as ventajoso.

Amortizaci´ on de un pr´ estamo. Pasemos al problema que nos interesa, el an´alisis de c´omo se devuelve un pr´estamo. Un banco nos presta una cantidad V y tenemos N a˜ nos para devolverlo. Por supuesto, tendremos que pagar unos intereses, que siguen una regla de una composici´on mensual con tipo de inter´es anual R. Es decir, cada mes pagaremos un inter´es (que calcularemos con R) por la cantidad de dinero que debamos en ese momento al banco; y adem´as querremos ir devolviendo el capital prestado. El m´etodo m´as habitual en los pr´estamos hipotecarios es el llamado sistema franc´ es, en el que se paga una cantidad ﬁja P cada mes. Con el resto de los datos del contrato, querremos calcular cu´al es el montante de ese pago mensual ﬁjo y la cantidad de dinero que habremos pagado al ﬁnalizar la amortizaci´on. Llamemos Dn a la deuda que mantenemos con el banco tras n meses. Entonces, En el instante inicial, debemos la cantidad total, D0 = V . R − P , porque se han acumulado unos Tras el pago del primer mes, D1 = V 1 + 12 intereses y hemos realizado un pago de P . (versi´ on preliminar 23 de diciembre de 2003)

6.1. Algunos ejemplos

401

R Tras el segundo mes, D2 = V 1 + 12 −P 1+ sobre la deuda que manten´ıamos con el banco.

R 12

− P ; ahora acumulamos intereses

pr eli m in ar

Al terminar el contrato, claro, D12 N = 0. Si observamos c´omo hemos calculado D2 , nos damos cuenta de que, en realidad, un argumento de recurrencia nos permite resolver el problema: en un cierto mes, la deuda con el banco ser´ a el resultado de restar a la deuda del mes anterior (m´as los intereses correspondientes) el pago ﬁjo de P . Esto es, R Dn = Dn−1 1 + −P , 12 para cada n ≥ 1. La condici´on inicial es D0 = V , y la condici´on extra D12 N = 0 nos permitir´a obtener el valor de P . Intentemos resolver la recurrencia. Por comodidad, llamemos a = 1 + R/12. Queremos resolver entonces Dn = a Dn−1 − P

para n ≥ 1 ,

D0 = V .

Ecuaciones semejantes a ´esta ya nos las hemos encontrado en varias ocasiones (v´eanse los primeros ejemplos de esta secci´on), y las resolvemos, de nuevo, por iteraci´on: Dn = a Dn−1 − P = a (a Dn−2 − P ) − P = a2 Dn−2 − aP − P = a2 (aDn−3 − P ) − aP − P = a3 Dn−3 − a2 P − aP − P = · · · = an D0 − P (an−1 + an−2 + · · · + a2 + a1 + 1) .

Ve rs i´on

Haciendo la suma geom´etrica que nos ha aparecido, con el valor inicial D0 = V , recordando que a = 1 + R/12 y tras unas cuantas manipulaciones, llegamos a que 12 R n 12 V − P + 1+ P . Dn = R 12 R alculos, determinar el valor de P : Pero como D12 N = 0, podemos, tras unos c´

R 1 . P =V 12 1 − (1 + R/12)−12 N Fij´emonos que, en cada mes, parte del pago P se destina al pago de los intereses, y otra parte a la amortizaci´on de capital. Como casi todo el mundo sabe, estos repartos var´ıan durante la vida del pr´estamo. Llamemos In a la cantidad invertida en intereses y Cn la destinada a capital, de manera que P = In + Cn . En el mes n se pagan los intereses generados desde el u ´ltimo pago, esto es, In = R Dn−1 /12. Como tenemos una expresi´on expl´ıcita para los Dn y para P , conocemos In y Cn . Pongamos unos datos, para hacernos una idea. El pr´estamo es de V = 60000 euros, se devuelve en n = 20 a˜ nos y el tipo de inter´es anual es R = 0,05. Con estos datos, el pago mensual (ﬁjo) es de P = 395, 97 euros. Las siguientes gr´aﬁcas muestran c´omo va disminuyendo la deuda con el banco a lo largo de los 240 meses de vida del pr´estamo (gr´aﬁca de la izquierda) y qu´e parte del pago se destina a intereses y qu´e parte a capital (gr´aﬁca de la derecha; como es bien sabido, al principio pagamos sobre todo intereses) (versi´ on preliminar 23 de diciembre de 2003)

402

Cap´ıtulo 6. Ecuaciones de recurrencia

400

60000 50000

300

pr eli m in ar

40000 200

30000 20000

100

10000 0

50

100

150

0

200

50

100

150

200

El lector podr´ a extraer conclusiones sobre la conveniencia de cancelar el pr´estamo cuando est´a pr´oximo al vencimiento (algo que se hace habitualmente). Existen otros sistemas de amortizaci´on de pr´estamos, que explicamos en los ejercicios 6.1.9 al 6.1.10. ♣ Ejemplo 6.1.19 C´ omo se administran medicamentos.

Para tratar una cierta enfermedad tomamos una cantidad ﬁja C de medicamento cada N horas. Buscamos un modelo matem´atico que permita determinar los valores de los par´ ametros C y N para que (1) la cantidad de medicamento en el organismo no supere nunca un cierto umbral de toxicidad B; y (2) que esa cantidad de medicamento siempre est´e por encima de un umbral de eﬁcacia A, por debajo del cual el medicamento no surte efecto.

Ve rs i´on

Tras cada N horas, s´ olo una fracci´ on d (un n´ umero entre 0 y 1) de la cantidad de droga presente en el organismo se mantiene; el resto desaparece. Digamos que esta eliminaci´on sigue un modelo de decaimiento exponencial: si en un cierto momento hay una cantidad D de medicamento, tras un tiempo t s´olo quedar´a D e−k t ,

donde k > 0 es una cantidad (la constante de decaimiento) que depender´a de diversos factores ametro, y que supondremos conocida9 . Esto supone que, en realidad, d no es un nuevo par´ sino que est´a relacionado con N mediante d = e−N t . Si N muy grande, es decir, las tomas est´an muy espaciadas, entonces d ser´a muy cercano a 0, y casi toda la droga desaparecer´a.

Vamos a suponer, por simplicidad, que el paso del medicamento al torrente sangu´ıneo es instant´aneo. Las tomas se producen en tiempos t0 , t1 , t2 , . . . Llamaremos yn e xn a las cantidades de droga en sangre justo antes e inmediatamente despu´es de la toma de tiempo tn , respectivamente. Los n´ umeros yn cumplen que yn = dxn−1 para cada n ≥ 1, porque s´olo se mantendr´a una fracci´on d de la cantidad presente tras la toma anterior. La otra sucesi´on de n´ umeros cumple que, para cada n ≥ 1, xn = yn + C = dxn−1 + C 9

Una manera habitual de dar el valor de esta constante es a trav´es de la (semi)vida media: es el tiempo que tarda en desaparecer la mitad de la cantidad inicial. Si llamamos Tm a este tiempo, entonces e−k Tm = 0,5, de donde podemos obtener el valor de k: k = log(2)/Tm .

(versi´ on preliminar 23 de diciembre de 2003)

6.1. Algunos ejemplos

403

Esta ecuaci´on se puede resolver por simple iteraci´on (y utilizando que x0 = C). Dejamos al lector que compruebe que las dos sucesiones de n´ umeros de inter´es son, para cada n ≥ 1, 1 − dn+1 1−d

B x2

x1

x4

x3

x0 = C

y4

y3

y2 y1

A t0

t1

t2

t3

xn = C

t4

e

yn = C

d − dn+1 . 1−d

pr eli m in ar

xn = C

1 − dn+1 ≤B 1−d

Querremos elegir valores de C y de N (o, lo que es lo mismo, de d) para los que, como en el dibujo, la cantidad de medicamento en sangre se mantenga siempre entre los dos l´ımites A y B (por supuesto, C ha de estar ya en el rango adecuado). El asunto es m´as delicado de lo que pudiera parecer. Observemos que ambas sucesiones, xn e yn , son crecientes, y necesitamos que y que

yn = C

d − dn+1 ≥ A. 1−d

La condici´on de la derecha se cumplir´a si el primero de los yn , esto es, y1 = dC, lo hace. Para la de la izquierda, ser´a suﬁciente con exigir que se cumpla para el l´ımn→∞ xn = C/(1 − d).

Ve rs i´on

De todo este an´alisis se deduce que los par´ametros del problema C y d han de veriﬁcar que

C

6

B

A ≤ C ≤ B(1 − d) . d

A

-d Y esto no es siempre posible. La regi´on que determina, en 0 1 el plano (d, C), la doble desigualdad anterior es la encerrada C entre las gr´ aﬁcas de A/d y B(1 − d). . . ¡y esa regi´on bien 6 pudiera no existir! En los dibujos de la derecha observamos las dos posibilidades: si B est´a cercano a A, el problema B no tiene soluci´on. Un an´ alisis m´as detallado, que dejamos como ejercicio al lector (v´ease el ejercicio 6.1.11), nos dice A que estaremos en el caso con soluci´on siempre que10 B ≥ 4A. -d 1 0 En este caso, tenemos toda una regi´on de pares de valores (d, C) admisibles para el sistema. Por ejemplo, si d est´a dado (es decir, si establecemos el tiempo entre tomas), podr´ıamos determinar la menor cantidad C que permite que las cosas funcionen; o al rev´es, dado un cierto C, la cantidad de medicamento que contiene una pastilla, podemos determinar el mayor espaciado entre tomas posible. El ejercicio 6.1.12 tiene los detalles. ♣ 10

Esto podr´ıa parecer muy restrictivo. La ratio entre B y A depende del medicamento en cuesti´ on, y en alg´ un caso es de tan solo 2 a 1 (aqu´ı estamos exigiendo 4 a 1). Como el lector podr´ a comprobar (v´ease el ejercicio 6.1.13), esta exigente ratio de 4 a 1 se puede reducir si nos damos un grado de libertad extra, como es el que la primera toma sea especial.

(versi´ on preliminar 23 de diciembre de 2003)

404

Cap´ıtulo 6. Ecuaciones de recurrencia

Ejemplo 6.1.20 El problema de Josefo. El que vamos a explicar a continuaci´on es, quiz´as, uno de los primeros problemas combinatorios de la Historia, una variaci´ on sobre el n 2 problema original que preocupaba a Flavio Josefo11 . Tenemos n pern−1 sonas sentadas a una mesa circular y vamos eliminando a la segunda 3 persona que nos vayamos encontrando en el sentido de las agujas del reloj (empezando a contar desde la primera posici´on), hasta que s´ olo 4 una sobreviva. El desaf´ıo, por supuesto, es calcular la posici´on inicial que debe ocupar una persona si quiere sobrevivir. Llamemos J(n) a la posici´on inicial que ha de ocupar el superviviente. Los primeros casos se pueden calcular a mano:

pr eli m in ar

1

n

1

2 3

4 5 6 7

8 9 10 11 12 13 14 15

16 · · ·

J(n)

1

1 3

1 3 5 7

1 3

1

5

7

9

11 13 15

···

Esta tabla sugiere algunas observaciones: primero, parece que todas las “posiciones de supervivencia” son impares (y as´ı debe ser, pues en la primera pasada eliminamos todas las posiciones pares). Adem´as, da la impresi´on de que los bloques di´adicos tienen algo que decir en el problema.

Ve rs i´on

Vayamos con un an´ alisis m´as cuidadoso: parece razonable distinguir los casos en que n sea par o impar. 1 Empezamos con el caso par, con n = 2k per1 2k−1 3 2 2k sonas. Queremos evaluar J(2k). En la prime2k−3 2k−1 5 ra pasada eliminamos a todas las personas que 3 ocupen posiciones pares, como se muestra en la 7 4 ﬁgura. Y la conﬁguraci´on que nos queda consta de k personas, aunque ahora no numeradas de 1 a k. Si estuvieran “bien” numeradas, la posici´on de supervivencia vendr´ıa dada, directamente, por J(k). No lo est´an, pero no es dif´ıcil recuperar ese orden: basta observar que la posici´on 2 ahora est´a etiquetada con 3, la 3 con 5, la 4 con 7, la 5 con 9, etc. Esto es, hemos doblado cada posici´on y le hemos restado 1. Si m es la posici´on superviviente con el orden (1, 2, . . . , k) (de manera que m = J(k)), con el nuevo etiquetado (1, 3, 5, . . . , 2k − 1) el superviviente ser´a 2m − 1. As´ı hemos conseguido escribir la ecuaci´on de recurrencia J(2k) = 2 J(k) − 1 ,

v´alida para cada k ≥ 1 (compr´ uebese que es coherente con los valores ya calculados). 11

El historiador jud´ıo Flavio Josefo (37- circa 100) particip´ o en la revuelta contra el poder romano del a˜ no 66 y escap´ o a la matanza que tuvo lugar despu´es de la toma de la ciudadela de Josapata. Se cuenta, quiz´ as ya con un tono algo legendario, que 41 rebeldes fueron cercados por las tropas romanas y que, antes de ser capturados, preﬁrieron el suicidio colectivo. S´ olo Josefo y otro compa˜ nero no parec´ıan muy convencidos de la utilidad del sacriﬁcio, as´ı que nuestro personaje propuso el siguiente sistema de inmolaci´ on: sentados a una mesa circular, se ir´ıa eliminando a cada tercera persona hasta que s´ olo dos sobrevivieran. Estos dos u ´ ltimos deber´ıan ser los u ´ltimos en morir. Josefo calcul´ o las posiciones que deb´ıan ocupar ´el y un compa˜ nero para sobrevivir al proceso.

(versi´ on preliminar 23 de diciembre de 2003)

6.1. Algunos ejemplos

405

pr eli m in ar

3 1 El caso impar, n = 2k + 1, es an´alogo. Aho2k+1 5 2k+1 2 ra la primera pasada elimina, de nuevo, a todas - 2k−1 7 3 las personas que ocupen posiciones pares, y a´ un 2k sobreviven k + 1 personas. Para llegar a una con9 4 ﬁguraci´on con k personas, observamos que la siguiente v´ıctima es la que ocupaba la posici´on 1. As´ı que, tras estos pasos, nos queda la conﬁguraci´on de la ﬁgura. Y, con argumentos an´ alogos a los de antes, establecemos que, para cada k ≥ 1, J(2k + 1) = 2 J(k) + 1.

Ahora ya tenemos las relaciones de recursi´on que satisfacen estos n´ umeros de Josefo: para cada k ≥ 1, J(2k) = 2 J(k) − 1

J(2k + 1) = 2 J(k) + 1

que nos permiten, junto con la condici´ on inicial J(1) = 1, generar la sucesi´on de los J(n). Uno estar´ıa tentado de resolverlas por simple iteraci´ on. Pero observemos que no es tan sencillo: partimos de un cierto n, y ya hay que ver si es par o impar para saber qu´e regla hay que aplicar. Por ejemplo, si n = 2k, aplicamos la primera. Pero en la siguiente iteraci´on hay que comprobar de nuevo la paridad, esta vez de k. Y aunque esto es un algoritmo que se puede implementar, no parece que vaya a conducir a una f´ ormula cerrada.

Ve rs i´on

No tendr´ıamos estas diﬁcultades si, por ejemplo, n fuera una potencia de 2, digamos n = 2m , porque siempre tendr´ıamos que aplicar la primera regla. Dejamos al lector que se ejercite comprobando que la iteraci´ on de la primera f´ ormula conduce a que J(2m ) = 1. Vamos a cambiar el enfoque: dado que lo que parece relevante aqu´ı es la paridad de n (y de sus sucesivas “mitades”), utilicemos la expresi´on binaria de n, n = (ak , ak−1 , . . . , a1 , a0 )2 ,

donde los aj ∈ {0, 1} y ak = 1.

Si estamos en el caso en que n es par (esto es, si a0 = 0), las relaciones de arriba nos exigen calcular el n´ umero de Josefo en n/2. Y la expresi´on binaria de n/2 es (ak , ak−1 , . . . , a2 , a1 )2 , pues s´olo hay que eliminar la u ´ltima cifra del desarrollo binario. Por otro lado, si n es impar, el n´ umero que nos interesa es ahora (n − 1)/2, cuya expresi´on en binario, como puede comprobar el lector es, de nuevo, (ak , ak−1 , . . . , a2 , a1 )2 . ¡Estupendo!, porque, si utilizamos la expresi´on binaria de n, la relaci´on de recurrencia se simpliﬁca notablemente: J ((ak , ak−1 , . . . , a1 , a0 )2 ) = 2 J ((ak , ak−1 , . . . , a1 )2 ) + (−1)a0 +1 (n´otese que sum´abamos un 1 o un −1 dependiendo de la paridad de n, esto es, del valor de (versi´ on preliminar 23 de diciembre de 2003)

406

Cap´ıtulo 6. Ecuaciones de recurrencia

a0 ). Y esta relaci´on s´ı que se puede iterar: J ((ak , . . . , a0 )2 ) = 2 2 J ((ak , . . . , a2 )2 ) + (−1)a1 +1 + (−1)a0 +1

pr eli m in ar

= 22 J ((ak , . . . , a2 )2 ) + 2 (−1)a1 +1 + (−1)a0 +1

= 23 J ((ak , . . . , a3 )2 ) + 22 (−1)a2 +1 + 2 (−1)a1 +1 + (−1)a0 +1 .. . k−1 (−1)aj +1 2j , = 2k J ((ak )2 ) + =1

j=0

porque ak = 1. Y ya tenemos la f´ormula que busc´abamos: si n = (ak , ak−1 , . . . , a1 , a0 )2 ,

entonces

J ((ak , . . . , a0 )2 ) =

k

(−1)aj +1 2j .

j=0

para cuya aplicaci´on basta con conocer la expresi´on en binario de n. En el ejercicio 6.1.14 se pide obtener una f´ ormula alternativa. ♣ EJERCICIOS.

Ve rs i´on

6.1.1 Tenemos dos sucesiones de n´ umeros, (an ) y {An }, cuyos primeros t´erminos coinciden: a1 = A1 . De la primera sabemos que cumple que an ≤ 2an−1 + 1 ,

para cada n ≥ 2.

Por su parte, la segunda sucesi´ on verifica la ecuaci´ on de recurrencia An = 2An−1 + 1 ,

para cada n ≥ 2.

Probar, por inducci´ on, que an ≤ An para cada n ≥ 1. umero de formas de distribuir 6.1.2 Obtener una f´ ormula de recurrencia para an,k , siendo an,k el n´ n bolas id´enticas en k cajas numeradas de forma que en cada caja haya entre 2 y 4 bolas. Sugerencia. Establecer una partici´ on de las distribuciones totales seg´ un el n´ umero de bolas (2, 3 o 4) que lleve la u ´ltima caja.

Soluci´ on. an,k = an−2,k−1 + an−3,k−1 + an−4,k−1 . 6.1.3 Obtener una f´ ormula de recurrencia para an , siendo an el n´ umero de tiras de ceros y unos de longitud a lo sumo n donde hay exactamente tres unos, uno de los cuales es el u ´ltimo s´ımbolo. Sugerencia. Observar que las listas que cuenta an son, o bien listas de longitud a lo sumo n − 1, o bien listas de longitud exactamente n. Para contar ´estas u ´ltimas, basta decidir la posici´ on de los dos unos que no est´ an en la u ´ltima posici´on de la lista.

(versi´ on preliminar 23 de diciembre de 2003)

6.1. Algunos ejemplos Soluci´ on. an = an−1 +

407 n−1 2 .

pr eli m in ar

umero de listas de longitud n formadas con 6.1.4 Obtener una ecuaci´ on de recurrencia para bn , el n´ elementos de {0, 1, 2} en las que no aparecen ni dos unos consecutivos ni dos doses consecutivos. Sugerencia. Distinguir entre las listas que acaban en 0, en 1 o en 2. El primer caso es trivial, y en los otros casos, distinguir a su vez entre las distintas posibilidades. Por ejemplo, las listas que acaban en 1 pueden acabar en 01 (que son f´ aciles de contar) o en 21; para ´estas, habr´a que volver a distinguir los dos casos posibles. Otra forma de abordar el problema es establecer un sistema de recurrencias, introduciendo tres nuevas sucesiones, las que cumplen las condiciones y acaban en 0, las que lo hacen en 1 y aqu´ellas que acaban en 2. Soluci´ on. bn = bn−1 + 2

n−2 j=1

bj + 4.

6.1.5 En el problema de la ruina del jugador (v´ease el ejemplo 6.1.9), nos interesa tambi´en la duraci´ on media del juego, d(n), cuando se parte de una fortuna n. Obs´ervese que d(0) = d(N ) = 0. Obt´engase que, para cada n en el rango adecuado, d(n) = p d(n + 1) + q d(n − 1) + 1 .

6.1.6 La sucesi´ on de n´ umeros L(n) del ejemplo 6.1.14 nos permite reescribir el resultado de la p´ agina 308 sobre el n´ umero de coeficientes bin´ omicos que son impares. Comprobar que n #{k ≤ n : es impar} = 2L(n) , k

Ve rs i´on

6.1.7 Comprobar, por inducci´ on, que si m ≥ 0, entonces n 2 −1

2L(k) = 3n ,

k=0

donde los L(k) son los n´ umeros de Leibniz del ejemplo 6.1.14.

∞

6.1.8 Definamos Hn =

e−t sinn (t)dt . Compr´ uebese que H(0) = 1 y H(1) = 1/2, y que

0

Hk =

k(k − 1) Hk−2 , 1 + k2

para cada k ≥ 2.

Ded´ uzcanse las f´ ormulas para las integrales de ´ındice par H2k y las de ´ındice impar H2k+1 . Soluci´ on. Para cada k ≥ 1,

H2k (2k)!

=

k

1 j=1 1+4j 2

y

H2k+1 (2k+1)!

=

k

1 j=1 1+(2j+1)2

6.1.9 Otro sistema para amortizar un pr´estamo consiste en lo siguiente: cada mes se pagan los intereses generados en el periodo anterior y se amortiza una cantidad fija C de capital. As´ı, el pago mensual, Pn , ser´ a Pn = In + C , para n ≥ 1, donde In es el inter´es generado desde el pago anterior. Obs´ervese que ahora el pago mensual no es fijo, sino que va decreciendo con el tiempo. Llamemos Dn a la deuda con el banco en el mes n.

(versi´ on preliminar 23 de diciembre de 2003)

408

Cap´ıtulo 6. Ecuaciones de recurrencia

(a) Obtener una f´ ormula para Dn . (b) De la condici´ on D12 N = 0, obtener el valor de C.

pr eli m in ar

(c) Con estas expresiones, obtener los valores de In y de Pn .

(d) Con los datos R = 0,05, N = 20 a˜ nos y V = 10 millones, dibujar la gr´ afica de los pagos de intereses y capital. Soluci´ on. (a) Dn = V − n C.

V 12 N

(b)C =

. (c)In =

V R 12

1−

n−1 12 N

,

Pn = In +

V 12 N .

6.1.10 Una tercera forma de amortizaci´ on es el llamado sistema americano. Dados los datos R, V y N como antes, se devuelve toda la deuda y sus intereses en un u ´nico pago al final del contrato. Esto es, se hace un pago en el mes 12 N de Pfinal = V

12 N R 1+ . 12

Para acumular ese capital se crea un fondo al que se contribuye con una cantidad fija P cada mes; este dinero se capitaliza mensualmente con un tipo de inter´es anual S (generalmente, distinto de R). Se pide establecer una recurrencia para An , el capital acumulado tras la aportaci´ on del mes n. Y, con la condici´ on de que A12 N = Pfinal , obtener el valor de P . 6.1.11 Estamos con el modelo de toma de medicamentos explicado en el ejemplo 6.1.19. Hallar los rangos de los par´ ametros d y C en los que mantendremos la cantidad de medicamento entre los l´ımites A y B. Deducir las condiciones sobre A y B para que estos rangos realmente existan.

Ve rs i´on Soluci´ on. (a) d ∈ ( 12 −

1 4

−

A 1 B, 2

+

1 4

−

A B ), C

∈ (B( 12 −

1 4

−

A 1 B ), B( 2

+

1 4

−

A B ))

6.1.12 Seguimos con el modelo de la toma de medicamentos. Los valores l´ımite son A = 100 y B = 500. Comprobar que el problema tiene soluci´ on y determinar los rangos para los par´ ametros d y C. El medicamento est´ a caracterizado por un valor de k = 2. (a) Si C = 200, ¿cu´ al ser´ a el mayor valor de N posible? (b) Si queremos que las tomas sean cada 8 horas, ¿cu´ al ser´ a la menor cantidad de medicamento que podr´ a llevar la pastilla?

6.1.13 Repetir el an´ alisis del ejemplo 6.1.19 suponiendo que la primera toma es especial, C0 (las restantes siguen siendo todas de C). Hallar xn e yn y comprobar las condiciones en las que tendremos soluci´ on. 6.1.14 Estamos con el problema de Josefo del ejemplo 6.1.20. Supongamos que la expresi´ on binaria de n es (ak , ak−1 , . . . , a1 , a0 )2 , donde ak = 1.

(a) Consideremos el n´ umero N cuya expresi´ on en binario tiene la misma longitud que la de n y sus k j cifras son todo unos; esto es, N = j=0 2 . Calcular 2n − N y comprobar que coincide con el valor de J(n). (b) Comprobar, utilizando el apartado anterior, que si escribimos n = 2k + l, con 0 ≤ l < 2k , entonces J(2k + l) = 2l + 1 . (c) Aplicar esta f´ ormula al c´ alculo de J(134) y J(1356).

(versi´ on preliminar 23 de diciembre de 2003)

6.1. Algunos ejemplos

409

pr eli m in ar

6.1.15 Una prueba alternativa de la f´ ormula del ejercicio anterior. En el texto ya se sugiri´ o probar que J(2k ) = 1, para cualquier k ≥ 0, de manera que el que ocupa la primera posici´ on es el superviviente en este caso. Ahora supongamos que n = 2k +l, con 0 ≤ l < 2k . Dejamos que el proceso de eliminaci´ on acabe con los l primeros. Determinar cu´ ales son para completar el argumento. 6.1.16 Utilizar la f´ ormula obtenida en el ejercicio 6.1.14 para probar que

J((ak , ak−1 , . . . a1 , a0 )2 ) = (ak−1 , ak−2 , . . . , a1 , a0 , ak )2 ;

esto es, que podemos obtener el valor de J(n) permutando c´ıclicamente una posici´ on de la expresi´ on binaria de n. 6.1.17 Ciertos n´ umeros cumplen que J(n) = n/2. Es el caso, por ejemplo, de 2, 10, 42, 170, etc. Utilizando el ejercicio 6.1.16, caracterizar los n´ umeros para los que esto ocurre. Soluci´ on. Los n´ umeros de la forma (1010 . . . 1010)2 .

6.1.18 Seguimos con el problema de Josefo, pero ahora queremos salvar a dos personas. Hallar K(n), la posici´ on que debe ocupar inicialmente una persona para ser la pen´ ultima en el proceso y as´ı poder salvarse tambi´en (al menos, si el u ´ltimo es clemente). 6.1.19 Compru´ebese que la soluci´ on del problema original de Josefo (v´ease la nota al pie en el ejemplo 6.1.20) es, con la notaci´ on adecuada a la cuesti´ on, J3 (41) = 31.

Ve rs i´on

6.1.20 De la cunicultura a la apicultura. Los z´ anganos tienen madre, la reina, pero cada reina tiene padre y madre. En el a ´rbol geneal´ ogico de un z´ angano, ¿cu´ antos antecesores hay si nos remontamos n generaciones? Obt´engase una ecuaci´ on de recurrencia. 6.1.21 Consideremos un pol´ıgono regular de n + 2 v´ertices, etiquetados (circularmente) con los umero de maneras de triangular, es decir, partir en n n´ umeros {0, 1, . . . , n + 1}. Llamemos Tn al n´ tri´ angulos, usando n−1 diagonales. Comprobar que los Tn satisfacen la recurrencia del ejemplo 6.1.10. 6.1.22 Consideremos una funci´ on f : X → X , donde X = {1, . . . , N }. Sea a0 ∈ X . Definimos a1 = f (a0 ), a2 = f (a1 ) y, en general, an = f (an−1 ). Comprobar que existe un n0 y un k tales que an+k = an para todo n ≥ n0 . 6.1.23 Anal´ıcense, a la luz del ejercicio anterior, los siguientes sistemas din´ amicos para diversos valores de a0 : a) El conjunto X = {0, 1, 2, . . . , 6} y la funci´ on f : X → X , donde f (n) es el resto de dividir 3n por 7. b) Sea X = {0, 1, . . . , 9999}. La regla f es la siguiente: dado n ∈ X , consideramos los n´ umeros a (que tiene las mismas cifras que n, pero ordenadas de menor a mayor) y b (mismas cifras que n, pero de mayor a menor). Finalmente, f (n) = b − a. Por ejemplo, si n = 3075, entonces a = 0357 y b = 7530, de manera que f (n) = 7173.

6.1.24 En el esquema de Fibonacci del ejemplo 6.1.7, los conejos tienen dos parejas de descendientes umero de cuando tienen 2 meses, y tres parejas a partir del tercer mes de vida. Llamemos an al n´ conejos que en el mes n tienen 3 meses de vida o m´ as, bn a los que tienen exactamente 2 meses y cn a los de 1 mes. Suponemos que c0 = 1 y a0 = b0 = 0. Escr´ıbase una recurrencia (matricial) para (an , bn , cn ) y ded´ uzcase una expresi´ on para el n´ umero total de conejos en el mes n.

(versi´ on preliminar 23 de diciembre de 2003)

410

Cap´ıtulo 6. Ecuaciones de recurrencia

6.1.25 Consid´erese la sucesi´ on de signos ±1 dada por la siguiente regla: u(2n) = u(n) ,

para cada n ≥ 1

y

u(2n + 1) = (−1)n ,

para cada n ≥ 0.

pr eli m in ar

Escr´ıbanse los primeros t´erminos. Observemos que todo n´ umero natural n se puede escribir de manera u ´nica en la forma n = as que agrupar los doses de su desarrollo en primos. Compr´ uebese 2r (2s + 1), con r ≥ 0 y s ≥ 0, sin m´ que la regla de recurrencia anterior se puede escribir como sigue:

Ve rs i´on

u(2r (2s + 1)) = (−1)s .

(versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

6.2.

411

Resoluci´ on de ecuaciones de recurrencia

6.2.1.

pr eli m in ar

Como el lector podr´a imaginar, la variedad de ecuaciones de recurrencia que se pueden plantear es inmensa. Y, en la mayor´ıa de ellas, resolverlas es una tarea dif´ıcil, si no imposible. Aqu´ı nos limitaremos a estudiar algunos casos particulares, sobre todo las ecuaciones lineales. Hay m´etodos para resolver otras familias de ecuaciones, pero dado que las funciones generatrices, que introduciremos en el cap´ıtulo 10, nos permitir´an abordar estos problemas m´as f´acilmente, obviaremos su descripci´on.

Ecuaciones lineales, homog´ eneas y con coeﬁcientes constantes

En esta subsecci´on nos interesaremos por las sucesiones (an )∞ on de n=0 que son soluci´ ecuaciones como la siguiente: A0 an + A1 an−1 + · · · + Ak an−k = 0 para cada n ≥ k,

donde los A0 , A1 , . . . , An−k son ciertos n´ umeros dados, con A0 , Ak = 0, y k ≥ 1. Observemos que, de manera muy sint´etica, estamos representando inﬁnitas condiciones para los t´erminos de la sucesi´on. Sin p´erdida alguna de generalidad, podemos suponer que A0 = 1, y muchas veces escribiremos la ecuaci´on de la siguiente forma: an = B1 an−1 + B2 an−2 + · · · + Bk an−k

para cada n ≥ k,

Ve rs i´on

para insistir en que cada t´ermino de la sucesi´on (a partir de un cierto ´ındice) se escribe como combinaci´on lineal (con coeficientes constantes) de unos cuantos t´erminos anteriores. La homogeneidad a la que nos referimos quiere decir que no aparecen t´erminos extra que no alisis que vamos a hacer. dependan de los propios aj . Esto resulta ser fundamental en el an´ En la subsecci´on 6.2.2 veremos c´omo podremos tratar el caso en que aparezcan t´erminos no homog´eneos. El n´ umero de t´erminos anteriores involucrados ser´ a el grado de la ecuaci´on: k, en el caso de la que hemos escrito (y diremos que la ecuaci´on es de orden k). Necesitaremos, adem´as, k condiciones iniciales para que la sucesi´on “arranque”; en el caso de arriba, los n´ umeros a0 , a1 , . . . , ak−1 . De todos los que hemos visto en la primera secci´on de este cap´ıtulo, s´olo los ejemplos 6.1.1, 6.1.5, 6.1.6, 6.1.7 y 6.1.9 son de este tipo. El caso k = 1, la ecuaci´on de primer grado, es especialmente sencillo, y la resoluci´ on se basa en la aplicaci´on reiterada de la ecuaci´on hasta llegar al valor inicial. Esto ya lo hemos hecho en varias ocasiones, incluso permitiendo la presencia de un t´ermino extra constante (ve´anse los ejemplos 6.1.3, 6.1.18 y 6.1.19; rev´ısese tambi´en el ejercicio 6.2.1), as´ı que no insistiremos en ello, aunque todas las propiedades generales que iremos descubriendo tambi´en se aplican a este caso. Los ingredientes del estudio general que vamos a desarrollar est´ an ya presentes en el caso de la ecuaci´on lineal homog´enea de segundo orden, a la que a˜ nadimos dos condiciones iniciales: an = α an−1 + β an−2 para cada n ≥ 2; (∗) a0 = p ,

a1 = q .

(versi´ on preliminar 23 de diciembre de 2003)

412

Cap´ıtulo 6. Ecuaciones de recurrencia

pr eli m in ar

´ Esta ser´a nuestra gu´ıa en los argumentos: los datos son α, β, p y q, y el objetivo es obtener una f´ ormula para an en t´erminos de n. Conviene aqu´ı se˜ nalar que tener una f´ ormula cerrada para la soluci´on no signiﬁca necesariamente que ´esta sea la manera m´as eﬁcaz de calcular los valores de la sucesi´on (la ecuaci´on de recurrencia podr´ıa ser un mejor m´etodo). La utilidad de una tal f´ ormula, muchas veces, consiste en que nos permite entender el comportamiento de los an (por ejemplo, para n grande) en t´erminos de ciertas cantidades que en un primer vistazo podr´ıan pasar inadvertidas. Tendremos esto en cuenta, y mucho, en el an´ alisis que vamos a hacer. Aunque es el problema completo (ecuaci´on m´as condiciones iniciales) lo que nos interesa, muchas de las propiedades de las soluciones s´ olo dependen de la ecuaci´on, as´ı que de ella haremos un an´ alisis espec´ıﬁco. A. Estructura de las soluciones

Ve rs i´on

Parece razonable iniciar el estudio asegur´ andonos de la existencia de soluciones. En el caso que nos ocupa, esta cuesti´on es sencilla, pues basta “arrancar” la sucesi´on a partir de los valores iniciales. Con el mismo argumento podemos comprobar la unicidad de la soluci´on del problema completo12 . Esto es muy importante: de entre todas las posibles sucesiones que satisfacen la ecuaci´on, s´olo una veriﬁca, adem´ as, las condiciones iniciales. As´ı que nos centramos en el estudio de la ecuaci´ on. Diremos que una sucesi´on (an )∞ n=0 = (a0 , a1 , a2 , a3 , . . . ) es soluci´ on de la ecuaci´on (∗) si sus t´erminos, a partir de a2 , veriﬁcan las inﬁnitas condiciones que tan abreviadamente hemos escrito en (∗). Las siguientes son observaciones inmediatas al respecto de estas soluciones: 1.

Si (an ) y (bn ) son dos soluciones de (∗), entonces la sucesi´on (cn ) deﬁnida mediante cn = an + bn tambi´en lo es pues, para cada n ≥ 2, cn = an + bn = α an−1 + β an−2 + α bn−1 + β bn−2 = α (an−1 + bn−1 ) + β (an−2 + bn−2 ) = α cn−1 + β cn−2 .

2.

De la misma manera, se comprueba que si (an ) es soluci´on de (∗) y r es un cierto n´ umero real ﬁjo, entonces la sucesi´on (cn ) deﬁnida a trav´es de cn = r an para cada n tambi´en lo es.

As´ı que el conjunto de soluciones13 de (∗), no es cualquier cosa, sino que tiene estructura, en on, y tambi´en concreto la de espacio vectorial14 : la suma de soluciones sigue siendo soluci´ el producto de una soluci´ on por una constante. Esto tiene una consecuencia muy importante. Supongamos que (an ) y (bn ) son dos soluciones distintas (con m´as precisi´on, no deben ser una m´ ultiplo de la otra). Por simpliﬁcar 12 Un argumento m´ as formal ser´ıa el siguiente: si hubiera dos soluciones, el principio de inducci´ on fuerte nos permitir´ıa probar que ambas, en realidad, son la misma. 13 N´ otese que hay inﬁnitas soluciones de la ecuaci´ on. 14 El lector avisado sabr´ a identiﬁcar los conceptos de base y dimensi´ on que aparecer´ an impl´ıcitamente en nuestros argumentos. Si adem´ as est´ a versado en la teor´ıa de resoluci´ on de ecuaciones diferenciales, muchas de las t´ecnicas que aqu´ı aparecer´ an le resultar´ an familiares.

(versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

413

pr eli m in ar

el argumento, supongamos que son (an ) = (0, 1, . . . ), la soluci´on que empieza con 0 y 1, y (bn ) = (1, 0, . . . ), que empieza con 1 y 0. Consideremos otra soluci´on cualquiera de la ecuaci´on (∗), digamos (cn ) = (c0 , c1 , c2 , . . . ). Formemos ahora la sucesi´on (dn ) deﬁnida mediante dn = c1 an + c0 bn , para cada n. Ya sabemos que (dn ) es soluci´on de la ecuaci´on. Pero, adem´as, sus dos primeros t´erminos coinciden con los de (cn ). As´ı que ambas sucesiones, (cn ) y (dn ), han de ser la misma. En conclusi´on, si encontramos dos soluciones “distintas” (linealmente independientes, en realidad), cualquier otra soluci´on de la ecuaci´on se puede escribir como combinaci´on lineal de ellas. Lo que nos falta es dise˜ nar un m´etodo para encontrar “buenas” soluciones “b´ asicas”. B. Forma de las soluciones

Quiz´as el lector se est´e preguntando, a estas alturas, por qu´e es necesario seguir con este an´alisis: ya hemos encontrado dos soluciones, las que empiezan, respectivamente, por (0, 1, . . . ) y por (1, 0, . . . ). Como han de veriﬁcar la ecuaci´on, los primeros t´erminos de estas sucesiones han de ser (an ) = (0, 1, α, α2 + β, α3 + 2αβ, α4 + 3α2 β + β 2 , . . . )

(bn ) = (1, 0, β, αβ, α2 β + β 2 , α3 β + 2αβ 2 , α4 β + 3α2 β 2 + β 3 , . . . )

Tambi´en sabemos que cualquier otra soluci´ on de la ecuaci´on se puede escribir como combinaci´on lineal de estas dos: su t´ermino general ser´a de la forma

Ve rs i´on

cn = Aan + Bcn ,

donde A y B son dos ciertas constantes (que en realidad quedar´an determinadas en cuanto nos den las condiciones iniciales). Pero el panorama no es muy alentador: ya tenemos una respuesta, pero no parece muy adecuada, pues no parece posible extraer de ella una f´ ormula cerrada y manejable del t´ermino general en funci´on de n. Quiz´as no estemos eligiendo bien las dos soluciones “especiales”. Recordemos que han de ser dos soluciones “distintas”, en el sentido de que una no sea un m´ ultiplo de la otra (en general, y ya pensando en ecuaciones de orden mayor, exigiremos que sean linealmente independientes). Podr´ıamos intentarlo, por ejemplo, con las sucesiones (1, 1, . . . ) y (1, −1, . . . ); el argumento funcionar´ıa de nuevo, pero no obtendr´ıamos una f´ ormula manejable. Buscamos soluciones con cierta estructura. Podr´ıamos intentar, por ejemplo, que los t´erminos de la soluci´on estuvieran en progresi´on aritm´etica. Es decir, empezamos con (a0 , a0 + d, . . . ), donde d est´a a nuestra disposici´on. El tercer t´ermino ser´ıa el dictado por la ecuaci´on: α(a0 + d) + βa0 y buscamos un valor de d para el que ese t´ermino sea el siguiente en la progresi´on, esto es, a0 + 2r. Enseguida nos damos cuenta de que no vamos por buen camino. As´ı que intentemos otra estructura que conocemos bien: que los t´erminos de la sucesi´on est´en en progresi´ on geom´etrica. Empezamos con (1, r, . . . ), a ver qu´e pasa. La sucesi´on es como sigue: (1, r, α r + β, α(αr + β) + β r, . . . ) (versi´ on preliminar 23 de diciembre de 2003)

414

Cap´ıtulo 6. Ecuaciones de recurrencia

Y vamos con el cuarto t´ermino:

pr eli m in ar

Ahora ajustamos r para que el tercer t´ermino est´e en progresi´on geom´etrica con los anteriores; esto es, r ha de cumplir que α r + β = r2 .

α(αr + β ) + β r = α r2 + β r = r(α r + β ) = r3 . =r2

=r2

¡Incre´ıble!, sale gratis. El mismo valor de r que nos permite ajustar el tercer t´ermino consigue hacerlo con el cuarto. El lector podr´a comprobar que lo mismo ocurre para los siguientes. As´ı que existe una soluci´ on de la ecuaci´on de la forma an = rn (recu´erdese que esto ya ocurr´ıa en las ecuaciones de primer grado que hemos resuelto en la secci´on 6.1), una f´ ormula de lo m´as sencilla. Adem´as, la ecuaci´on de segundo grado que deﬁne el valor de r adecuado puede tener otra soluci´on, que nos permitir´ıa construir otra sucesi´on, tambi´en con t´erminos en progresi´on geom´etrica, con la que completar el an´alisis del problema. C. M´ etodo de resoluci´ on

Ya estamos en condiciones de resumir y formalizar estas ideas. Buscamos soluciones (an ) de la ecuaci´on (∗) cuyos t´erminos est´en en progresi´ on geom´etrica; es decir, que sean de la n umero no nulo que determinaremos forma an = r , para todo n ≥ 0, donde r es un cierto n´ en un momento. El que sea soluci´ on exige que

Ve rs i´on

rn = α rn−1 + β rn−2

para cada n ≥ 2.

Pero estas inﬁnitas condiciones se resumen, en realidad, dividiendo por rn−2 , en una sola, r2 = α r + β

(el lector que haya estudiado el ejemplo 6.1.7 encontrar´a familiar este argumento). A la ecuaci´on algebraica as´ı obtenida se le llama ecuaci´ on caracter´ıstica. El an´ alisis depender´a de qu´e tipo de soluciones tenga esta ecuaci´on de segundo grado. Caso 1. La ecuaci´ on caracter´ıstica tiene dos ra´ıces reales distintas

Llamemos r1 y r2 a estas dos ra´ıces. Sabemos que las sucesiones deﬁnidas por an = r1n y bn = r2n son soluciones de (∗). Son adem´as, distintas (linealmente independientes), porque r1 = r2 . As´ı que cualquier otra soluci´on se escribir´a como combinaci´on lineal de ellas. Es decir, podemos escribir la soluci´on general de (∗) como n A r1 + B r2n

donde A y B son dos constantes cualesquiera. Si ahora buscamos la (´ unica) soluci´on que veriﬁca dos ciertas condiciones iniciales, bastar´ a con determinar los valores de A y B adecuados, mediante sencillas relaciones algebraicas. Lo vemos en un ejemplo. (versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

415

Ejemplo 6.2.1 Consideremos la sucesi´ on de n´ umeros de Fibonacci, Fn , dada por F0 = 0, F1 = 1 y Fn = Fn−1 + Fn−2 para cada n ≥ 2.

A

pr eli m in ar

La ecuaci´on caracter´ ıstica correspondiente es r2 − r − 1 = 0, cuyas soluciones son, como ya √ √ 1+ 5 1− 5 vimos, r1 = 2 y r2 = 2 ; as´ı que la soluci´on general de la ecuaci´on de Fibonacci es √ √ 1− 5 n 1+ 5 n +B . 2 2

En esta f´ormula tenemos codiﬁcadas todas las soluciones de la ecuaci´on de Fibonacci. Queda determinar los valores de A y B que corresponden a la sucesi´on que nos incumbe, la que tiene como valores iniciales 0 y 1. S´ olo hay que escribir los casos n = 0 y n = 1 de la f´ormula y resolver el sistema de ecuaciones correspondiente:   0 = F0 = A + B  1 1 √ √ =⇒ A = √ y B = −√ .  1+ 5 1− 5 5 5  +B 1 = F1 = A 2 2 Y la f´ormula para el n-´esimo n´ umero de Fibonacci resulta ser 1 Fn = √ 5

√ √ 1 1+ 5 n 1− 5 n −√ 2 2 5

Ve rs i´on

la llamada f´ ormula de Binet, de 1843 (aunque Daniel Bernoulli y Euler ya la conoc´ıan hacia 1724). Pasan cinco siglos desde que Fibonacci se interesara por estos n´ umeros hasta que se obtiene esta expresi´on. Nada menos que cinco siglos separan las simples manipulaciones con la ecuaci´on del nivel de abstracci´on que supone el an´alisis que aqu´ı hemos hecho y que nos ha conducido a esta f´ ormula. F´ormula, por cierto, algo sorprendente; obs´ervese que los distintos t´erminos, que involucran ra´ıces de 5, se combinan m´agicamente para dar siempre un entero. Quiz´as no sea as bien hace la manera m´as eﬁcaz de calcular el valor de un cierto Fn , pero descubre, o m´ expl´ıcita, la relaci´on entre estos n´ umeros de Fibonacci y τ , la raz´on ´aurea, relaci´on sobre la que profundizaremos m´as adelante. ♣ Caso 2. La ecuaci´ on caracter´ıstica tiene una ra´ız real doble ´nica ra´ız (doble), r1 , s´olo si los La ecuaci´on caracter´ıstica r2 − αr − β = 0 tiene una u coeﬁcientes α y β son muy especiales. En concreto, con la ayuda de la f´ormula cuadr´atica (el radicando α2 + 4β ha de ser 0), obtenemos que tienen que ser de la forma α = 2r1 y β = −r12 . La ecuaci´on de recurrencia con la que estamos es, pues, an = 2r1 an−1 − r12 an−2 ,

para cada n ≥ 2.

Sabemos que (an ) = (1, r1 , r12 , r13 , . . . ) es una soluci´on de la ecuaci´on, pero falta otra. No queremos que sea un m´ ultiplo de ´esta, y parece razonable suponer que ha de depender de r1 . (versi´ on preliminar 23 de diciembre de 2003)

416

Cap´ıtulo 6. Ecuaciones de recurrencia

Podr´ıamos intentarlo con la sucesi´on (bn ), que empieza con (0, r1 , . . . ) y que cumple las condiciones requeridas. Miremos el aspecto de sus primeros t´erminos:

pr eli m in ar

b2 = 2r1 b1 − r12 b0 = 2r12 ,

b3 = 2r1 b2 − r12 b1 = 4r13 − r13 = 3r13 ,

b4 = 2r1 b3 − r12 b2 = 6r14 − 2r14 = 4r14 .

De lo m´as atractivo; y sorprendente: las sucesivas cancelaciones hacen que los t´erminos de la ormula sencilla y manejable. sucesi´on sean de la forma nr1n , para cada n ≥ 0, de nuevo una f´ El lector puede comprobar m´as formalmente que, efectivamente, si r1 es una ra´ız doble de la ecuaci´on caracter´ıstica, entonces la sucesi´on dada por bn = n r1n para cada n es una soluci´ on de la ecuaci´on de recurrencia. As´ı que la soluci´on general se puede escribir como

A r1n + B n r1n

De nuevo, los valores de A y B se determinar´an con las condiciones iniciales.

Por supuesto, hab´ıa una raz´ on, adem´as de las heur´ısticas que hemos expuesto aqu´ı, para elegir la forma particular de esta segunda soluci´on (v´ease el ejercicio 6.2.2). No hay tal Deus ex machina, al que a veces somos tan aﬁcionados en los textos de Matem´aticas. Ejemplo 6.2.2 La ruina del jugador, revisada.

Ve rs i´on

En el ejemplo 6.1.9 d´ abamos los ingredientes del problema: empezamos a jugar con n euros, donde 0 ≤ n ≤ N , para cierto N ﬁjo. En cada partida ganamos con probabilidad p, y perdemos con probabilidad q = 1 − p. Si a(n) es la probabilidad de arruinarnos, entonces a(n + 2) =

q 1 a(n + 1) − a(n) , p p

si 0 ≤ n ≤ N − 2.

Las condiciones “iniciales”, un tanto inusuales, son a(0) = 1 y a(N ) = 0. La ecuaci´on caracter´ıstica es, en este caso, q 1 r2 − r + = 0, p p cuyas soluciones son r1 = q/p y r2 = 1. Llamemos, por comodidad, δ al cociente q/p. Hay dos casos, dependiendo de si δ = 1 o no.

Caso p = q (es decir, δ = 1). Estamos ante un juego en el que, en cada partida, la probabilidad de ganar no es la misma que la de perder. Si estuvi´eramos hablando de una moneda, dir´ıamos que est´a “cargada”. Cuando jugamos a la ruleta, apostando al rojo o al negro, estamos en este caso, como luego explicaremos (de hecho, en el caso en que p < q, como el lector se habr´a imaginado ya). Como las ra´ıces de la ecuaci´on caracter´ıstica son distintas, la soluci´on general ser´a a(n) = A 1n + B δ n . (versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

417

con lo que la soluci´on es a(n) = −

y B=

1 , 1 − δN

pr eli m in ar

Y, con las condiciones iniciales, determinamos A y B:  a(0) = A + B = 1  δN =⇒ A = − 1 − δN a(N ) = A + B δ N = 0 

δN 1 + δn , N 1−δ 1 − δN

(donde, recordemos, δ = q/p).

Caso p = q = 1/2 Ahora hay una u ´nica ra´ız de la ecuaci´on caracter´ıstica, r1 = r2 = 1, y la soluci´on general se puede escribir como a(n) = A 1n + B n 1n = A + Bn.

De las condiciones iniciales obtenemos que A = 1 y B = −1/N , con lo que a(n) = 1 −

n . N

Ve rs i´on

El comportamiento de las dos soluciones es bien diferente: en el caso p = q, es una funci´on lineal de n, mientras que en el otro es una funci´ on exponencial. Para medir realmente qu´e supone esto, supongamos que estamos en un casino europeo apostando al rojo: de los 36 n´ umeros, hay 18 rojos y otros 18 negros. Pero hay tambi´en una casilla, la del 0, que no lleva color; si sale el 0, la banca se lleva todas las apuestas. Parece poco negocio para el casino, pero analic´emoslo con cuidado. La probabilidad de ganar es p = 18/37, mientras que la de perder es q = 19/37, ligeramente superior, debido a la presencia de esta casilla extra con el 0. El cociente δ = q/p vale 1,0555. Pr´acticamente 1, pero no exactamente 1. Las gr´aﬁcas que aparecen a continuaci´on comparan los valores de a(n) en el rango 0 ≤ n ≤ N con δ = 1 y δ = 1,0555. Con δ = 1, claro, tenemos una recta. La de la izquierda corresponde a N = 40, y ya se aprecia una cierta diferencia. La de la derecha es para N = 200, y la discrepancia es ya espectacular. 1

1

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0

10

20 n

30

40

0

20

40

60

80 100 120 140 160 180 200 n

Obs´ervese que en la gr´aﬁca de la derecha, la probabilidad de arruinarse es pr´ acticamente 1 (en el caso δ = 1, 0555) a menos que n est´e muy, pero que muy cercano a N = 200. Digamos que (versi´ on preliminar 23 de diciembre de 2003)

418

Cap´ıtulo 6. Ecuaciones de recurrencia

pr eli m in ar

estamos jugando a “doblar o arruinarse” (N = 2n). Si el juego es equilibrado, la probabilidad de arruinarse es siempre un 1/2, sea cual sea N . Pero en la ruleta, para N = 40 tenemos una probabilidad de ruina de casi el 70 %. . . y si estamos con N = 200, nos arruinaremos en m´ as del 98 % de las ocasiones. Las conclusiones quedan para el lector. ♣ Caso 3. La ecuaci´ on caracter´ıstica tiene dos ra´ıces complejas

La ecuaci´on caracter´ıstica tiene coeﬁcientes reales, as´ı que sabemos15 que las dos ra´ıces complejas son conjugadas una de la otra. Digamos que son z1 = a + bi y z2 = z 1 = a − bi. El lector puede comprobar que las sucesiones (an ) y (bn ) deﬁnidas, para cada n, mediante an = z1n y bn = z2n respectivamente, son soluciones de la ecuaci´on de recurrencia, as´ı que su soluci´on general se puede escribir como A z1n + B z2n = A z1n + B z n1 , donde A y B son dos par´ametros que, como siempre, se determinar´an con las condiciones iniciales. Pero todo en este problema, los coeﬁcientes de la ecuaci´on y los propios t´erminos de la sucesi´on, son n´ umeros reales. Y obtenemos una soluci´on escrita en t´erminos de n´ umeros complejos. Pese a la advertencia de Hadamard (v´ease la p´agina 36), puede que esto no nos deje muy satisfechos (y eso que, aceptando esta escritura en complejos, ¡la f´ormula que se obtiene es de lo m´as manejable!)

Ve rs i´on

As´ı que nos ponemos a pensar si podemos encontrar otro par de soluciones, que cumplan las condiciones habituales, y cuyos t´erminos sean n´ umeros reales (y, por supuesto, tales que la f´ormula que obtengamos siga siendo razonable). Nuestras soluciones especiales empiezan con y (bn ) = (1, z 1 , . . . ) . (an ) = (1, z1 , . . . )

¿Qu´e podemos hacer para conseguir, a partir de ´estas, otras dos sucesiones cuyos dos primeros t´erminos (de cada una) sean reales? Por supuesto16 , sumarlas y restarlas (con las constantes adecuadas). As´ı que deﬁnimos dos nuevas sucesiones (# an ) y (#bn ) mediante # an =

an + b n 2

y

#bn = an − bn 2i

(para cada n ≥ 0)

cuyos primeros t´erminos resultan ser 1 + 1 z + z 1 1 , , . . . = (1, Re(z1 ), . . . ) 2 2 1 − 1 z − z 1 1 , , . . . = (0, Im(z1 ), . . . ) = 2i 2i

# an = #bn 15

En el caso de la ecuaci´ on de segundo grado es obvio. Para ecuaciones de mayor grado, ya vimos el argumento en la demostraci´ on de la proposici´ on 4.45. 16 Si alg´ un lector no est´ a familiarizado con las cuestiones relacionadas con los n´ umeros complejos, puede consultar el ﬁnal de la secci´ on 1.1.

(versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

419

pr eli m in ar

Y la mitad del trabajo est´ a hecho: los t´erminos de las dos soluciones son todos reales. Pero la cosa es todav´ıa m´as sorprendente: los siguientes t´erminos se pueden describir de manera sencilla. Como en ellos est´an involucradas potencias de z1 y z 1 , conviene que escribamos las ra´ıces en su forma polar: z1 = |z1 |eiθ y z2 = z 1 = |z1 | e−iθ , donde θ = arg(z1 ). Tienen el mismo m´odulo y argumento θ de signo contrario, pues son complejas conjugadas. Y ahora, la casi m´agica f´ ormula de Euler-De Moivre, que nos dice que las potencias se escriben de manera muy sencilla: z1n = (|z1 | eiθ )n = |z1 |n einθ

y

z2n = (|z1 | e−iθ )n = |z1 |n e−inθ

De manera que los t´erminos generales de las nuevas sucesiones son, simplemente, # an = #bn =

z1n + z n1 einθ + e−inθ = |z1 |n = |z1 |n cos(nθ) , 2 2 z1n − z n1 einθ − e−inθ = |z1 |n = |z1 |n sin(nθ) . 2i 2i

Perfecto: todos los t´erminos son reales, y la f´ormula es sencilla. Decidimos entonces emplear, para describir la soluci´on general de la ecuaci´on, la expresi´on

∞ A |z1 |n cos(nθ) + B |z1 |n sen(nθ)

n=0

Ve rs i´on

donde, recordemos, θ = arg(z1 ).

Ejemplo 6.2.3 Queremos encontrar la sucesi´ on de n´ umeros (an ) definidos por an = 2 an−1 − 2 an−2 ,

para cada n ≥ 2,

junto con las condiciones iniciales a0 = 1 y a1 = 1. Con la ecuaci´on caracter´ıstica podemos obtener las ra´ıces z1 y z2 : r2 − 2r + 2 = 0

=⇒

z1 = 1 + i y z2 = z 1 = 1 − i .

Ser´ıa l´ıcito, desde luego, escribir la soluci´on general de la ecuaci´on como ∞ A (1 + i)n + B (1 − i)n . n=0

Pero es mejor utilizar la expresi´on alternativa. Observemos que el m´odulo y el argumento del n´ umero complejo z1 = 1 + i son, respectivamente, |z1 | =

√ 2

y

arg(z1 ) =

π . 4

As´ı que podemos escribir la soluci´on general como π π ∞ A 2n/2 cos n + B 2n/2 sen n . 4 4 n=0 (versi´ on preliminar 23 de diciembre de 2003)

420

Cap´ıtulo 6. Ecuaciones de recurrencia

pr eli m in ar

Con las condiciones iniciales determinamos que A = 1 y que B = 0, as´ı que la respuesta buscada es, para cada n ≥ 0, π n . an = 2n/2 cos 4 Compru´ebese que, a pesar de escribirse de esta forma algo extravagante, los t´erminos de la sucesi´on son todos enteros. ♣ Todos los argumentos que hemos desarrollado hasta aqu´ı para el caso de la ecuaci´on de segundo grado se aplican, mutatis mutandis, a las ecuaciones lineales, homog´eneas y con coeﬁcientes constantes de grado k. Dejamos al lector que reconstruya la teor´ıa para el caso general, y nos limitamos a exponer el resultado b´ asico, as´ı como a ilustrarlo con un ejemplo. Teorema 6.1 Dado k ≥ 1, la soluci´ on general de la ecuaci´ on

an = A1 an−1 + A2 an−2 + · · · + Ak an−k se puede escribir de la forma

{P1 (n) r1n + P2 (n) r2n + · · · + Ps (n) rsn },

on caracter´ıstica donde r1 , r2 , . . . , rs son las ra´ıces distintas (reales o complejas) de la ecuaci´ rk = A1 rk−1 + A2 rk−2 + · · · + Ak−1 r + Ak

Ve rs i´on

y cada Pi (n) es un polinomio gen´erico (con coeficientes arbitrarios) de grado igual a la multiplicidad de la correspondiente ra´ız ri menos uno. Ejemplo 6.2.4 Consideremos la ecuaci´ on an = 4an−1 −6an−2 +6an−3 −5an−4 +2an−5 , para cada n ≥ 5, junto con las condiciones iniciales a(0) = a(1) = a(2) = a(3) = 0 y a(4) = 1. Se trata de una ecuaci´on de recurrencias de grado 5. La ecuaci´on caracter´ıstica correspondiente es la qu´ıntica r5 = 4r4 − 6r3 + 6r2 − 5r + 2 ,

cuyas ra´ıces son 2, 1 (ra´ız doble), i y −i (dos ra´ıces complejas conjugadas, como debe ser). As´ı que, conforme al teorema anterior, la soluci´on general de la ecuaci´on de recurrencia se puede escribir como ∞ . (A1 + A2 n)1n + A3 2n + A4 in + A5 (−i)n n=0

O, si queremos evitar la presencia de n´ umeros complejos, como π π ∞ (A1 + A2 n)1n + A3 2n + A4 1n cos n + A5 1n sin n . 2 2 n=0 Si ahora imponemos las cinco condiciones iniciales, determinaremos los valores de los n´ umeros A1 , . . . , A5 . Dejamos al lector la comprobaci´on (algo tediosa) de que la soluci´on del problema es la sucesi´on dada por 1 1 1 n 1 i [(−i)n − in ] para cada n ≥ 0. an = 2 − n + − + 5 2 10 20 (versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

421

o bien

pr eli m in ar

π π 1 n 1 1 1 n + sin n . an = − n + 2 − cos 2 5 5 2 10 2 Ambas f´ormulas, pese a su alambicada escritura, representan a la sucesi´on de n´ umeros (enteros) cuyos primeros t´erminos son (0, 0, 0, 0, 1, 4, 10, 22, 47, 98, 200, 404, 813, 1632, 3270, . . . )

6.2.2.

♣

Ecuaciones lineales, no homog´ eneas y con coeﬁcientes constantes

Consideramos ahora un caso m´as general, en el que la ecuaci´on contiene un t´ermino extra que depende del ´ındice n: an + B1 an−1 + B2 an−2 + · · · + Bk an−k = f (n) , donde f (n) es una cierta funci´on no nula.

De nuevo, y por simpliﬁcar, supongamos que nuestra ecuaci´on es de grado dos, (∗)

an + α an−1 + β an−2 = f (n)

para cada n ≥ 2.

Ve rs i´on

Tendremos, adem´as, dos condiciones iniciales, los valores de a0 y a1 . Centr´emonos en las soluciones de la ecuaci´on (∗). Observemos que ahora no tenemos la estupenda estructura de antes. Por ejemplo, si (an ) y (bn ) son dos soluciones de (∗), la sucesi´on suma (cn ) deﬁnida mediante cn = an + bn para cada n, ya no es soluci´on de (∗), como se comprueba f´acilmente: para cada n ≥ 2, cn + αcn−1 + βcn−2 = (an + bn ) + α(an−1 + bn−1 ) + β(an−2 + bn−2 ) = an + αan−1 + βan−2 + bn + αbn−1 + βbn−2 = f (n) + f (n) = 2f (n) .

As´ı que no obtenemos f (n), como se necesitar´ıa. Pero no todo est´a perdido. Lo que s´ı sigue ocurriendo es que la soluci´ on de la ecuaci´on (∗), junto con los dos valores iniciales, existe (basta arrancar la sucesi´on) y es u ´nica. De nuevo, los dos valores iniciales determinan completamente la soluci´on que nos interesa. Busquemos una forma adecuada de escribir la soluci´on general de la ecuaci´on (∗). Nos apoyaremos en lo que ya sabemos de las ecuaciones homog´eneas. Planteamos la asociada a nuestro problema: (∗∗)

an + α an−1 + β an−2 = 0 ,

para cada n ≥ 2.

De esta ecuaci´on sabemos c´omo calcular su soluci´on general, que ser´a de la forma (Aan +Bbn ), donde (an ) y (bn ) son sucesiones soluci´on de (∗∗) (con el aspecto que corresponda a cada caso, dependiendo de las ra´ıces de la ecuaci´on caracter´ıstica). Y ahora viene la observaci´on clave: consideramos una soluci´ on particular de la ecuaci´on (∗). Vale una cualquiera, por ejemplo la que obtenemos arrancando la sucesi´on a partir (versi´ on preliminar 23 de diciembre de 2003)

422

Cap´ıtulo 6. Ecuaciones de recurrencia

pr eli m in ar

de dos valores iniciales que ﬁjemos. Llamemos (cn ) a esta soluci´on. Lo que aﬁrmamos es que cualquier sucesi´on de la forma Aan + Bbn + cn , donde A y B son par´ametros, es soluci´ on de la ecuaci´on (∗). La comprobaci´on, mediante las correspondientes manipulaciones algebraicas, queda como ejercicio para el lector. Pero adem´as, toda soluci´on de (∗) se puede escribir como arriba. Es, una vez m´as, un argumento de unicidad: si (γn ) es una soluci´on que empieza por (γ0 , γ1 , . . . ), podemos encontrar A y B que determinen una sucesi´on que es soluci´on de (∗) y que empieza como (γn ). As´ı que han de ser la misma. El problema queda resuelto, excepto por un peque˜ no detalle que explicaremos luego. Si queremos encontrar la sucesi´on de n´ umeros (an ) que cumplen la ecuaci´on an + αan−1 + βan−2 = f (n) ,

para cada n ≥ 2,

junto con las condiciones iniciales a0 = p y a1 = q,

analizamos primero la ecuaci´on homog´enea asociada, an + αan−1 + βan−2 = 0. La soluci´ on general de esta ecuaci´on ser´a de la forma (Aan + Bbn ). Calculamos una soluci´ on particular de la ecuaci´on completa; digamos que es la sucesi´on (cn ).

Ve rs i´on

Ya tenemos la soluci´on general de la ecuaci´on completa, (Aan + Bbn + cn ). Y ahora (y no antes) imponemos las condiciones iniciales para determinar los n´ umeros A y B. Ejemplo 6.2.5 Encontrar la sucesi´ on de n´ umeros (an ) que satisface la ecuaci´ on de recurrencia an = an−1 + an−2 + 7, junto con las condiciones iniciales a0 = 0 y a1 = 1.

La ecuaci´on homog´enea asociada es la de Fibonacci, de la que conocemos bien la forma de la soluci´on (v´ease el ejemplo 6.2.1). Ahora nos damos cuenta (!) de que la sucesi´on cuyos t´erminos son todos iguales a −7 es soluci´on de la ecuaci´on. N´otese que nos referimos u ´nicamente a la ecuaci´on (los dos primeros valores de esta sucesi´on son, claro, −7 y −7). As´ı que la soluci´on general de la ecuaci´on completa se puede escribir como √ √ 1− 5 n 1+ 5 n +B − 7. A 2 2 Imponiendo los valores iniciales a0 = 1 y a1 = 1, y tras unos laboriosos c´alculos, determinamos los valores de A y B y concluimos que la soluci´on que buscamos viene dada por √ √ √ √ 7 9 5 7 9 5 1+ 5 n 1− 5 n + − + − 7, an = 2 10 2 2 10 2

para cada n ≥ 0.

♣

El detalle al que nos refer´ıamos es nuestra constante preocupaci´on por que la f´ ormula obtenida sea manejable. Desde luego, la expresi´on de la parte “homog´enea” de la soluci´on lo es, que para eso hicimos todo el esfuerzo antes. Pero, ¿c´omo obtener una soluci´ on particular (versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

423

pr eli m in ar

con una expresi´on sencilla?. Si, por ejemplo, la obtenemos partiendo de dos valores iniciales cualesquiera, es casi seguro que no la tenga. No existe un m´etodo general para obtener estas soluciones “agradables”, sino s´ olo reglas (casi trucos) ad hoc que se aplican cuando la funci´on f (n) tiene una forma espec´ıﬁca. Queda siempre tambi´en, claro, el m´etodo de prueba y error. Lo vemos en un ejemplo, en el que tambi´en advertiremos las posibles diﬁcultades del m´etodo, que se denomina m´ etodo de los coeficientes indeterminados. Se trata, esencialmente, de buscar soluciones particulares dentro de la misma “familia” de funciones a la que pertenezca f (n) (obs´ervese que, en el ejemplo anterior, la soluci´ on particular era una constante, como el t´ermino no homog´eneo). Digamos que estamos con la ecuaci´on an − an−1 − an−2 = 3n .

S´olo estamos interesados en encontrar una soluci´on particular, el resto del trabajo (soluci´ on general de la homog´enea, condiciones iniciales) ya lo sabemos hacer. Buscamos soluciones de la forma # an = C3n , donde C es una constante que est´a a nuestra disposici´on, y que determinamos con la propia ecuaci´on: an−1 − # an−2 = 3n # an − #

=⇒

C3n − C3n−1 − C3n−2 = 3n

=⇒

9C − 3C − C = 9 ,

de donde obtenemos que C = 9/5. Y, efectivamente, # an = 95 3n es una soluci´ on particular de la ecuaci´on, como puede comprobar el lector.

Ve rs i´on

Pero ahora imaginemos que la ecuaci´on es an − an−1 − an−2 = τ n ,

donde τ es la raz´on ´aurea. Probamos, como antes, con una soluci´on del tipo # an = Cτ n : # an − # an−1 − # an−2 = τ n =⇒ Cτ n − Cτ n−1 − Cτ n−2 = τ n =⇒ C(τ 2 − τ − 1) = τ 2 .

Y no hay manera de determinar C, porque τ 2 − τ − 1 = 0. El m´etodo no funciona, no puede funcionar, porque τ n es ya soluci´ on de la ecuaci´on homog´enea (τ era una de las ra´ıces de la ecuaci´on caracter´ıstica), as´ı que no puede ser soluci´on de la completa. Inspir´andonos en alg´ un argumento que hicimos anteriormente, podr´ıamos intentar con soluciones de la forma # an = C n τ n : # an − # an−1 − # an−2 = τ n =⇒ Cnτ n − C(n − 1)τ n−1 − C(n − 2)τ n−2 = τ n =⇒ Cn(τ − τ − 1) + C(2 + τ ) = τ 2

2

√ 5+ 5 τ2 = . =⇒ C = 2+τ 10

Y ya tendr´ıamos determinado el valor de C y, por tanto, una soluci´ on particular. Las ideas de este m´etodo se pueden aplicar tambi´en a ecuaciones en las que el t´ermino no homog´eneo sea un polinomio o una funci´ on seno o coseno. Como las funciones generatrices nos permitir´an resolver todos estos casos (v´ease la secci´on 10.4), no entraremos en m´as detalles. (versi´ on preliminar 23 de diciembre de 2003)

424

6.2.3.

Cap´ıtulo 6. Ecuaciones de recurrencia

Sistemas de ecuaciones de recurrencia

pr eli m in ar

Consideremos un sistema de dos ecuaciones de recurrencia lineales (de grado uno), homog´eneas y con coeﬁcientes constantes: an = α1,1 an−1 + α1,2 bn−1 , bn = α2,1 an−1 + α2,2 bn−1 , v´alido para cada n ≥ 1, donde los αij son ciertos n´ umeros reales; adem´as tendremos unas condiciones iniciales a0 = p y b0 = q. Es muy conveniente escribir este sistema en forma matricial: α1,1 α1,2 an−1 an = para n ≥ 1, bn α2,1 α2,2 bn−1 A

transici´ on17

a la matriz A. Buscamos dos sucesiones (an ) y (bn ) Llamaremos matriz de que satisfagan las ecuaciones y las condiciones iniciales, que tambi´en se pueden escribir en estos t´erminos: p a0 . = q b0

Ve rs i´on

Los argumentos que expondremos a continuaci´on servir´an para sistemas con un n´ umero mayor de ecuaciones (y de sucesiones). Como la relaci´on de m´as arriba es v´ alida para todo n ≥ 1, podemos aplicarla reiteradamente, hasta llegar al vector de valores iniciales (de manera an´aloga a lo que hac´ıamos cuando se trataba de una u ´nica ecuaci´on de primer orden). En este lenguaje matricial, la iteraci´on de la regla se traduce, simplemente, en la multiplicaci´ on de matrices: 2 n α1,1 α1,2 an−1 α1,1 α1,2 an−2 α1,1 α1,2 a0 an = = =· · ·= . bn α2,1 α2,2 bn−1 α2,1 α2,2 bn−2 α2,1 α2,2 b0

Como conocemos los valores de a0 y b0 , todo el problema se reduce al de calcular la potencia n-esima de la matriz de transici´on A. ¿Es esto sencillo? La respuesta es casi obvia: depende (de c´omo sea la matriz A, claro). Veamos un par de ejemplos primero. Ejemplo 6.2.6 Supongamos que tenemos un sistema de ecuaciones an = 2 an−1 , bn = 3 bn−1 ,

v´ alido para n ≥ 1, junto con las condiciones iniciales a0 = b0 = 1. El sistema es muy especial: las dos ecuaciones est´an desacopladas (para resolver cada ecuaci´on no necesitamos la informaci´on de la otra). En este caso proceder´ıamos resolviendo cada una 17

El nombre viene sugerido por la siguiente interpretaci´ on: tenemos un cierto sistema descrito por los valores de las sucesiones an y bn en cada “tiempo” n. La matriz A nos dice c´ omo evoluciona el sistema de un instante de tiempo al siguiente, cu´ al es la transici´ on entre ambos estados.

(versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

425

pr eli m in ar

por su lado, para obtener el valor, en funci´on de n, de an y bn . Esta resoluci´on tan sencilla tiene que tener una traducci´ on en lenguaje matricial. En ´el, n 2 0 a0 an = . 0 3 bn b0 As´ı que hay que calcular la potencia n-´esima de una matriz diagonal. Es f´acil comprobar que n 2n 0 2 0 = . 0 3 0 3n As´ı que

an bn

=

2n 0 0 3n

a0 b0

=

2n a0 3n b0

=

2n 3n

,

lo que, le´ıdo componente a componente, es la soluci´on que obtendr´ıamos resolviendo cada ecuaci´on por separado. ♣ Ejemplo 6.2.7 Consideremos ahora el sistema an = 2 an−1 , bn = an−1 + 2 bn−1

para cada n ≥ 1, junto con las condiciones iniciales a0 = 1, b0 = 3.

Ve rs i´on

La soluci´on del problema, con los mismos argumentos de antes, viene dada (escrita en forma matricial) por n 2 0 1 an . = 1 2 3 bn As´ı que el problema se reduce a calcular la potencia de una matriz que no es diagonal, pero tiene una forma muy especial. No es muy dif´ıcil convencerse (calculando los primeros casos y luego utilizando inducci´ on de que n 2 0 2n 0 = , 1 2 n 2n−1 2n de manera que la soluci´on del problema es 2n an 2n 1 0 = = 3 n 2n−1 2n bn n 2n−1 + 3 × 2n Compru´ebese que efectivamente, las sucesiones an = 2n y bn = n 2n−1 + 3 × 2n veriﬁcan el sistema de ecuaciones y las condiciones iniciales. ♣ Hemos visto que hay dos casos especialmente sencillos: cuando la matriz es diagonal, λn 0 λ 0 n =⇒ A = , A= 0 µn 0 µ (versi´ on preliminar 23 de diciembre de 2003)

426

Cap´ıtulo 6. Ecuaciones de recurrencia

en cuyo caso

An =

λn 0 n−1 nλ λn

pr eli m in ar

o cuando la matriz es de la forma λ 0 , A= 1 λ

(como dec´ıamos antes, ambas aﬁrmaciones se pueden probar por inducci´on). En general, la matriz de transici´on A no ser´a tan sencilla. Pero hemos destacado estos dos casos porque son los que nos van a permitir resolver el caso general. Observemos que si pudi´eramos escribir la matriz A de la siguiente manera: λ 0 P −1 , A=P 0 µ para ciertos n´ umero λ y µ y para cierta matriz P (invertible), entonces el c´ alculo de An es inmediato. Veamos la potencia 2: $ %2 λ 0 λ 0 λ 0 P −1 = P P −1 P P −1 A2 = P 0 µ 0 µ 0 µ 2 λ 0 λ2 0 −1 = P P =P P −1 , 2 0 µ 0 µ

Ve rs i´on

donde hemos utilizado que P P −1 = I, la matriz identidad 2 × 2. Un argumento similar (o para ser m´as formales, una prueba por inducci´ on) nos permitir´ıa deducir que λn 0 n P −1 , A =P n 0 µ con lo que el problema se resolver´ıa efectuando este producto de tres matrices (recordemos que al ﬁnal habr´a que multiplicar tambi´en por el vector de condiciones iniciales). Lo mismo ocurrir´ıa si A se pudiera escribir como λ 0 λn 0 −1 n P , en cuyo caso tendr´ıamos que A = P A=P P −1 . n−1 n 1 λ nλ λ

´ Al lector que haya pasado por un curso de Algebra lineal b´ asica ya le estar´a resultando familiar el aspecto de estas matrices especiales. Gran parte del esfuerzo (y de los sudores) que se emplea en uno de esos cursos va dirigido al problema de la diagonalizaci´on o, en su caso, de la obtenci´on de formas can´onicas. Y una de sus mejores aplicaciones la encontramos, precisamente, en el c´ alculo de la potencia de una matriz. El resultado b´ asico sobre estas cuestiones, el teorema de las formas can´ onicas de Jordan, nos dice que, dada una matriz A de dimensi´on 2, entonces o bien podemos encontrar una matriz P (invertible) de manera que A se puede escribir como λ 0 P −1 , A=P 0 µ (versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

427

pr eli m in ar

para ciertos n´ umeros λ y µ (los autovalores de la matriz), o bien podemos encontrar una matriz Q (tambi´en invertible) de manera que λ 0 Q−1 , A=Q 1 λ para cierto n´ umero λ (que ser´ıa un autovalor doble, en este caso). Las matrices P ´o Q se ´ calculan a partir de los autovectores asociados a los autovalores. Estas dos son las llamadas 18 formas can´onicas de Jordan . Como todo esto forma parte del folklore habitual de los cursos ´ de Algebra lineal, no entraremos en los detalles19 , y nos limitaremos a ver algunos ejemplos, en los que supondremos cierto manejo con estos conceptos. Ejemplo 6.2.8 Una reacci´ on en cadena: tenemos un cierto medio, con ´ atomos de un cierto elemento. Lanzamos contra ellos dos tipos de part´ıculas, A y B. Cuando una part´ıcula A choca con un ´ atomo, ´este se desintegra, dando lugar a 2 del tipo A y a 3 del tipo B; si es una part´ıcula B la que choca con el ´ atomo, entonces se producen 1 de A y 4 de B. Al comienzo hay dos de tipo A y una de tipo B. Interesa el n´ umero de part´ıculas de cada clase tras n unidades de tiempo. umero de part´ıculas de tipo A y B, respectivamente, tras n unidades Llamemos an y bn al n´ de tiempo. Los procesos de desintegraci´on se traducen en el sistema de recurrencias an = 2 an−1 + bn−1 , bn = 3 an−1 + 4 bn−1 ,

Ve rs i´on

para cada n ≥ 1, mientras que la condici´ on inicial es a0 = 2 y b0 = 1. Escrito en forma matricial, 2 1 an−1 an = , 3 4 bn bn−1 M

para cada n ≥ 1. Con lo visto anteriormente, la soluci´ on ser´a n 2 1 2 an , = 3 4 1 bn as´ı que s´olo resta calcular la potencia n de la matriz M . Ser´a necesario diagonalizarla. Empecemos calculando sus autovalores, las soluciones de la ecuaci´on 2−λ 1 = 0, det 3 4−λ 18 En realidad, estamos obviando algunas sutilezas, porque lo anteriormente expuesto es cierto si permitimos que λ y µ sean n´ umeros complejos. Si no son reales, hay otras formas can´ onicas que nos permiten escribir la matriz en t´erminos reales, pero no entraremos en los detalles. 19 Para aqu´ellos familiarizados con estas cuestiones: en el caso de que la forma can´ onica sea diagonal, sus entradas son los autovalores de A, mientras que P es la matriz que cambia a una base en la que la transformaci´ on lineal descrita por la matriz A es, simplemente, un cambio de escala en las dos direcciones.

(versi´ on preliminar 23 de diciembre de 2003)

428

Cap´ıtulo 6. Ecuaciones de recurrencia

pr eli m in ar

que resultan ser λ1 = 1 y λ2 = 5. Ahora, el subespacio asociado al autovalor λ1 viene dado por el n´ ucleo de la aplicaci´on representada por la matriz M − λ1 I, esto es, por la soluci´on del sistema 0 x 1 1 . = 0 y 3 3 Resolviendo este sistema, podemos tomar como autovector asociado al autovalor λ1 = 1 ucleo de a v1 = (1, −1). El subespacio asociado al autovalor λ2 = 5 viene dado por el n´ M − λ2 I, y si procedemos de manera an´aloga, obtenemos un posible autovector, v2 = (1, 3) para este autovalor. Ya tenemos la matriz P de cambio de base, 1 3 −1 1 1 −1 . , cuya inversa es P = P = 4 1 1 −1 3 De esta manera,

1 0 0 5

M =P

P −1 .

Calcular entonces M n ya no representa diﬁcultad alguna: 1 1 1n 0 1 1 3 + 5n 3 −1 −1 + 5n n = M = . 4 4 −1 3 1 1 0 5n −3 + 3 × 5n 1 + 3 × 5n

Ve rs i´on

Y la soluci´on del problema ser´a 1 1 3 + 5n 5 + 3 × 5n 2 −1 + 5n an = = . 4 4 1 bn −3 + 3 × 5n 1 + 3 × 5n −5 + 9 × 5n Es decir, que

1 1 (5 + 3 × 5n ) y bn = (−5 + 9 × 5n ) 4 4 nos proporcionan el n´ umero de part´ıculas de tipos A y B que hay en cada instante de tiempo n, n ≥ 0. Podemos listar los primeros casos: an =

5

···

tiempo

0

1

2

3

4

Tipo A

2

5

20

95

470

Tipo B

1 10 55 280 1405 7030 · · ·

2345 · · ·

Ambas poblaciones crecen muy r´ apidamente, como corresponde al car´ acter exponencial de las soluciones. Y es claro (la propia din´ amica del sistema lo suger´ıa) que va a haber m´ as part´ıculas del tipo B que del tipo A. Pero podr´ıa interesarnos saber cu´al es la raz´on entre las dos poblaciones, si se aproxima a un l´ımite ﬁnito o no. Mirando a las expresiones de an y bn , observamos que, para n muy grande, an ∼

3 n 5 , 4

bn ∼

9 n 5 , 4

(versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

429

por lo que la raz´ on entre las poblaciones se aproxima (y bastante r´ apidamente) a una proporci´on 1:3 (¡esto ya no era tan obvio con s´ olo mirar las recurrencias!). ♣

Veamos un ejemplo:

pr eli m in ar

En la secci´on 10.4 aprenderemos a resolver sistemas de ecuaciones de recurrencia con otras herramientas (funciones generatrices); un enfoque quiz´ as m´as eﬁciente, porque, en principio, permite abordar sistemas de ecuaciones de ´ordenes mayores que uno. En el caso de dimensi´ on 2, la forma de Jordan que no es diagonal aparece cuando la matriz A tiene un autovalor doble λ, y el n´ ucleo de A − λ I s´olo tiene dimensi´on 1 (s´olo hay un autovector asociado). Si nos vamos a matrices de dimensi´ on d, la descripci´on se complica un poco: la forma de la matriz can´onica de Jordan asociada a la matriz original depender´ a de la multiplicidad de los autovalores y del n´ umero de autovectores que tenga asociado cada uno de ellos. Pero, esencialmente, es una matriz diagonal por cajas, donde cada una de las cajas es de la forma   λ 0 0 ··· 0 0    1 λ 0 ··· 0 0     0 1 λ ··· 0 0      . . . . . . ... ...   .. .. ..      0 0 0 ··· λ 0  0 0 0 ··· 1 λ

Ve rs i´on

Ejemplo 6.2.9 Consideremos el siguiente sistema de ecuaciones de recurrencia de primer orden:    an = 2 an−1 + bn−1 + cn−1 bn = 3 bn−1   cn = bn−1 + 3 cn−1 para cada n ≥ 1, junto con las condiciones iniciales a0 = 1, b0 = 3, c0 = 2. La matriz de transici´on del sistema es

 2 1 1   A= 0 3 0 , 0 1 3 

as´ı que la soluci´on del sistema viene dada por  n     an 2 1 1 1        bn  =  0 3 0   3  0 1 3 2 cn Es f´acil ver que los autovalores de A (las soluciones de det(A − λ I) = 0) son los n´ umeros 2 y 3 (´este, un autovalor doble). Para el autovalor simple, λ = 2, el c´alculo del n´ ucleo de A − 2 I nos dice que podemos tomar como autovector asociado a v1 = (1, 0, 0). (versi´ on preliminar 23 de diciembre de 2003)

430

Cap´ıtulo 6. Ecuaciones de recurrencia

pr eli m in ar

Pero el subespacio asociado al autovalor 3 s´ olo tiene dimensi´on 1. Concretamente, el n´ ucleo de A−3 I est´a generado por el vector (1, 0, 1). La matriz can´onica no va a ser diagonal, as´ı que tendremos que recurrir a un sustituto. Calculamos el n´ ucleo de la matriz (A − 3 I)2 , que resulta estar generado por los vectores (1, 0, 1) y (0, 1, 0). Tomamos ahora un vector que est´e en el n´ ucleo de (A − 3 I)2 pero no en el de A − 3 I; v2 = (1, 1, 1) podr´ıa valer. Y ahora calculamos   1   v3t = (A − 3 I) v2t =  0  1 Los tres vectores que hemos obtenido forman (al ponerlos como columnas) la matriz P , que mostramos a continuaci´on, junto con su inversa P −1 :     1 0 −1 1 1 1     P −1 =  0 1 P = 0 1 0 , 0  0 −1 1 0 1 1 de manera que

 2 0 0   A = P  0 3 0  P −1 0 1 3 

Ve rs i´on

El c´alculo de An es ahora ya muy sencillo:     2n 2n n 3n−1 3n − 2n 0 0   −1   An = P  0  3n 0 P = 0 3n 0 n−1 n n−1 n 0 n3 0 n3 3 3

Y la soluci´on del sistema se obtiene, ﬁnalmente, multiplicando por el vector de condiciones iniciales:      n n  an 1  an = −2 + (n + 2) 3    n  n+1  bn  = A  3  =⇒ bn = 3   ♣ 2 cn cn = (n + 2) 3n EJERCICIOS.

6.2.1 Consideramos la ecuaci´ on de recurrencia xn = α xn−1 + β, para cada n ≥ 1, junto con el valor inicial x0 . Compr´ uebese que (a) si β = 0, entonces xn = αn x0 para cada n ≥ 0; (b) si α = 1, entonces xn = n β + x0 para cada n ≥ 0; (c) si α = 1, entonces n

xn = α x0 + β

αn − 1 α−1

,

para cada n ≥ 0.

(versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

431

Sugerencia. Aplicar reiteradamente la ecuaci´ on. Para c) se puede hacer un “cambio de variables”: considerar x ˜n = xn + t, con un t apropiado de manera que se reduzca al caso a).

pr eli m in ar

6.2.2 Estamos con la ecuaci´ on an = αan−1 + β an−2 , para cada n ≥ 2, junto con las condiciones iniciales a0 y a1 . Suponemos que r y s son las dos ra´ıces (reales y distintas) de la ecuaci´ on caracter´ıstica asociada. Comprobar que la soluci´ on de la ecuaci´ on de recurrencias (y las condiciones iniciales) se puede escribir como rn − sn (a1 − a0 s) + a0 sn . r−s Ahora suponemos que r y s se hacen cada vez m´ as pr´ oximas (en el l´ımite, estaremos en el caso de una ra´ız doble de la ecuaci´ on caracter´ıstica). Comprobar, quiz´ as apelando a la noci´ on de derivada, que la soluci´ on en el caso de ra´ız doble se puede escribir como combinaci´ on lineal de sn y nsn . 6.2.3 (a) Hallar una f´ ormula para los n´ umeros un que verifican: u0 = a, u1 = b y un+2 = un + n para cada n ≥ 1. (b) Un triple lineal es una lista de 3 n´ umeros naturales a, b, c, ordenados, a < b < c, y tales que umero de triples lineales formados con n´ umeros comprendidos entre 1 y n. c − b = b − a. Sea Tn el n´ Probar que T2n+1 = T2n + n y obtener una recurrencia an´ aloga para T2n . Hallar una f´ ormula para Tn .

Ve rs i´on

Sugerencia. Para el primer apartado, distinguir entre los un de ´ındice par y los de ´ındice impar y resolver los problemas (que son ahora de primer orden) por separado. Para el segundo, distinguir entre los triples cuyo u ´ltimo elemento sea el mayor (2n + 1 en el caso impar, 2n en el par) y los que no. Reunir los resultados para obtener la recurrencia de los Tn . Para resolverla, observar que si la aplicamos dos veces, obtenemos el problema del apartado (a). Soluci´ on. (a) (b)

u2n = n(n − 1) + a, T2n

u2n+1 = (n − 1)(n + 1) + b ,

n−1 T2n+1 = T2n + n =⇒ Tn = Tn−1 + 2 = T2n−1 + (n − 1)

=⇒

n+1 Tn = 2

n−2 2

6.2.4 Resolver las recurrencias: (a) an+3 = 4an+2 − 5an+1 + 2an , n ≥ 0 con condiciones iniciales a0 = a1 = 0 y a2 = 1. (b) an+3 = 3an+2 − 3an+1 + an , n ≥ 0 con condiciones iniciales a0 = a1 = 0 y a2 = 1. Soluci´ on. (a) an = −1 − n + 2n

(b) an = − n2 +

n2 2

6.2.5 Resolver la recurrencia: an+2 = 2an+1 + 2an + n, n ≥ 0 con condiciones iniciales a0 = 0 y a1 = 2. Sugerencia. Observar que la ecuaci´ on es lineal de segundo orden, pero es una ecuaci´ on no homog´enea, tiene un t´ermino extra que no depende de los t´erminos de la sucesi´ on. La teor´ıa nos dice en este caso que la soluci´on general se escribe como suma de la soluci´on general de la ecuaci´ on homog´enea (an+2 − 2an+1 − 2an = 0) m´ as una soluci´ on particular de la ecuaci´ on completa. Para buscar ´esta u ´ltima y teniendo en cuenta la forma particular de la no homogeneidad, probar con (p) an = A1 + nA2 .

(versi´ on preliminar 23 de diciembre de 2003)

432

Cap´ıtulo 6. Ecuaciones de recurrencia (h)

(p)

Soluci´ on. an = an + an = A(1 +

√

3)n + B(1 −

√

3)n −

√ n C.I. 7 3 = 3 2 (1

+

√ n 3) −

√ 7 3 2 (1 −

√ n 3) −

n 3

pr eli m in ar

6.2.6 Supongamos que estamos en un juego en el que la probabilidad de ganar una partida particular, p, es 0,49. Si empezamos con 50 fichas y nuestra estrategia es la de retirarnos s´ olo cuando hayamos doblado esa cantidad (o bien cuando nos hayamos arruinado, en que nos “retiran”). ¿Cu´ al ser´ a la probabilidad de arruinarnos: (a) si apostamos una ficha en cada partida? (b) ¿Y si las apuestas son de 10 fichas? (c) ¿Y si las apuestas son de 50 fichas? Sugerencia. En los dos u ´ltimos apartados, considerar a 10 y a 50, respectivamente, como nuevas unidades. Soluci´ on. (a) 0,88 ,

(b) 0,549 ,

(c) 0,51 .

6.2.7 En un juego en el que p = 0,49, hacemos apuestas de 1 ficha y nos retiramos cuando tengamos 100 fichas. ¿Qu´e cantidad inicial de fichas deberemos tener para poder asegurar que tenemos, al menos, un 50 % de oportunidades de terminar ganando? Sugerencia. Se trata de evaluar el valor de n para el que a(n) es menor que 0.5.

Ve rs i´on

Soluci´ on. 84 euros.

    2an = 5an−1 + bn−1

6.2.8 Resolver el siguiente sistema de ecuaciones de recurrencia

  

2bn = an−1 + 5bn−1 a0 = 1,

b0 = 0

Sugerencia. Los autovalores on son 2 y 3, y los autovectores asociados 1 1de la matriz de transici´ son, respectivamente, −1 y 1 .

Soluci´ on. an = 12 (3n + 2n ) ,

bn = 12 (3n − 2n ) . b ◦

6.2.9 Consideremos la figura siguiente:

◦ ◦ a c Colocamos una ficha (aleatoriamente) en una de las posiciones a, b o ´ c y luego la movemos siguiendo los caminos posibles del dibujo (todos los movimientos son igualmente probables). Llamamos an a la probabilidad de que la ficha est´e en a tras n movimientos (de forma an´ aloga se definen bn y cn ).

(a) Mostrar que: an + bn + cn = 1, n = 0, 1, 2... (b) Calcular an , bn y cn . (Sugerencia: establecer un sistema de recurrencias). (c) Estimar estas probabilidades en el l´ımite n → ∞. (d) ¿C´ omo cambiar´ıa el problema si la distribuci´ on inicial no fuera aleatoria? Por ejemplo, si sabemos que la ficha est´ a inicialmente en a.

(versi´ on preliminar 23 de diciembre de 2003)

6.2. Resoluci´on de ecuaciones de recurrencia

433

pr eli m in ar

Sugerencia. La probabilidad de estar en a tras n movimientos se escribe en t´erminos de la de estar en b tras n − 1 y luego moverse de b a a (y este suceso tiene una cierta probabilidad) m´ as la de estar en c tras n − 1 y luego moverse a a. Igual para bn y cn . La matriz de transici´ on tiene autovalores 1, -1/3 y -2/3, con autovectores       1 1 0        3/2   −1/2   1  3/2 −1/2 −1 respectivamente. Para el u ´ltimo apartado, basta cambiar el vector de condiciones iniciales, del (1/3, 1/3, 1/3) de la distribuci´ on aleatoria al (1, 0, 0). Observar que en este caso no se rompe la simetr´ıa entre las probabilidades bn y cn . Comprobar si esa simetr´ıa se mantiene cuando iniciamos los movimientos con la ﬁcha en c. Soluci´ on.

(b)

(d)

 1 n 1 1   an = 4 + 12 − 3 n 1 − 13 bn = 38 − 24  n  1 − 31 cn = 38 − 24  1 n 1 3   an = 4 + 4 − 3 n 3 bn = 38 − 12 − 13  n  3 cn = 38 − 12 − 13

(c) l´ım an = n→∞

1 , 4

l´ım bn = l´ım cn =

n→∞

n→∞

3 8

Ve rs i´on

6.2.10 Sea una sucesi´ on (an ) definida por una ecuaci´ on de recurrencia lineal y homog´enea de grado m. Sea r el m´ aximo m´ odulo de las ra´ıces de la ecuaci´ on caracter´ıstica correspondiente. Comprobar que |an | l´ım sup n < +∞ . r n→∞

(versi´ on preliminar 23 de diciembre de 2003)

Versión preliminar Algunos ejemplos. 382 Capítulo 6. Ecuaciones de recurrencia

Recommend Stories

Story Transcript

Get in touch

Social