Cap´ıtulo 10

Funciones generatrices Como el lector habr´a observado, en muchas cuestiones combinatorias que hemos venido no, n, de un conjunto estudiando es natural especificar, aunque de forma gen´erica1 , el tama˜ de referencia, o el paso (n tambi´en) de un proceso de construcci´ on combinatorio, o las veces (n, ¡c´omo no!) que se repite un procedimiento. La respuesta a la cuesti´ on de inter´es, que podemos nombrar, de manera gen´erica tambi´en, como an , depende de n. Si por ejemplo n toma los valores 0, 1, 2, . . . , los resultados correspondientes forman una sucesi´ on (an )∞ n=0 . En ocasiones, disponemos de una f´ ormula para el t´ermino general de la sucesi´on en funci´ on del par´ ametro n. Por ejemplo, el n´ umero de subconjuntos de un conjunto de tama˜ no n es umeros +1 ´o −1 hasta un total de
2n y an = 2n . O, por ejemplo, si elegimos repetidamente n´ sumamos los resultados, el n´ umero de elecciones en las que la suma final vale 0 es an = 2n n . En otras ocasiones, nuestro an´ alisis nos permite obtener una regla de recurrencia para los umero de listas de ceros y unos de longitud n en n´ umeros an . Si por ejemplo an cuenta el n´ las que no aparecen ceros consecutivos (pero s´ı pueden aparecer unos consecutivos), entonces para cada n ≥ 3,

an = an−1 + an−2

como vimos en el ejemplo 6.1.5. Nuestra ecuaci´ on de recurrencia favorita, la de Fibonacci. umeros de Fibonacci Fn , pues las condiciones iniciales Aunque los an no son exactamente los n´ son ligeramente distintas (recu´erdese la definici´on 6.1). En p´ aginas anteriores han ido pareciendo ecuaciones de recurrencia para los coeficientes bin´omicos, los n´ umeros de Stirling, el n´ umero de particiones de un entero con ciertas caracter´ısticas, etc. Una regla de recurrencia (complementada con unas condiciones iniciales) es, sin duda, una buena manera de describir una sucesi´ on (an ). Pero, en muchas ocasiones, no nos permite entender c´omo es la sucesi´on: si crece o decrece, c´omo de deprisa lo hace, etc. En el cap´ıtulo 6 aprendimos diversas t´ecnion de n, ciertos tipos de cas para resolver, esto es, obtener una f´ormula para los an en funci´ ecuaciones de recurrencia. Pero no siempre es posible hacerlo, e incluso en el caso de tenerla, pudiera ser tan complicada que fuera dif´ıcil extraer la informaci´ on que encierra. En general, no nos interesa un t´ermino en concreto, sino toda la sucesi´on (an ). Si queremos aprender sobre la sucesi´on (an ) en s´ı, una posibilidad, en muchos casos la mejor posible, es 1

Perd´ onesenos el oximoron.

747

Cap´ıtulo 10. Funciones generatrices

748

aprehenderla mediante un u ´nico objeto, una funci´ on generatriz. En palabras de Wilf (de su muy recomendable Generatingfunctionology), una funci´ on generatriz es una cuerda de la ropa en la que tendemos una sucesi´on de n´ umeros para exhibirla.

Estas funciones permiten codificar sucesiones de la siguiente manera: (an )∞ n=0

←→

∞ 

an xn = f (x) .

n=0

Simplemente, decidimos que los n´ umeros an son los sucesivos coeficientes de la serie de potencias que nombramos como f (x). Al manipular f (x) estaremos manipulando la sucesi´on (an ) en su conjunto. Este enfoque, algo inocuo a primera vista, se revelar´ a (y ´este es el objetivo de este cap´ıtulo y los dos siguientes) un eficac´ısimo m´etodo. Por ejemplo, al codificar la sucesi´ on desconocida (an ) que cumple a0 = 0,

a1 = 1,

an = an−1 + an−2

para cada n ≥ 2,

obtendremos que la funci´ on generatriz asociada es x . f (x) = 1 − x − x2 Y de aqu´ı, tras algunas manipulaciones, obtendremos, ¡oh, sorpresa!, que √  √  √  √  5 1+ 5 n 5 1− 5 n − , an = 5 2 5 2 para cada n ≥ 0, lo que nos habr´ıa costado adivinar a priori 2 . Pero no s´ olo esto. Tener la sucesi´on codificada como coeficientes de una funci´ on tiene muumero de subconjuntos de tama˜ n o n que podemos exchas ventajas. Sea, por ejemplo, an el n´
 para cada n = 0, 1, . . . , 100, traer de un conjunto con 100 elementos. Sabemos que an = 100 n mientras que an = 0 si n > 100. Escribamos entonces  ∞ 100    100 n n an x = x = (1 + x)100 , f (x) = n n=0

n=0

donde ya hemos aplicado el teorema del binomio. Derivando y sustituyendo en x = 1 (tanto en la serie de potencias como en la expresi´on final de la funci´ on), obtenemos que   100  100 99 n . 100 × 2 = n n=0

O, en otras palabras, que   100
100 100 n n 100 1  n = n=0 50 = 100
100 , 100 2 n=0 n n=0 n que nos dice el tama˜ no medio de los subconjuntos es 50. 2

Valga el pleonasmo. Adivinar a posteriori es m´ as habitual y sencillo.

(versi´ on preliminar 29 de octubre de 2008)

10.1. Introducci´ on a las funciones generatrices

10.1.

749

Introducci´ on a las funciones generatrices

Es hora de que formalicemos un poco. En lo que sigue vamos a asociar funciones a sucesiones infinitas de n´ umeros, f (x)

←→

(an )∞ n=0 ,

mediante la regla

f (x) =

∞ 

an xn .

n=0

on” aunque, a priori, f (x) es la funci´ on generatriz3 de los (an ). Usamos la palabra “funci´ puede que la serie no converja y no tengamos realmente una funci´ on. A veces, por ejemplo cuando queramos sustituir x por un valor determinado, s´ı que tendremos que prestar atenci´ on a las cuestiones de convergencia. Pero mientras no sea ´ese el caso, podr´ıamos argumentar todo mediante series formales (v´ease la secci´on 10.7). El n´ umero an , que generalmente ser´a la respuesta a un cierto problema combinatorio, es el coeficiente de xn en la serie de potencias anterior, lo que resumiremos a veces con la notaci´on an = Coefn [f (x)] . A. Funciones generatrices de suma conocida Si disponemos de una expresi´ on para la funci´ on generatriz, entonces grandes ∞ tenemos n ventajas. Por ejemplo, si resulta que la serie de potencias f (x) = n=0 an x converge en un cierto intervalo (−R, R) y conocemos la expresi´on de f (x), entonces podremos evaluar la funci´ on (y cualquiera de sus derivadas) en valores de x que cumplan que |x| < R. En particular, podremos calcular los coeficientes mediante la f´ormula de Taylor habitual, an =

f (n) (0) , n!

aunque, en general, este m´etodo de c´alculo de coeficientes es poco pr´actico. De todo esto hablaremos en la secci´on 10.3, pero, por ahora, veamos algunos ejemplos. Por razones que pronto se har´ an evidentes, nuestra serie de potencias b´ asica, que deberemos tener siempre en mente, es la suma de la serie geom´etrica, ∞  n=0

xn =

1 , 1−x

que, desde el punto de vista anal´ıtico, s´ olo tiene sentido si |x| < 1. En este nuevo lenguaje, 1/(1 − x) es la funci´ on generatriz de la sucesi´ on infinita de unos: 1 1−x

←→

(1)∞ n=0 ;

o tambi´en Coefn [1/(1 − x)] = 1 para cada n = 0, 1, 2 . . . .

3

En ocasiones, funciones generatrices ordinarias, para distinguirlas de las que se manejan en otros contextos: funciones generatrices de probabilidad (v´ease el cap´ıtulo 11), funciones generatrices exponenciales o funciones generatrices de Dirichlet (cons´ ultese, para estos dos tipos, el cap´ıtulo 13). Estas otras funciones generatrices son, simplemente, variaciones en el m´etodo de codificar: contienen la misma informaci´ on, pero preparada para c´ alculos y an´ alisis particulares.

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

750

Tambi´en conocemos ya la serie de potencias que define la funci´ on exponencial:   ∞ ∞  xn 1 1 = ex ; ex ←→ para cada n ≥ 0. ; o bien Coefn [ex ] = n! n! n! n=0 n=0 Obs´ervese que la serie de potencias de la izquierda converge para cualquier valor de x. El teorema del binomio nos proporciona otro caso conocido: para m ≥ 1, ∞    m n x . (1 + x)m = n n=0

Esta representaci´on es v´alida para todo x porque, en
realidad, la serie de potencias es un  m polinomio, pues para n > m los coeficientes bin´omicos n son nulos:        m m m m , ,..., , 0, 0, . . . ; (1 + x) ←→ 0 1 m Ejemplo 10.1.1 Calculemos los coeficientes de la funci´ on f (x) = (1− x)−m−1 , para m ≥ 0. Obs´ervese que el caso m = 0 corresponde a la serie geom´etrica, cuyo desarrollo ya conocemos. N´otese tambi´en que, al derivar sucesivamente,       1 1 2 1 6 1 = , = , = ,... 2 3 1−x (1 − x) 1−x (1 − x) 1−x (1 − x)4 generamos, salvo constantes, la familia de funciones en las que estamos interesados. Mientras estemos en |x| < 1, todas estas manipulaciones son v´alidas (v´ease la subescci´on 10.3.1). As´ı que tiene sentido calcular los coeficientes de la funci´ on (1 − x)−m−1 , para cierto m ≥ 0, mediante la f´ ormula de Taylor. Sea entonces f (x) = (1 − x)−m−1 , y calculemos sus derivadas sucesivas: f  (x) =

m+1 (m + 1)(m + 2) (m + 1)(m + 2) · · · (m + n) , f  (x) = , . . . , f (n) (x) = . (1 − x)m+2 (1 − x)m+3 (1 − x)m+n+1

As´ı que (m + n)! . m!     m+n 1 (n) 1 (m + n)! f (0) = = . Coefn [f (x)] = n! n! m! m f (n) (0) =

Por tanto,

Es decir,

 ∞   m+n n 1 = x . (1 − x)m+1 m n=0

O, escrito de otro modo, 1 (1 − x)m+1



←→

m+n m

∞ n=0

       m m+1 m+2 = , , ,... . m m m

N´ otese que m es un par´ ametro fijo y que n es el ´ındice de la sucesi´ on. Cuando m = 0, recuperamos la sucesi´on que vale uno para cada n. ♣ (versi´ on preliminar 29 de octubre de 2008)

10.1. Introducci´ on a las funciones generatrices

10.1.1.

751

El m´ etodo de las funciones generatrices

Vamos a ilustrar la manera en que hay que proceder (y las precauciones que habr´ıa que tomar) a la hora de utilizar las funciones generatrices en el siguiente ejemplo, en el que recurrimos a una de nuestras sucesiones favoritas, la de Fibonacci, definida por F0 = 0, F1 = 1 y

Fn = Fn−1 + Fn−2

para cada n ≥ 2.

El primer paso es asociar a estos n´ umeros su funci´on generatriz, F (x) =

∞ 

Fn xn ,

n=0

de la que no sabemos, o al menos haremos como que no sabemos4 , si converge o no. Para ilustrar la versatilidad de este enfoque de las funciones generatrices, no fijamos todav´ıa nuestro objetivo; podr´ıa interesarnos obtener una f´ ormula cerrada para los Fn (esto es, resolver as. . . la recurrencia), quiz´ as calcular alguna serie num´erica relacionada con los Fn , o quiz´ La informaci´ on de que disponemos es la ecuaci´on de recurrencia (y los valores iniciales), as´ı que la utilizamos para manipular la sucesi´ on de n´ umeros (elevaremos estas manipulaciones formales a la categor´ıa de “reglas” en la secci´ on 10.2): F (x)

=

F0 + F1 x + F2 x2 + F3 x3 + · · ·

=

F0 + F1 x + (F0 + F1 )x2 + (F1 + F2 )x3 + · · ·

 F0 + F1 x + F0 x2 + F1 x3 + F2 x4 + · · · + F1 x2 + F2 x3 + F3 x4 + · · ·

=

F0 + F1 x + x2 F (x) + x(F (x) − F0 )

=

=⇒ F (x)(1 − x − x2 ) = x ,

donde, en el u ´ltimo paso, hemos utilizado los valores iniciales, F0 = 0 y F1 = 1. Sigue siendo una identidad formal: el producto de F (x) por el polinomio (1 − x − x2 ) da como resultado la sucesi´ on de n´ umeros (0, 1, 0, 0, . . . ), que hemos codificado como x. Seguimos: la soluci´ on (formal) es que F (x) coincide con el producto de x por la rec´ıproca (formal) de (1 − x − x2 ), que denotamos como 1/(1 − x − x2 ): 1 F (x) = x 1 − x − x2 (el lector que est´e interesado en el significado preciso de lo que estamos denominando “identidades formales” puede consultar la secci´ on 10.7). Ahora bien, la funci´ on x/(1 − x − x2 ) tiene un desarrollo de potencias, que llamamos simplemente Σ(x). Esto es un resultado general (v´ease el teorema 10.3), pero en este caso no hace falta apelar a ´el, pues basta observar que ∞  1 x = x = x (x + x2 )n , 1 − x − x2 1 − (x + x2 ) n=0

donde hemos utilizado la serie geom´etrica. As´ı que, necesariamente, la expresi´ on formal x/(1− x − x2 ), esto es, F (x), debe coincidir con la serie de potencias Σ(x).

√ De la f´ ormula de Binet (v´ease la secci´ on 6.3) se deduce que Fn es pr´ acticamente igual a τ n / 5. Incluso sin necesidad de conocer la f´ ormula expl´ıcita, se comprueba por inducci´ on que Fn < 2n si n ≥ 1. De estas estimaciones se puede deducir sin dificultad la convergencia de la serie para |x| < R con, por ejemplo, R = 1/2. 4

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

752

Si, como haremos en el ejemplo 10.4.1, nos interesara obtener una f´ ormula para los Fn , podr´ıamos reescribir los t´erminos (x + x2 )n que aparecen en la serie Σ(x) utilizando, a su vez, el teorema del binomio. O quiz´ as, directamente a partir de 1/(1 − x − x2 ), utilizar el m´etodo de las fracciones simples para obtener, una vez m´as, la f´ ormula de Binet √ n √  √ n √  5 1+ 5 5 1− 5 − para cada n ≥ 0 Fn = 5 2 5 2 Pero nuestro an´ alisis nos permite llegar m´as all´a. Por ejemplo, como veremos m´as adelante, la serie Σ(x) converge en el intervalo (−1/τ, 1/τ ) ≈ (−0, 6180, 0, 6180). Por supuesto, la raz´on a´urea ten´ıa que aparecer. As´ı que, a posteriori, comprobamos que F (x) converge en ese intervalo. De manera que tiene sentido evaluar F (x) en, digamos, x = 1/2, para obtener que F (1/2) =

∞  n=0

Fn

1/2 1 = = 2. n 2 1 − (1/2) − (1/2)2

O quiz´ as en x = τ /3, tambi´en en el intervalo de convergencia, para obtener la identidad F (τ /3) =

∞  n=0

Fn

τ /3 3τ τn = = . n 2 3 1 − (τ /3) − (τ /3) 9 − 3τ − τ 2

O, incluso, y con ciertas precauciones, atrevernos a evaluar la serie de potencias en un valor extremo de la regi´on de convergencia, como x = 1/τ . En los usos de funciones generatrices que iremos desgranando m´as adelante, deber´ıamos incluir siempre justificaciones de esta ´ındole, aunque no insistiremos en ellas, sobre todo, para no perder el hilo y repetirnos en exceso. Pero el lector est´a ya avisado. Guiados por los pasos que hemos ido dando en el ejemplo de los n´ umeros de Fibonacci, podemos enunciar tres etapas para el m´etodo de las funciones generatrices: La primera consiste, simplemente, en codificar la sucesi´on de inter´es con una funci´ on generatriz. Siguiendo a Wilf, se trata de de colgar la sucesi´ on de n´ umeros de la cuerda de tender ropa que es la funci´ on generatriz f (x). El siguiente paso es hallar una expresi´ on adecuada para f (x). Para ello necesitaremos manipular las expresiones que nos vayan apareciendo. En la secci´ on 10.2 veremos las reglas necesarias para hacerlo. Por u ´ltimo, necesitaremos desarrollar f (x), pues, al fin y al cabo, lo que nos interesan son f´ ormulas para los coeficientes. O quiz´as nos baste con analizar la f (x) obtenida. O m´as a´ un, es posible que lo que interese sea evaluar la funci´ on f (x) en un cierto valor de x. Esto requerir´ a estudiar las propiedades de f (x) como funci´ on. Las herramientas y los resultados que ser´an u ´tiles en esta tarea los encontraremos en la secci´on 10.3. Con esto ya tendremos la t´ecnica. La secci´on 10.4 nos permitir´ a comprobar la potencia de las funciones generatrices para resolver ecuaciones de recurrencia. Y, finalmente, en la secci´on 10.5 veremos algunas otras cuestiones que el uso de las funciones generatrices resuelve. En la secci´ on 10.7, y a modo de ap´endice, desarrollaremos parte del lenguaje de las series de potencias formales. Dejamos, por su especial relevancia, el estudio del uso de las funciones generatrices en ciertas cuestiones probabil´ısticas y combinatorias para los cap´ıtulos 11 y 12, respectivamente. (versi´ on preliminar 29 de octubre de 2008)

10.2. Manipulaci´ on de funciones generatrices

10.2.

753

Manipulaci´ on de funciones generatrices

Veremos ahora c´omo algunas operaciones entre funciones generatrices se traducen en sus sucesiones asociadas; o viceversa. En todo lo que sigue, salvo cuando sea imprescindible hacer un estudio expl´ıcito, supondremos que todas las manipulaciones est´an bien justificadas. El lector con inclinaciones anal´ıticas puede revisar el ejercicio 10.3.1; aqu´el cuyo esp´ıritu sea m´as algebraico y quiera interesarse por el punto de vista de las series formales de potencias puede consultar la secci´ on 10.7. Regla 1: Sumar y multiplicar por constantes Sean dos funciones generatrices f (x) y g(x), asociadas a dos sucesiones de n´ umeros, (an ) umeros cualesquiera. Esta primera regla tiene que y (bn ), respectivamente, y sean α y β dos n´ ver con los coeficientes de la funci´on αf (x) + βg(x). No hay grandes sorpresas, son los que uno espera: ⎫ f (x) ←→ (an )∞ n=0 ⎬ g(x) ←→

(bn )∞ n=0

⎭

=⇒

αf (x) + βg(x) ←→ (α an + β bn )∞ n=0

As´ı que al sumar (y/o multiplicar por constantes) funciones generatrices, estamos sumando (y/o multiplicando por constantes) las sucesiones asociadas. La prueba es trivial y queda como entretenimiento (ni siquiera ejercicio) para el lector. Regla 2: Producto de funciones La siguiente regla considera el producto puntual de dos funciones generatrices f (x) y g(x) asociadas a las sucesiones (an ) y (bn ), respectivamente. Empezamos con las primeras manipulaciones:      ∞ ∞ ∞ ∞  ak xk bj xj = ak bj xk+j . f (x) · g(x) = k=0

j=0

k=0 j=0

Ahora viene el paso clave para la f´ ormula que presentaremos luego. Se trata de determinar el coeficiente n-´esimo de la serie de potencias f (x)g(x). Obtendremos t´erminos con xn cuando los ´ındices k y j sean tales que k + j = n. Y cada combinaci´ on de ´estas contribuir´a con el producto ak bj correspondiente. As´ı que, si llamamos cn a los coeficientes de f (x)g(x), podemos escribir que  ak bj . cn = k+j=n

En realidad es una suma doble, en los ´ındices k y j; pero s´ olo sumamos aqu´ellos cuya suma valga n. A´ un podemos reescribirla de forma m´ as manejable. Miremos los primeros casos. Por ejemplo, para c0 , debemos considerar las maneras de escribir k + j = 0: s´olo hay una, k = 0 y as posibilidades: tendremos j = 0, as´ı que c0 = a0 b0 . Para el segundo coeficiente, c1 , ya hay m´ k + j = 1 cuando, o bien k = 0 y j = 1, o bien k = 1 y j = 0; es decir, c1 = a0 b1 + a1 b0 . (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

754

El lector ya podr´ a escribir el valor de c2 , listando, simplemente, los posibles pares (k, j) que cumplan que k + j = 2. Llegar´a as´ı sin dificultad a que c2 = a0 b2 + a1 b1 + a2 b0 . Tras este an´alisis preliminar, la regla general es casi obvia: cn =

n 

ak bn−k ,

k=0

el llamado producto de Cauchy: ⎫ f (x) ←→ (an )∞ n=0 ⎬ ⎭ g(x) ←→ (bn )∞ n=0

=⇒

f (x) · g(x) ←→

 n

∞ ak bn−k

k=0

n=0

Interpretaci´ on combinatoria del producto de dos funciones generatrices Imaginemos que tenemos objetos de dos tipos, A y B. Para cada n, hay an objetos de no n. tipo A y tama˜ no n, mientras que existen bn objetos de tipo B y tama˜ El objetivo es formar objetos de tama˜ no total n que est´en formados por uno de tipo A y otro de tipo B. Para construirlos, aplicamos las reglas de la suma y del producto: 1. Llamamos k al tama˜ no del objeto de tipo A elegido. El par´ ametro k, por supuesto, se mover´a entre 0 y n. 2. Elegimos el objeto de tipo A de tama˜ no k. Esto se podr´ a hacer de ak formas. 3. Elegimos el objeto de tipo B, que tendr´ a que ser de tama˜ no n − k: se podr´ a hacer de bn−k maneras. umero de objetos que podemos construir con esas caracter´ısticas, En total, si llamamos cn al n´ se tendr´a que n  ak bn−k . cn = k=0

En t´erminos de las funciones generatrices asociadas, si llamamos f (x) y g(x) a las funciones on f (x)g(x) generatrices asociadas a las sucesiones (an ) y (bn ), respectivamente, la funci´ ser´a la funci´ on generatriz de los cn . Para ilustrar esta interpretaci´on, consideremos el siguiente ejemplo. Ejemplo 10.2.1 En un consejo de administraci´ on hay 25 personas, de las que 11 son mujeres. Se quiere formar un comit´e con 10 personas.
 es distintos. ¿De cu´antas formas se podr´ a hacer? La respuesta es inmediata: hay 25 10 comit´ Pero ahora vamos a contarlos atendiendo al n´ umero de hombres y mujeres que hay en ellos. En la terminolog´ıa anterior, los objetos de tipo A ser´an las posibles combinaciones de mujeres que forman parte del comit´e, y los de tipo B, las de hombres:

  

   11 14 formas de escoger n formas de escoger n = , bn = # = . an = # de entre las 11 mujeres de entre los 14 hombres n n (versi´ on preliminar 29 de octubre de 2008)

10.2. Manipulaci´ on de funciones generatrices Sus funciones generatrices asociadas son ∞    11 n x = (1 + x)11 A(x) = n n=0

y

755

B(x) =

∞    14 n=0

n

xn = (1 + x)14 .

La respuesta que buscamos es el coeficiente 
la14funci´  on A(x) B(x), un coeficiente del  c10
11de as, que ya sabemos, por la regla 2, que vale 10 j=0 j 10−j . Pero, adem´ 11

14

A(x) B(x) = (1 + x) (1 + x)

25

= (1 + x)



=⇒ Coef10 [A(x) B(x)] =

 25 . 10

As´ı que hemos probado que 

25 10



 10     11 14 . = j 10 − j j=0

Y si generalizamos el argumento (con s mujeres, t hombres y un comit´e de n personas), tendremos una prueba, con funciones generatrices, de la identidad de Vandermonde,    n    s t s+t = , j n−j n j=0

que ya ha aparecido en varias ocasiones (v´eanse las subsecciones 3.1.1 y 3.1.3).

♣

Regla 3: Desplazar coeficientes En muchas ocasiones interesa considerar la sucesi´on de n´ umeros que se obtiene de una dada desplazando los coeficientes hacia la derecha o hacia la izquierda. Consideremos la funci´ on generatriz f (x) de una cierta sucesi´on (an ). Si multiplicamos por x, x f (x) = a0 x + a1 x2 + a2 x3 + · · · =

∞ 

aj xj+1 =

j=0

∞ 

an−1 xn .

n=1

Es decir, el coeficiente n-´esimo de xf (x) es el coeficiente n − 1 de f (x). Pero cuidado, s´ olo para n ≥ 1, pues el coeficiente cero de xf (x) es ahora 0: xf (x)

←→

(0, a0 , a1 , a2 , . . . ) .

Y si multiplicamos por una potencia mayor, xm , con m ≥ 1, desplazamos la sucesi´on hacia la derecha m posiciones y tendremos m ceros al principio. La regla general es f (x) ←→ (an )∞ n=0

=⇒

xm f (x) ←→ (0, 0, (m) . . ., 0, a0 , a1 , a2 , . . . ) = (an−m )∞ n=0

La u ´ltima expresi´on es simplemente una notaci´on que nos permite abreviar, en la que aplicamos el convenio de que si el ´ındice del coeficiente es negativo, entonces el coeficiente vale cero. (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

756

El desplazamiento de coeficientes en el otro sentido requiere un an´ alisis m´as cuidadoso. on f (x) y nos Por ejemplo, partimos de una sucesi´on (a0 , a1 , a2 , . . . ) asociada a una funci´ preguntamos por la funci´ on generatriz g(x) asociada a la sucesi´ on (a1 , a2 , a3 , . . . ). Obs´ervese on vienen dados por bn = an+1 , para cada n ≥ 0. que los coeficientes bn de esta nueva funci´ on Primero, claro, hay que eliminar el coeficiente a0 , as´ı que debemos considerar la funci´ f (x) − a0 = a1 x + a2 x2 + a3 x3 + · · · umeros Esto no es todav´ıa g(x), pues la funci´ on f (x) − a0 est´a asociada a la sucesi´on5 de n´ (0, a1 , a2 , . . . ). La funci´ on que buscamos, g(x), est´a asociada a (a1 , a2 , a3 , . . . ). As´ı que, con la regla de desplazamiento hacia la derecha, xg(x) genera la sucesi´on (0, a1 , a2 , a3 , . . . ), que es, precisamente, f (x) − a0 . De manera que f (x) − a0 . x ¡Ay!, una x en el denominador, y se supone que esto es una serie de potencias centrada en el 0. Pero no debemos preocuparnos, porque la serie de la funci´on f (x) − a0 no tiene t´ermino independiente, as´ı que al dividirla por x obtenemos una serie de potencias legal. El caso general sigue los mismos argumentos. Dado m ≥ 1, si f (x) es la funci´ on generatriz de la sucesi´ on (an ), entonces xg(x) = f (x) − a0

f (x) − a0 − a1 x − · · · − am−1 xm−1 xm

=⇒

←→

g(x) =

(am , am+1 , am+2 , . . . ) = (an+m )∞ n=0

La operaci´ on del numerador sustituye los primeros m coeficientes por 0 y la “divisi´on” por xm los elimina. Resumimos las dos reglas de desplazamiento de coeficientes: Coefn [f (x)] = Coefn+m [xm f (x)] ,

f (x) − a0 − a1 x − · · · − am−1 xm−1 . (si n ≥ m) Coefn [f (x)] = Coefn−m xm Y, como ejemplo de aplicaci´ on, consideremos la funci´ on 1/(1 − x), asociada a la sucesi´on (1, 1, 1, . . . ). Entonces, x2 x ←→ (0, 1, 1, 1 . . . ) , ←→ (0, 0, 1, 1, . . . ) , etc. 1−x 1−x Obs´ervese que si desplazamos, por ejemplo, la sucesi´on hacia la izquierda tres posiciones, volvemos a tener la sucesi´on de unos. No hay problema, porque, como el lector podr´ a comprobar, la funci´ on 1 2 1 1−x − 1 − x − x . vuelve a ser 3 x 1−x 5

Obs´ervese que, de paso, hemos hallado una “regla” que permite sustituir un coeficiente cualquiera por 0. Aqu´ı lo hemos hecho para el primer coeficiente, pero el lector podr´ıa reflexionar sobr´e cu´ al es la funci´ on generatriz de la sucesi´ on en la que, por ejemplo, sustituimos el vig´esimo coeficiente de la original por 0. . . La respuesta, claro, es f (x) − a19 x19 .

(versi´ on preliminar 29 de octubre de 2008)

10.2. Manipulaci´ on de funciones generatrices

757

Regla 4: Derivar (y algo m´ as) on generar´ a la Si tenemos una funci´ on f (x) que genera unos ciertos (an ), ¿qu´e funci´ sucesi´on (n an )? Buscamos una operaci´on que, aplicada a f (x), haga que sus coeficientes aparezcan multiplicados por la posici´on que ocupan. La estructura especial de las series de potencias nos hace sospechar que esa operaci´on va a ser la derivaci´ on (o casi): f (x) =

∞ 

n

an x

=⇒



f (x) =

n=0

∞ 

n an xn−1 .

n=1

As´ı que f  (x) est´a asociada a la sucesi´on (1a1 , 2a2 , 3a3 , . . . ). Casi lo tenemos, salvo que el primer coeficiente deber´ıa ser 0a0 . As´ı que debemos desplazar la sucesi´on hacia la derecha una posici´on, y esto ya lo aprendimos a hacer con la regla anterior: x f  (x)

←→

(0a0 , 1a1 , 2a2 , 3a3 , . . . ) = (n an )∞ n=0

Si lo que queremos es obtener la funci´ on asociada a la sucesi´on (n2 an ), el mismo argumento, pero ahora aplicado a la funci´ on x f  (x) (cuyos coeficientes son n an ), nos lleva a que 
←→ (n2 an )∞ x x f  (x) n=0 . Y as´ı podr´ıamos seguir. Cada factor n extra en el coeficiente se obtiene repitiendo la operaci´on. Por abreviar, llamemos (x d/dx) al operador que act´ ua sobre una funci´ on deriv´ andola primero y multiplic´ andola por x despu´es. Entonces, si la potencia (xd/dx)m indica que hay que repetir m veces la operaci´on, tenemos que, para cada m ≥ 1,   d m f (x) ←→ (an )∞ =⇒ x (f (x)) ←→ (nm an )∞ n=0 n=0 dx Esta operaci´ on ser´a especialmente interesante, por ejemplo, a la hora de calcular medias, algo que haremos varias veces m´as adelante, en especial en el cap´ıtulo 11. Por ahora, y como ilustraci´ on, veamos cu´al es la funci´ on generatriz f (x) de la sucesi´on de n´ umeros (0, 1, 2, 3, . . . ). Sabemos que 1/(1 − x) genera la sucesi´on (1, 1, 1, . . . ), as´ı que no hay m´ as que aplicarle esta regla para obtener lo que buscamos:   x 1 = ←→ (0, 1, 2, 3, . . . ) . x 1−x (1 − x)2 O, con m´ as generalidad, podemos obtener la funci´ on generatriz de la sucesi´ on de n´ umeros (0, d, 2d, 3d, 4d, . . . ), la progresi´on aritm´etica que empieza en 0 y cuya diferencia es d: d 1−x

←→

(d, d, d, d, . . . )

xd (1 − x)2

=⇒

←→

(0, d, 2d, 3d, . . . )

Con muy poco m´ as de esfuerzo se puede comprobar que la funci´ on generatriz de una progresi´on aritm´etica general, que empiece en un cierto a y tenga diferencia d, es xd a + x (d − a) a + = 2 1 − x (1 − x) (1 − x)2

←→

(a, a + d, a + 2d, a + 3d, . . . ) .

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

758 Regla 5: Integrar

Digamos que una cierta funci´ on f (x) tiene como coeficientes a los n´ umeros (bn ), que nos son desconocidos. Disponemos, sin embargo, de los coeficientes (an ) de la funci´ on f  (x). ¿C´omo podemos escribir los bn en t´erminos de los an ? Obs´ervese que 

f (x) =

∞ 

n

an x ,

y tambi´en que



f (x) =

n=0

∞ 

k−1

kbk x

=

∞ 

(n + 1)bn+1 xn .

n=0

k=1

S´ olo tenemos que igualar coeficientes en las dos expresiones de f  (x) para obtener que bn+1 = an /(n + 1) para cada n ≥ 0 y concluir que f  (x) ←→ (an )∞ n=0

=⇒

 a a a  0 1 2 f (x) ←→ b0 , , , , . . . 1 2 3

Obs´ervese que el primer coeficiente de f (x) queda sin determinar. Ejemplo 10.2.2 Partimos de f  (x) = 1/(1− x) y queremos conocer los coeficientes de f (x). on, Los coeficientes de f  (x) son todos 1, as´ı que, siguiendo la regla de integraci´ ∞  1 n x . f (x) = b0 + n n=1

1 vienen Por otro lado, las funciones f (x) que verifican la ecuaci´ on diferencial f  (x) = 1−x
1  dadas por f (x) = log 1−x + C , donde C es una constante. Si sustituimos en x = 0, obtenemos C = f (0) = b0 . As´ı que     1 1 1 1 ←→ 0, 1, , , , . . . . log 1−x 2 3 4 ♣

Regla 6: Obtener sumas parciales La funci´ on 1/(1 − x), aqu´ella cuyos coeficientes son todos unos, es muy especial. Veamos el efecto que tiene, sobre los coeficientes de una cierta funci´on f (x), la multiplicaci´ on por la serie b´ asica. Aplicamos, simplemente, la regla 2: ∞

∞

∞

s=0

t=0

n=0

   1 = as xs xt = f (x) 1−x

 n



ak xn .

k=0

As´ı que el coeficiente n-´esimo de la funci´on f (x)/(1 − x) es la suma de los n primeros coeficientes de la funci´on f (x). El efecto de dividir por 1−x es que devuelve lo que llamaremos las sumas parciales de los coeficientes originales. f (x) ←→

(an )∞ n=0

=⇒

f (x) ←→ (a0 , a0 + a1 , a0 + a1 + a2 , . . . ) = 1−x

(versi´ on preliminar 29 de octubre de 2008)

 n k=0

∞ ak

n=0

10.2. Manipulaci´ on de funciones generatrices

759

Ejemplo 10.2.3 Calculemos de nuevo la suma de los primeros n n´ umeros naturales. El resultado ya lo conocemos (v´ease, por ejemplo, el ingenioso argumento que expusimos en la p´ agina 42). Obteng´ amoslo con funciones generatrices. Sabemos que la funci´ on x/(1 − x)2 est´a asociada a los n´ umeros (0, 1, 2, 3, . . . ). Es decir, que su coeficiente k-´esimo es, justamente, k. Esto lo obtuvimos utilizando la regla 4. Ahora, con esta nueva regla, resulta que x x 1 = 1 − x (1 − x)2 (1 − x)3

←→

 ∞ n k k=0

n=0

As´ı que la respuesta est´a en el coeficiente n-esimo de la funci´on x/(1− x)3 . Conocemos (v´ease el ejemplo 10.1.1) los coeficientes de (1 − x)−3 , as´ı que s´olo hay que utilizar la regla 3 para concluir que, si n ≥ 1,



    x 1 3 + (n − 1) − 1 n+1 n(n + 1) = Coef = = = Coefn n−1 (1 − x)3 (1 − x)3 2 3−1 2 (tambi´en v´ alido para n = 0). An´ alogos argumentos permiten obtener la suma de los primeros n cuadrados, cubos, etc. (v´ease el ejercicio 10.2.2, y tambi´en el 10.2.3). ♣ Ejemplo 10.2.4 Consideremos los n´ umeros arm´ onicos Hn , dados, para cada n ≥ 1, por n

Hn = 1 +

1 1 1 1 + + ··· + = 2 3 n j j=1

on generatriz de estos Hn . Definimos H0 = 0. Queremos encontrar la funci´ Ya sabemos, del ejemplo 10.2.2, que ∞  1   1 n x = log g(x) = n 1−x n=1

(obs´ervese que el t´ermino independiente, el valor g(0), es 0). As´ı que no hay m´ as que aplicar la regla de las sumas parciales para obtener que la funci´ on generatriz de los n´ umeros arm´onicos es   ∞  1 1 n log . Hn x = f (x) = 1−x 1−x ♣ n=0 Regla 7: Eliminar coeficientes Eliminar (esto es, sustituir por 0) algunos coeficientes de f (x) es sencillo (v´ease la nota al pie de la p´ agina 756). En ocasiones es necesario eliminar un conjunto infinito de ellos, por ejemplo los coeficientes de ´ındice par, para quedarnos con los de ´ındice impar. O quiz´ as nos interese rescatar u ´nicamente los coeficientes cuyos ´ındices sean, digamos, m´ ultiplos de 5. (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

760

Veamos el primer caso: f (x) es la funci´ on generatriz de una sucesi´ on de n´ umeros (an ) y queremos quedarnos u ´nicamente con los coeficientes de ´ındice par. Si escribimos f (x) =

∞ 

n

an x ,

entonces

f (−x) =

n=0

∞ 

n

an (−x) =

n=0

∞ 

an (−1)n xn

n=0

Obs´ervese que si f (x) tiene sentido para un cierto x, es decir, si x est´a dentro del radio de convergencia, entonces −x tambi´en lo estar´ a y tendr´ a sentido hablar de f (−x). Ahora, como el lector atento ya habr´ a imaginado, sumamos las dos series: f (x) + f (−x) = (a0 + a1 x + a2 x2 + a3 x3 + · · · ) + (a0 − a1 x + a2 x2 − a3 x3 + · · · ) . S´ olo sobreviven los t´erminos de ´ındice impar (multiplicados por 2), as´ı que ∞   f (x) + f (−x) = an xn = a2k x2k . 2 n par k=0

Ya podemos escribir la regla correspondiente: f (x) ←→ (an )∞ n=0 =⇒

f (x) + f (−x) ←→ (a0 , 0, a2 , 0, a4 , 0, a6 , 0, . . . ) 2

De manera an´ aloga, si restamos ambas series, seleccionaremos los t´erminos de ´ındice impar (que aparecer´an tambi´en multiplicados por 2), as´ı que f (x) ←→ (an )∞ n=0 =⇒

f (x) − f (−x) ←→ (0, a1 , 0, a3 , 0, a5 , 0, . . . ) 2

Seleccionar los t´erminos cuyos ´ındices son m´ ultiplos de 3 o´ de 4, o en general de un cierto entero, es algo m´as complicado, y requiere entender esta series de potencias en el contexto de la variable compleja (v´ease el ejercicio 10.2.4). Un asunto algo m´ as delicado es formar la funci´ on generatriz g(x) cuyos coeficientes son, digamos, los de ´ındice par de la f (x) (sin los ceros intermedios). Empecemos, por ejemplo, con la funci´ on generatriz de los n´ umeros de Fibonacci, f (x) =

∞  n=0

Fn xn =

x . 1 − x − x2

La funci´ on generatriz de la sucesi´ on (F0 , 0, F2 , 0, F4 , 0, . . . ) se obtiene como sigue: ∞   1 x f (x) + f (−x) −x x2 2n = F2n x = + . = g(x) = 2 2 1 − x − x2 1 + x − x2 1 − 3x2 + x4 n=0 Se trata de una serie de potencias en la que s´ olo aparecen potencias del tipo x2n y, como on definida a trav´es de debe ser, g(x) es, en realidad, una funci´ on de x2 . As´ı que la funci´ 2 h(x ) = g(x), ∞  x = F2n xn h(x) = 1 − 3x + x2 n=0

est´a asociada a la sucesi´on (F0 , F2 , F4 , . . . ). El lector podr´ a encontrar la versi´ on general de este procedimiento en el ejercicio 10.2.4. (versi´ on preliminar 29 de octubre de 2008)

10.2. Manipulaci´ on de funciones generatrices Regla 8: Composici´ on Partimos de dos funciones generatrices, f (x) = mos de calcular los coeficientes de su composici´on

761

∞

n n=0 an x

y g(x) =

∞

n n=0 bn x ,

y trata-

f (g(x)) = f ◦ g(x) . En lo que sigue, necesitaremos efectuar este tipo de operaciones en varias ocasiones (por ejemplo, en la subsecci´on 10.5.3 y en la secci´ on 11.2). Pero advertimos al lector de que se trata de una operaci´ on que no siempre est´a bien definida, ni desde el punto de vista anal´ıtico, ni siquiera desde el punto de vista de las series formales. Porque, si el lector se entretiene comprobando los detalles (como sugerimos hacer en el ejercicio 10.7.7), los coeficientes de la serie de potencias resultante no tienen por qu´e estar bien definidos, y resulta imprescindible a˜ nadir algunas condiciones adicionales. Afortunadamente, en los usos que aqu´ı veremos, estaremos en las condiciones que justifican estos manejos, que ilustramos ahora con dos ejemplos. Ejemplo 10.2.5 Partimos de una funci´ on generatriz f (x), asociada a la sucesi´ on (an ), y tomamos g(x) = x/(1 − x). Queremos describir los coeficientes de la funci´ on f (g(x)) = f (x/(1 − x)). Vamos a calcular, por comodidad, una peque˜ na variaci´ on, como es  x  1 f . 1−x 1−x Procedemos formalmente, sustituyendo una funci´ on en la otra e intercambiando los ´ındices de sumaci´ on:  ∞  ∞ ∞ ∞  x     1  xk 1 m+k m 1 k k f = ak = ak x = ak x x 1−x 1−x 1−x (1 − x)k (1 − x)k+1 k m=0 k=0 k=0 k=0   ∞    ∞  n      m+k n n = ak x = ak xn . k k n=0

n=0

k+m=n

k=0

Los coeficientes que se obtiene son sumas parciales de los an originales, pero ponderadas con coeficientes bin´omicos. Ya tenemos una nueva regla: f (x) ←→

(an )∞ n=0

=⇒

   ∞ n   x 1 n f ←→ ak 1−x 1−x k n=0 k=0

N´otese que los coeficientes de esta composici´on son sumas finitas. Apliquemos esta regla a la funci´ on generatriz de los n´ umeros de Fibonacci:   x x 1 1 f = , entonces , si f (x) = 2 1−x−x 1−x 1−x 1 − 3x + x2 como podr´ a comprobar el lector sustituyendo una funci´ on en la otra y simplificando. (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

762


  Los coeficientes de esta funci´on son, por la regla que acabamos de exponer, nk=0 nk Fk . Pero, como vimos en la Regla 7, son tambi´en los n´ umeros F2n . De esta manera probamos que F2n =

n    n k=0

k

Fk

para cada n ≥ 0

(m´as adelante, en la subsecci´on 10.5.2, insistiremos en el uso de las funciones generatrices para la verificaci´ on de identidades). Ejemplo 10.2.6 La funci´ on generatriz f (x) est´ a asociada a la sucesi´ on (an ), y ahora tomamos g(x) = 1 + x. Queremos describir los coeficientes de la funci´ on f (g(x)) = f (1 + x). Procedemos formalmente, intercambiando los ´ındices de sumaci´ on: f (1 + x) =

∞ 

k

ak (1 + x) =

k=0

∞ 

ak

k    k n=0

k=0

n

n

x =

∞  ∞    k n=0

k=n

n

ak xn .

As´ı llegamos a otra nueva “regla”: f (x) ←→

(an )∞ n=0

=⇒

 ∞ ∞   k f (1 + x) ←→ ak n n=0 k=n

Pero, ¡atenci´ on!, a diferencia del caso anterior, los coeficientes de f (1 + x) son ahora sumas infinitas, y por tanto no est´ a claro si est´an bien definidos o no (depender´ a de los an que consideremos). Si, por ejemplo, f (x) es un polinomio, la lista de coeficientes an es finita y tendr´ a sentido definir esta composici´on. Si al lector le intriga este diferente comportamiento, puede revisar el ejercicio 10.7.7, donde descubrir´ a que la sustituci´ on tiene sentido si g(0) = 0 (como ocurr´ıa para el caso de g(x) = x/(1 − x). Para una funci´ on como g(x) = 1 + x (para la que g(0) = 0), deberemos exigir condiciones adicionales a los an . ´ 10.2 EJERCICIOS DE LA SECCION 10.2.1 Si f (x), g(x) y h(x) son las funciones generatrices de las sucesiones (an ), (bn ) y (cn ), respectivamente, ¿cu´ ales son los coeficientes de las funci´ on f (x)g(x)h(x)? Si m ≥ 1, ¿cu´ ales son los coeficientes de la funci´ on f m (x)? 10.2.2 Compru´ebese, utilizando las reglas 4 y 6, que ∞  x + x2 = n2 xn (1 − x)3 n=0

y que

∞  n   x + x2 = k 2 xn . 4 (1 − x) n=0 k=0

Calc´ ulense los coeficientes de la funci´ on de la derecha para comprobar que que la suma de los primeros n cuadrados vale n(n + 1)(2n + 1)/6. Constr´ uyase tambi´en el argumento que permite evaluar la suma de los primeros n cubos.

(versi´ on preliminar 29 de octubre de 2008)

10.2. Manipulaci´ on de funciones generatrices

763

10.2.3 Consid´erense las dos funciones f (x) =

n  k=0

xn+1 − 1 x = x−1 k

y

g(x) =

n 

k xk .

k=1





Compru´ebese que g(x) = xf (x). Obs´ervese que g(1) = f (1) nos da el valor de la suma de los n primeros n´ umeros naturales. Calc´ ulese f  (1), derivando directamente en la f´ ormula de f (x) (y aplicando dos veces la regla de L’Hˆ opital). Constr´ uyase un argumento similar para comprobar que la suma de los primeros n cuadrados vale n(n + 1)(2n + 1)/6. 10.2.4 Selecci´ on de coeficientes con ´ındices m´ ultiplos de un entero. Ya hemos visto que si f (x) es la funci´ on generatriz de la sucesi´ on (an ), entonces g(x) = (f (x) + f (−x))/2 genera la sucesi´ on (a0 , 0, a2 , 0, a4 , 0, a6 , . . . ). Descubriremos en este ejercicio c´ omo hallar la funci´ on generatriz de la sucesi´ on en la que s´ olo aparecen los t´erminos de ´ındice m´ ultiplo de un cierto N , para lo que usaremos algunas propiedades de las ra´ıces N -´esimas de la unidad. (a) Compru´ebese (a mano) que g(x) =

f (x) + f (ix) + f (−x) + f (−ix) 4

genera la sucesi´ on

(a0 , 0, 0, 0, a4, 0, 0, 0, a8 , 0, . . . ).

(b) Dado N ≥ 2, consideramos las ra´ıces N -´esimas de la unidad, 1, ω, ω 2 , . . . , ω N −1 , con ω = e2π i/N , que cumplen que

N −1 1  j t 0 si t no es m´ ultiplo de N ; (ω ) = 1 si t es m´ ultiplo de N N j=0 (v´ease la p´ agina 32). Util´ıcese esto para comprobar que si f (x) genera la sucesi´ on (an ), entonces g(x) =

N 1  f (ω j x) N j=1

genera la sucesi´ on

(a0 , 0, . . . , 0, aN , 0, . . . , 0, a2N , 0, . . . ).

(c) Obs´ervese que la funci´ on g(x) definida en el apartado anterior es una serie de potencias de xN . Verif´ıquese, finalmente, que la funci´ on h(x) definida a trav´es de h(xN ) = g(x) genera la lista de coeficientes (a0 , aN , a2N , a3N , . . . ). 10.2.5 Recordando que la funci´ on ex genera la sucesi´ on (1/n!), y utilizando el ejercicio 10.2.4, obt´enganse f´ ormulas expl´ıcitas de las funciones generatrices de las sucesiones     1 1 1 1 1 y 1, 0, 0, 0, , 0, 0, 0, , 0, . . . 0, 1, 0, , 0, , 0, , 0, . . . 3! 5! 6! 4! 8! 10.2.6 La funci´ on x/(1 − x − x2 ) genera los n´ umeros de Fibonacci (Fn ). Util´ıcese el ejercicio 10.2.4 para comprobar que ∞ 

F2n x2n =

n=0

x2 1 − 3x2 + x4

y que

∞ 

F2n+1 x2n+1 =

n=0

x(1 − x2 ) 1 − 3x2 + x4

y para verificar que las funciones generatrices de las sucesiones (F0 , F2 , F4 , . . . ) y (F1 , F3 , F5 , . . . ) son ∞ 

x F2n x = 1 − 3x + x2 n=0 n

y que

∞  n=0

F2n+1 xn =

1−x 1 − 3x + x2

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

764

10.3.

Series de potencias y funciones generatrices

La relaci´on de listas de n´ umeros con funciones (an )∞ n=0

←→

f (x) =

∞ 

an xn

n=0

es un camino de ida y vuelta. Si tenemos la sucesi´ on (an ), nos interesa codificarla con su funci´ on generatriz ∞  an xn . f (x) = n=0

Se trata de una funci´ on, de una serie de potencias, que, a veces, podemos considerar como un objeto puramente algebraico. El camino de vuelta tambi´en es relevante: en ocasiones partiremos de una funci´ on f (x) que querremos desarrollar (si es que se puede) en serie de potencias, un desarrollo que ser´ a v´ alido en un cierto intervalo centrado en el origen. Nos interesan las dos direcciones. Porque aunque empecemos con (an ) y le asociemos su funci´ on generatriz f (x) para tener toda la sucesi´ on codificada, luego, una vez reconocida f (x), querremos desarrollarla en serie de potencias para as´ı obtener propiedades (f´ ormula, comportamiento asint´ otico) de los an . En este proceso resulta muy u ´til conocer la versi´ on anal´ıtica de la teor´ıa de las series de potencias, a la que vamos a dedicar esta secci´on. Estudiaremos, por un lado, las propiedades que tienen las series de potencias en cuanto funciones (subsecci´on 10.3.1). Por otro, repasaremos las diversas herramientas de que disponemos para obtener el desarrollo en serie de potencias de una funci´ on f (x): empezaremos, en la subsecci´on 10.3.2, con un recordatorio de ciertas cuestiones de representabilidad en serie de potencias. En la subsecci´on 10.3.3 describiremos el m´etodo de las fracciones simples, que quiz´as sea ya familiar al lector, y que es especialmente u ´ til a la hora de desarrollar funciones racionales. En la subsecci´ on 10.3.4 nos ocuparemos de la otra gran familia de funciones de inter´es, la relacionada con la serie geom´etrica y el teorema del binomio. Por u ´ltimo, la subsecci´ on 10.3.5 constituir´ a, o al menos as´ı lo esperamos, un puro divertimento para el lector: se trata de analizar los maravillosos argumentos que desarroll´ o Euler para sumar los inversos de los cuadrados.

10.3.1.

Series de potencias como funciones

Consideramos la funci´ on f (x) =

∞ 

an xn ,

n=0

umeros y x es una serie de potencias centrada en cero, donde (an ) es una cierta sucesi´on de n´ la variable6 . Se trata de una suma de infinitas funciones (a0 m´as a1 x, m´as a2 x2 , etc.), y como tal proceso infinito, hay que entenderlo en el sentido del l´ımite. El que una expresi´ on as´ı tenga sentido depender´ a, tanto de los coeficientes an , como de los valores de x que consideremos. 6 Tanto los coeficientes como la variable pueden ser n´ umeros complejos, aunque casi siempre ser´ an para nosotros n´ umeros reales.

(versi´ on preliminar 29 de octubre de 2008)

10.3. Series de potencias y funciones generatrices

765

A. Radio de convergencia

 Dada una serie num´erica infinita del tipo ∞ n=0 an , decimos que la serie converge si N l´ımN →∞ n=0 an existe y es finito. Y decimos que la serie converge absolutamente si  l´ımN →∞ N emonos en que, al introducir el valor absoluto, la convergencia n=0 |an | < +∞. Fij´ de la serie depende s´olo del tama˜ no de los coeficientes (del ritmo con el que decrecen a 0 cuando n → ∞), y perdemos posibles cancelaciones que pudieran ayudar en la convergencia de la serie original. Por eso, si una serie converge absolutamente, entonces tambi´en converge en el sentido ordinario. Pero el rec´ıproco no es cierto en general. El ejemplo m´ as simple es el de las series ∞ ∞   1 (−1)n+1 y . n n n=1 n=1 La de la izquierda, la serie arm´ onica, diverge. La de la derecha, sin embargo, converge (obtendremos su valor en el ejercicio 10.3.9). Esto es una consecuencia directa del siguiente resultado sobre series alternadas, que ya hemos utilizado alguna vez en cap´ıtulos anteriores: o n decreciente de t´erminos no negativos, a0 ≥ a1 ≥ · · · ≥ 0. Teorema 10.1 Sea (an ) una sucesi´ n Si l´ımn→∞ an = 0, entonces la serie ∞ n=0 (−1) an converge. Y el error cometido al truncar la serie en un cierto t´ermino est´ a controlado por el tama˜ no del primer t´ermino despreciado: ∞ t      n (−1) an − (−1)n an  ≤ at+1 .  n=0

n=0

Son parte de cualquier curso de C´ alculo los criterios de convergencia de series num´ericas. Por ejemplo, el criterio del cociente nos dice que si el l´ımite    an+1    ρ = l´ım  n→∞ an   existe (puede ser infinito), entonces la serie an converge si ρ < 1 y diverge si ρ > 1. En el caso ρ = 1, este criterio no decide y podemos tener convergencia o divergencia. Por ejemplo, obtenemos ρ = 1 al aplicar este criterio a las series con an = 1/n y an = 1/n2 . Y mientras que la serie arm´onica diverge, la suma de los inversos de los cuadrados, como veremos en la subsecci´on 10.3.5, vale π 2 /6. El criterio de la ra´ız es semejante: ahora el l´ımite que interesa calcular es  ρ = l´ım n |an | . n→∞

Si ρ < 1, la serie converge, y diverger´ a si ρ > 1. De nuevo, ρ = 1 no nos dice nada.  y que conocemos el valor ρ del Supongamos que tenemos una serie de potencias n an xn  ıamos l´ımite del criterio del cociente para la serie num´erica asociada ∞ n=0 an , Entonces podr´ intentar aplicar el criterio del cociente a los n´ umeros que sumamos en la serie de potencias:       n→∞  an+1 xn+1   = |x|  an+1  −   an  −−→ |x| ρ .  an xn  (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

766

As´ı que cuando |x| < ρ, la serie de potencias converger´a; y diverger´ a si |x| > ρ (el mismo argumento valdr´ıa si el ρ fuera el del criterio de la ra´ız).  n umero R De manera m´as formal, una serie de potencias ∞ n=0 an x tiene asociado un n´ 7 (entre 0 e ∞), su radio de convergencia, que se calcula de la siguiente manera :  1 = l´ım sup n |an | . R n→∞ Una vez calculado el radio de convergencia R, la serie de potencias converge absolutamente para los valores de x en el intervalo8 |x| < R, diverge si |x| > R; y en |x| = R podemos tener convergencia y/o divergencia. B. Derivadas

 n on bien definida en el intervalo (−R, R). Pero m´ as As´ı que f (x) = ∞ n=0 an x es una funci´ a´ un, la serie converge uniformemente en cualquier intervalo cerrado contenido estrictaon f (x) se puede mente en (−R, R). Sin entrar en m´ as detalles9 , esto supone que la funci´ diferenciar indefinidamente, y que esas derivadas vuelven a ser series de potencias de nuevo definidas en el intervalo (−R, R). La derivada se obtiene, simplemente, derivando t´ermino a termino: ∞   nan xn−1 para x ∈ (−R, R). f (x) = n=1

C. Comportamiento en los extremos del intervalo de convergencia  n on en el intervalo (−R, R), dado por La serie de potencias ∞ n=0 an x define una funci´ su radio de convergencia R. Es un intervalo abierto; nada se dice del comportamiento en los extremos de ese intervalo.  n La serie geom´etrica es un buen ejemplo de ello. ∞ n=0 x coincide con 1/(1 − x) en el intervalo (−1, 1). En x = −1, 1/(1 − x) vale 1/2, pero la serie no converge. En x = 1, la funci´ on 1/(1−x) no est´a definida; pero si nos aproximamos a 1 desde la regi´ on de convergencia (−1, 1), tiende a ∞, mientras que la serie tambi´en diverge a ∞. Vamos a ver a continuaci´ on c´ omo la convergencia de la serie num´erica que se obtiene al sustituir x = R (o, an´ alogamente, x = −R) en la serie de potencias nos dice que la funci´ on est´a adecuadamente definida por la serie en ese punto. En realidad, podemos restringirnos al caso en el que el radio de convergencia es R = 1 y bastar´ a analizar la sustituci´ on en x = 1 (el lector podr´ a comprobarlo completando los detalles del ejercicios 10.3.7). Antes de tratar el caso general, estudiaremos el caso particular en los coeficientes sean no negativos, porque es m´ as sencillo y tiene peculiaridades interesantes. 7 Es, esencialmente, el criterio de la ra´ız (aunque tambi´en podr´ıamos emplear una versi´ on con el criterio del cociente, v´ease el ejercicio 10.3.2). El s´ımbolo l´ım sup es el l´ımite superior de una sucesi´ on, una cantidad que, a diferencia de los l´ımites ordinarios, siempre existe (aunque cuando el l´ımite ordinario existe, coincide con el l´ımite superior). M´ as sobre radios de convergencia y comportamiento de los coeficientes, en la secci´ on 12.3. 8 En la versi´ on compleja, la regi´ on de convergencia no es un intervalo, sino un disco centrado en el origen. 9 El lector sabr´ a, sin duda, de las sutilezas que encierra la noci´ on de convergencia uniforme.

(versi´ on preliminar 29 de octubre de 2008)

10.3. Series de potencias y funciones generatrices

767

C.1) T´ erminos no negativos: continuidad en x = 1 En muchas de las aplicaciones de las funciones generatrices, los coeficientes de las series de potencias ser´an no negativos. Dos ejemplos: en los problemas de recuento, los an no s´olo son no negativos, sino adem´ as enteros; en las funciones generatrices de probabilidad, que umeros no negativos cuya suma vale 1. veremos en el cap´ıtulo 11, los an ser´an n´ El inter´es de la cuesti´on, un ejercicio, es el  como ejemplificamos m´as adelante y en alg´ a . Para ello, formamos la funci´ o n generatriz siguiente: queremos sumar ∞ n=0 n f (x) =

∞ 

an xn ,

n=0

hallamos una expresi´ on anal´ıtica para f (x) y luego calculamos l´ımx↑1 f (x). El resultado es la suma deseada. Por su utilidad y uso frecuente, vamos a considerar en este apartado el caso particular en que adem´ as de ser no negativos, los an cumplen10 que ∞ 

an < +∞ .

n=0

En este caso, el an´alisis de la convergencia es directo, porque si |x| < 1, ∞ 

|an xn | <

n=0

∞ 

|an | < +∞ .

n=0

As´ı que la serie de potencias converge absolutamente para |x| < 1; esto es, su radio de convergencia ser´ a, al menos, 1. Observemos que f (x) est´a definida por la serie en (−1, 1). Pero, en este caso, adem´as podemos sustituir x = 1 en la serie de potencias y “definir” f (1) mediante f (1) = ∞ n=0 an . Ahora nos preguntamos por la relaci´ on entre estas dos definiciones de f (x): la obtenida en (−1, 1) (a trav´es de la serie de potencias) y la definici´on en x = 1 que hemos hecho hace un momento. O, en t´erminos m´as t´ecnicos: ¿es f (x) continua (por la izquierda) en x = 1? Comprob´emoslo. Para empezar, ∞  n=0

an ≥

∞ 

an xn = f (x) ,

en 0 < x < 1,

n=0

porque en la segunda suma multiplicamos cada t´ermino (positivo) por el xn correspondiente, que es siempre < 1. Adem´as, f (x) es una funci´ on que crece con x. As´ı que existir´ a el l´ımite cuando x ↑ 1 y cumplir´ a que ∞  an ≥ l´ım f (x) . n=0

x↑1

10 El resultado que aqu´ı vamos a obtener aqu´ı (caso de coeficientes no negativos) es tambi´en cierto incluso si la serie num´erica diverge a +∞ (v´ease el lema 11.2).

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

768

Por otra parte, como todos los t´erminos son positivos, l´ım f (x) = l´ım x↑1

x↑1

∞ 

n

an x ≥ l´ım x↑1

n=0

N 

n

an x =

n=0

N 

an .

n=0

Y esto para cada N que consideremos. De estas dos observaciones deducimos que l´ım f (x) = l´ım x↑1

x↑1

∞  n=0

n

an x =

∞ 

an .

n=0

C.2) El Lema de Abel La continuidad vista anteriormente es general; ´este es el contenido del siguiente resultado11 , que ennoblecemos con el nombre de Abel12 : ∞ n Lema 10.2 (Abel) Si la serie de potencias n=0 an x tiene f∞(x) = radio de convergencia 1 y la serie num´erica n=0 an converge, entonces l´ım f (x) = x↑1

∞ 

an .

n=0

Dejamos la demostraci´on como ejercicio para el lector (v´ease el ejercicio 10.3.6) y nos dedicamos a ilustrarlo con la siguiente aplicaci´ on. ∞ 1 . Ejemplo 10.3.1 Calculemos el valor de la serie n=1 n (n+1)

Figura 10.1: Abel

El m´etodo habitual de c´ alculo parte de la siguiente observaci´ on: 1 1 1 = − n (n + 1) n n+1 11



para cada n ≥ 1,



Que conviene poner en perspectiva. Abel estaba interesado en dar sentido a sumas del tipo n an mediante ´ltimo l´ımite existe, se dice que la serie original es sumable Abel. Este m´etodo de el l´ımx→1 n an xn . Si este u sumaci´ on permite, por ejemplo, decidir que n (−1)n (una serie en principio divergente) se pueda interpretar como l´ımx→1 n (−1)n xn = l´ımx→1 1/(1 + x) = 1/2. Lo que el lema 10.2 asegura es que si n an ya es convergente, entonces tambi´en es sumable Abel (y el resultado de ambos procesos de sumaci´ on coinciden). El ejemplo n (−1)n nos muestra que el camino contrario, el que nos asegurar´ıa que si una serie es sumable Abel, entonces es tambi´en convergente, no es cierto en general. Para que lo sea, es necesario imponer ciertas condiciones a los coeficientes (los resultados correspondientes son conocidos como teoremas tauberianos). 12 La historia de Niels Henrik Abel (1802-1829), nacido en Noruega (entonces parte del reino dan´es), es una de las m´ as tristes de las Matem´ aticas. Una vida marcada por los problemas econ´ omicos, de salud y tambi´en por la mala suerte, que le acompa˜ nar´ıa hasta su temprana muerte por tuberculosis. Parece ser que envi´ oa Gauss sus trabajos sobre la imposibilidad de resolver la ecuaci´ on qu´ıntica por radicales, pero ´estos aparecer´ıan sin abrir tras la muerte del genio de G¨ ottingen. Tambi´en una famosa memoria sobre integrales el´ıpticas que envi´ o a la Academia de Paris fue extraviada y encontrada posteriormente por Cauchy. Se cuenta que, dos d´ıas despu´es de la muerte de Abel, se escribieron dos cartas para ´el: en una de ellas se le comunicaba la aparici´ on del tratado en la Academia de Paris. En la otra, Crelle, en cuya revista public´ o Abel gran parte de sus trabajos, le confirmaba que le hab´ıa conseguido un puesto permanente en Berlin. En el a˜ no 2002, el Gobierno noruego instituy´ o el Premio Abel, que pretende ser un equivalente al Premio Nobel para las Matem´ aticas (campo en el que, hasta ahora, s´ olo las Medallas Fields ten´ıan un rango semejante). El lector interesado puede consultar la semblanza de Abel titulada El Newton del Norte (La Gaceta de la RSME 5 (2002), no. 1), escrita en 1910 nada menos que por Jos´e Echegaray, matem´ atico espa˜ nol y Premio Nobel. . . aunque de Literatura, claro.

 



(versi´ on preliminar 29 de octubre de 2008)



10.3. Series de potencias y funciones generatrices

769

que nos basta para obtener el resultado deseado:    ∞ N    1 1 1 1 1 1 1 1 = l´ım − = l´ım 1 − + − + · · · + − N →∞ n (n + 1) N →∞ n n+1 2 2 3 N N +1 n=1 n=1   1 = 1. = l´ım 1 − N →∞ N +1 El enfoque alternativo, que utiliza funciones generatrices, comienza escribiendo α(x) =

∞  n=1

x2 x3 x4 1 xn+1 = + + + ··· , n (n + 1) 1·2 2·3 3·4

que es una serie de potencias con coeficientes positivos que tendr´a sentido y podr´ a ser derivada en |x| < 1. Derivando dos veces, ∞  x2 x3 1 n x = x+ + +··· , α (x) = n 2 3 n=1 



α (x) =

∞ 

xn = 1 + x + x2 + x3 + · · · =

n=0

1 . 1−x

Una vez que hemos conseguido sumar la serie de potencias de α (x), integrando una vez obtenemos que 1 α (x) = log 1−x (la constante de integraci´ on es cero, porque α (0) = 0). Integrando de nuevo, y recordando que α(0) = 0, obtenemos α(x) = (1 − x) log(1 − x) + x . El lema de Abel, aplicado a α(x), nos asegura que l´ım α(x) = x↑1

∞ 

1 . n (n + 1) n=1

S´ olo queda, y es un ejercicio sencillo de C´alculo, obtener el l´ımite cuando x ↑ 1 de α(x) = (1 − x) log(1 − x) + x; ese l´ımite resulta valer 1. ♣

10.3.2.

Funciones como series de potencias

Una funci´ on f (x) definida e infinitamente derivable en un intervalo (−D, D) alrededor del origen se dice representable en serie de potencias (en un intervalo (−E, E), no necesariamente el anterior) si ∞  an xn para todo x ∈ (−E, E). f (x) = n=0

Como la serie converge en (−E, E), el radio de convergencia R ser´a ≥ E. Derivando t´ermino a t´ermino, obtenemos que f (n) (0) , an = n! as´ı que la serie de potencias es, precisamente, la serie de Taylor de f (x) en el 0. La representaci´on, si es v´alida, es u ´nica. (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

770

Pero el asunto es m´as delicado de lo que pudiera parecer. Supongamos que partimos, como parece razonable, de una funci´ on f (x) definida e infinitamente derivable en un cierto intervalo (−D, D). Podemos formar, entonces, la serie de potencias ∞  f (n) (0)

n!

n=0

xn .

Nos preguntamos si esta serie de potencias converge en alg´ un punto adem´ as, claro, de en x = 0. Y en el caso de que haya convergencia en un cierto valor de x, si la suma de la serie coincide con f (x). Por ejemplo, podemos considerar la funci´ on f (x) = 1/(1 + x2 ), que es infinitamente derivable en todo x ∈ R. La serie de Taylor asociada es ∞ 

(−1)n x2n .

n=0

Ahora bien, el radio de convergencia de esta serie es R = 1. ¿Cu´ al es la raz´on por la que la serie representa a una funci´ on tan magn´ıfica como f (x) s´ olo en el intervalo (−1, 1)? De nuevo, la respuesta hay que buscarla en los n´ umeros complejos. El denominador de f (x) se anula en i y −i, as´ı que, vista como una funci´ on compleja, la serie de potencias converge en el disco de radio 1. 2

M´ as sorprendente es el caso de la funci´on f (x) = e−1/x si x = 0 y f (0) = 0. El lector podr´ a comprobar que f (n) (0) = 0 para todo n, as´ı que la serie de Taylor asociada es id´enticamente nula. Y claro, s´olo representa a f (x) en x = 0. En la terminolog´ıa de antes, D = R = ∞ (la funci´ on es infinitamente derivable en todo x, y la serie de Taylor converge para todo x), pero E = 0 (la serie de Taylor s´olo representa a la funci´ on en x = 0). As´ı que hay que exigirle m´ as a la funci´ on. Por ejemplo, condiciones sobre el tama˜ no de la funci´ on y sus derivadas. Una ilustraci´ on de esto es lo siguiente: si existe una constante A > 0 tal que |f (n) (x)| ≤ An para todo n y para todo x en un cierto entorno de x = 0, entonces la serie de Taylor representa a la funci´on en ese entorno. Afortunadamente, en la pr´ actica nuestras funciones ser´ an cocientes de polinomios, o variaciones sobre series de potencias ya conocidas, y las cuestiones de representabilidad ser´an sencillas. Por ejemplo, un resultado que utilizaremos (impl´ıcitamente) en muchas ocasiones es el siguiente: Teorema 10.3 Si f (x) es representable en serie de potencias en (−R, R) y f (0) = 0, entonces la funci´ on 1/f (x) es representable en serie de potencias en un cierto intervalo (−R , R ). Reflexionemos sobre lo que supone esto. Tenemos una cierta sucesi´on de n´ umeros, una serie formal f ; pero, adem´ as, la serie de potencias que con ellos formamos representa a una cierta funci´ on f (x). Desde el punto de vista formal, podr´ıamos calcular la sucesi´on de n´ umeros correspondiente a la rec´ıproca 1/f . Lo que aqu´ı se afirma es que una serie de potencias asociada a esa nueva sucesi´on converge en (−R , R ). Y con eso basta: no puede converger a otra cosa que a la funci´ on 1/f (x). (versi´ on preliminar 29 de octubre de 2008)

10.3. Series de potencias y funciones generatrices

10.3.3.

771

Desarrollo en serie de potencias de cocientes de polinomios

En muchas ocasiones nos enfrentaremos con el problema de obtener la serie de potencias asociada a un cociente de polinomios P (x) 1 = P (x) . Q(x) Q(x) El que esta funci´ on es representable en serie de potencias es justo lo que acabamos de ver. Lo que nos interesa ahora es c´ omo obtener ese desarrollo. En realidad, podr´ıamos limitarnos a desarrollar 1/Q(x). Una vez hecho, multiplicarla por P (x) no consistir´ a m´as que en aplicar, las veces que sea necesario, las reglas de manipulaci´on de funciones generatrices (suma de funciones, desplazamiento de coeficientes, multiplicaci´ on por constantes) que aprendimos en la secci´on 10.2. ´ Pero claro, tenemos el Teorema Fundamental del Algebra (teorema 4.44), que nos dice que si el polinomio Q(x) tiene grado k, entonces podemos escribir que C 1 = , r Q(x) (x − α1 ) 1 · · · (x − αt )rt donde C es una cierta constante, los αj son las ra´ıces (en principio, complejas) de Q(x) y los rj son las multiplicidades correspondientes. La suma r1 + · · · + rt es justamente k. Conocemos, por otro lado, los desarrollos en serie de potencias de ∞

 1 = xn , 1−x n=0

 ∞   1 n+m n = x , (1 − x)m+1 m

para m ≥ 1.

n=0

(desde el punto de vista anal´ıtico, estas identidades son ciertas si |x| < 1, como prueba, por ejemplo, el criterio del cociente). Manipulando estas expresiones, algo que dejamos como ejercicio al lector, podemos obtener los desarrollos de las siguientes funciones: si a = 0 y b son dos ciertas constantes,  ∞ ∞    1 (−1)n bn n n + m (−1)n bn n 1 = x , = x , para m ≥ 1 a + bx n=0 an+1 (a + bx)m+1 n=0 an+m+1 m (¿donde convergen estas series de potencias?). Como veremos en la subsecci´on siguiente, todas estas series son miembros de una “familia” mucho m´as numerosa. Vista la versatilidad de la serie b´asica, observamos que si consigui´eramos reescribir la expresi´on que obtuvimos antes para 1/Q(x) como una suma de t´erminos del tipo 1 , (x − αj )

o bien

1 , (x − αj )2

o quiz´ as

1 , (x − αj )3

etc.,

incluso permitiendo la presencia de t´erminos polin´ omicos en el numerador, el c´alculo de la serie de potencias de 1/Q(x) ser´ıa sencillo. Esto es lo que justifica el m´etodo de fracciones simples que pasamos a explicar. (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

772 El m´ etodo de fracciones simples

on racional del tipo El objetivo13 es desarrollar en serie de potencias una funci´ f (x) =

P (x) , Q(x)

donde P (x) y Q(x) son ciertos polinomios.

Primero, podemos suponer que el grado del polinomio del denominador es menor que el del denominador, pues si no fuera as´ı dividir´ıamos un polinomio por otro y llegar´ıamos a una expresi´on del tipo R(x) , T (x) + Q(x) donde R(x) ya es un polinomio de grado menor que el de Q(x). Los coeficientes del polinomio T (x) habr´ıa que tenerlos en cuenta, por supuesto: si tiene grado digamos k, influir´ıan en los primeros k coeficientes de la funci´on. Por ejemplo, 2 x3 + 1 = (x − 1) + 2 , x2 + x + 1 x +x+1 y s´olo restar´ıa desarrollar en serie el segundo t´ermino (recordando que el t´ermino x− 1 habr´ıa de ser tenido en cuenta al final). Supongamos entonces que estamos con P (x)/Q(x), y que el grado de Q(x) es mayor que el de P (x). El primer paso es encontrar las ra´ıces del polinomio del numerador, esto es, las soluciones de Q(x) = 0. Sabemos bien que esto puede resultar complicado, y que no hay f´ ormulas expl´ıcitas si el polinomio es de grado alto. Pero supongamos que las soluciones son on racional como los n´ umeros αi (con multiplicidades ri ). Podremos entonces escribir la funci´ P (x) P (x) =C . Q(x) (x − α1 )r1 · · · (x − αt )rt La constante C no desempe˜ na papel alguno en el estudio que estamos haciendo (aunque a la hora del c´ alculo habr´ a que tenerla en cuenta, por supuesto), as´ı que supongamos que es 1. El m´etodo de las fracciones simples consiste en reescribir la expresi´on anterior como   Ai,1 Ai,2 Ai,ri  P (x) + = + · · · + , (x − α1 )r1 · · · (x − αt )rt (x − αi ) (x − αi )2 (x − αi )ri t

i=1

donde los Ai,j son constantes que hay que determinar. Hay varias maneras de hacer esto, pero quiz´ as la m´as sencilla es la de sumar los t´erminos del miembro de la derecha: en el denominador nos volver´ a a quedar Q(x) y entonces bastar´a igualar los numeradores. De ah´ı obtendremos un sistema de ecuaciones lineales que nos dar´an el valor de las inc´ ognitas Ai,j . Una vez determinados los valores de estos n´ umeros, todo lo que nos queda son funciones que sabemos desarrollar: de la serie geom´etrica y su familia. 13

Quiz´ as el lector est´e familiarizado con el uso de este m´etodo para integrar una funci´ on racional P (x)/Q(x), reescribi´endola como suma de t´erminos con denominadores de la forma (ax +b)n , o de la forma (ax2 +bx+c)n , porque las integrales asociadas son inmediatas, en t´erminos de la funci´ on logaritmo o la funci´ on arcotangente. En nuestro an´ alisis nos limitaremos al primer tipo, pero a cambio deberemos manejar n´ umeros complejos.

(versi´ on preliminar 29 de octubre de 2008)

10.3. Series de potencias y funciones generatrices

773

N´otese que en todos estos argumentos, estamos d´andonos la licencia de entender las series de potencias como funciones de variable compleja; y los coeficientes que obtendremos al final del desarrollo ser´an, en general, combinaciones de n´ umeros complejos. Veamos un ejemplo, algo complicado de c´alculo, pero suficientemente ilustrativo: Ejemplo 10.3.2 Queremos desarrollar en serie de potencias la funci´ on racional f (x) =

x5 + x4 − 4 x3 + 4 x2 − 4 x + 4 P (x) = . Q(x) −x4 + 2 x3 − 2 x2 + 2 x − 1

El polinomio del numerador tiene grado mayor que el del denominador, as´ı que habr´ a que hacer una divisi´ on previa. Aunque podr´ıamos limitarnos a desarrollar 1/Q(x), y luego multiplicar por P (x), hag´ amoslo todo a la vez. La divisi´ on de los polinomios nos permite escribir f (x) = (−x − 3) +

−x4

+ 2 x3

1+x . − 2 x2 + 2 x − 1

Ahora, las cuatro soluciones de la ecuaci´ on −x4 + 2 x3 − 3 x2 + 2 x − 1 = 0 son i, −i y 1 (´esta, por partida doble). Y reescribir el polinomio en t´erminos de estas ra´ıces conduce a Q(x) = −x4 + 2 x3 − 3 x2 + 2 x − 1 = −(x − i) (x + i)(x − 1)2 = −(1 − i x) (1 + i x)(1 − x)2 . Obs´ervese c´omo hemos reescrito los factores, preparando los c´ alculos posteriores. Olvid´emonos por el momento del t´ermino −x − 3 (lo tendremos en cuenta al final) y desarrollemos el resto. El m´etodo de las fracciones simples nos sugiere escribirlo como (por comodidad, hemos puesto el signo menos en el denominador) B C1 C2 A −1 − x + + + = . (1 − i x) (1 + i x)(1 − x)2 (1 − i x) (1 + i x) 1 − x (1 − x)2 Si ahora sumamos a la derecha, el numerador que obtenemos resulta ser, tras el reordenamiento adecuado,         x3 iA−iB−C1 +x2 (1−2i)A+(1+2i)B+C1 +C2 +x (i−2)A−(i+2)B−C1 + A+B+C1 +C2 . on del siguiente Comparando con −1 − x llegamos a que los n´ umeros A, B, C1 y C2 son soluci´ sistema de ecuaciones: ⎧ iA − iB − C1 = 0 , ⎪ ⎪ ⎪ ⎨ (1 − 2i)A + (1 + 2i)B + C + C = 0 , 1 2 ⎪ (i − 2)A − (i + 2)B − C1 = −1 , ⎪ ⎪ ⎩ A + B + C1 + C2 = −1 . Esto es, A=

1+i , 4

B=

1−i , 4

1 C1 = − , 2

D = −1 .

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

774

Ahora ya podemos escribir nuestra funci´ on f (x) de una forma adecuada: f (x) = −3 − x +

1−i 1 1 1 1 1+i 1 + − − . 4 1 − ix 4 1 + ix 2 1 − x (1 − x)2

Finalmente, utilizamos la serie geom´etrica (y familia) para desarrollar en serie de potencias:   ∞  n+1 1 1+i n 1−i n i + (−i) − − xn f (x) = −3 − x + 4 4 2 1 n=0

∞ n  in+1   3  i n n 1 + (−1) + 1 − (−1) − − n xn . = −3 − x + 4 4 2 n=0 Los primeros coeficientes de esta funci´on (hay que tener cuidado con los dos primeros, en los que influye el t´ermino −3 − x) son (−4, −4, −4, −4, −5, −7, −8, −8, −9, −11, −12, −12, −13, · · · ) En realidad, todos los coeficientes que se obtienen son n´ umeros reales (m´as a´ un, enteros negativos). Pero esto es casualidad, porque nadie nos aseguraba, en principio, que los coeficientes del desarrollo tuvieran alg´ un significado especial. A´ un se puede escribir una f´ ormula m´as compacta para los an (para n ≥ 2):  −n − 1 si n ≡ 0 ´o n ≡ 3 (m´od 4), an = −n − 2 si n ≡ 1 ´o n ≡ 2 (m´od 4) La funci´ on parec´ıa complicada, pero sus coeficientes son sorprendentemente sencillos.

10.3.4.

♣

La serie geom´ etrica y la familia bin´ omica

La “familia” de la serie geom´etrica es m´as numerosa de lo que uno sospechar´ıa. Veamos, por ejemplo, lo que nos dice la f´ ormula del binomio:   ∞ ∞  m n  m(m − 1) · · · (m − n + 1) n m x . x = (1 + x) = n! n n=0

n=0

La serie llega, en realidad, hasta n = m; la presencia del coeficiente bin´ omico en la serie de la izquierda lo hace evidente. Pero tambi´en con la escritura de la derecha: si n > m, entonces algunos de los factores del numerador se anula. Veamos, por otra parte, el desarrollo de la funci´ on (1 − x)−m−1 :  ∞  ∞  m + n n  (m + n)(m + n − 1) · · · (m + 2)(m + 1) n 1 x = x = (1 − x)m+1 n! n n=0

=

n=0

∞  (−m − 1)(−m − 2) · · · ((−m − 1) − n + 2)((−m − 1) − n + 1) n=0

n!

(−x)n .

Hemos cambiado de signo los n factores del numerador, y el (−1)n resultante se lo hemos incorporado a la x. (versi´ on preliminar 29 de octubre de 2008)

10.3. Series de potencias y funciones generatrices

775

Todos estos manejos persiguen descubrir la analog´ıa que hay entre estos dos desarrollos, el de (1 + x)m y el de (1 + (−x))−m−1 . La simetr´ıa es evidente. Y es que ambos son casos particulares del siguiente teorema: Teorema 10.4 (Teorema del binomio) Para cada α ∈ R, si |x| < 1, entonces α

fα (x) = (1 + x) =

∞  α(α − 1)(α − 2) · · · (α − n + 1)

n!

n=0

xn .

Afirmamos aqu´ı que la serie de potencias converge, con seguridad, para |x| < 1, pero en algunos casos el intervalo de convergencia podr´ıa ser mayor. Por ejemplo, si α es un entero positivo, tenemos simplemente un polinomio (y la convergencia ser´a para todo x). Antes de ver la demostraci´ on, vamos a aplicar el teorema a la obtenci´on de los desarrollos en serie de unas cuantas funciones. Si α es un entero positivo, tenemos la f´ ormula del binomio habitual. Si α = −1 y ponemos −x en lugar de x, estamos con la serie geom´etrica. Tambi´en hemos visto ya el caso α = −m − 1, con m ≥ 0, y las posibles traslaciones y cambios de escala en la variable. As´ı que nos centraremos en otros valores de α. Por comodidad, y s´ olo por esta subsecci´on, consideraremos el coeficiente bin´ omico generalizado   α α(α − 1) · · · (α − n + 1) , = n! n donde α ∈ R (que coincide con el coeficiente bin´ omico habitual cuando α = m). Ejemplo 10.3.3 El caso α = 1/2. √ Estamos con la funci´on 1 + x, para |x| < 1:  ∞  ∞   √ 1 1/2 (1/2 − 1)(1/2 − 2) · · · (1/2 − n + 1) n 1/2 n x , 1 + x = (1 + x) 2 = x =1+ n! n n=0 n=1 =1+

∞  (−1)n−1 1 · 3 · 5 · · · (2n − 3)

n=1

2n

n!

xn .

√ M´ as interesante, desde el punto de vista combinatorio, es el desarrollo de la funci´ on 1 − 4x (en principio, para |x| < 1/4):  ∞  ∞   1 1 · 3 · 5 · · · (2n − 3) 1/2 1/2 (−4)n xn = (−1)n−1 n (−4x)n = 1 + (1 + (−4x)) 2 n! n n=0

∞ 

n=1

2n

1 · 3 · 5 · · · (2n − 3)(2n − 1) n! n x 2n − 1 n! n! n=1    ∞  1 · 3 · · · (2n − 1) 2 · 4 · · · (2n − 2) 2n n 1 x = 1− 2n − 1 n! n! = 1−

= 1−

n=1 ∞ 

1 (2n)! n x . 2n − 1 n! n! n=1

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

776

Tras unas sencillas manipulaciones, deducimos que √   ∞ 2n n 1 − 1 − 4x  1 = x . 2x n+1 n n=0

As´ı que la funci´ on de la izquierda genera una sucesi´ on de n´ umeros que son ya viejos conocidos, los n´ umeros de Catalan, sobre cuyas interpretaciones combinatorias nos extendimos en el ejemplo 2.3.3 y cuya expresi´ on expl´ıcita ya hab´ıamos obtenido en el ejemplo 3.1.3. ♣ Ejemplo 10.3.4 Las funciones trigonom´etricas inversas. Sorprendentemente, la f´ ormula del binomio nos permite hallar los desarrollo en serie potencias de inversas de funciones trigonom´etricas, como por ejemplo el arcoseno. La clave es que su derivada es 1 d arcsin(x) = √ . dx 1 − x2 Desarrollemos entonces la funci´on de la derecha con el teorema del binomio; para ello, calculemos primero   (−1/2) (−1/2 − 1) (−1/2 − 2) · · · (−1/2 − n + 1) −1/2 = n! n (−1)n 1 · 3 · 5 · · · (2n − 1) (−1/2) (−3/2) (−5/2) · · · (1 − 2n)/2 = . = n! 2n n! Con esto, y utilizando que 2n n! = 2 · 4 · 6 · · · 2n,  ∞  ∞   1 1 · 3 · 5 · · · (2n − 1) 2n −1/2 1 √ x = (−1)n x2n = 1 + 2n n! n 1 − x2 n=0 n=1  ∞ ∞ ∞     (2n)! 1 (2n)! 1 2n 1 2n 2n 2n x =1+ x = = 1+ x . 2n n! 2 · 4 · 6 · · · 2n 2n n! 2n n! n 22n n=1 n=1 n=0 Ahora queremos integrar esta serie. Con ayuda de la Regla 5 de la secci´ on 10.2, m´as la observaci´ on de que arcsin(0) = 0 (que nos permite fijar el valor del primer coeficiente), obtenemos que   ∞  1 2n 1 x2n+1 . arcsin(x) = 22n n 2n + 1 n=0

De la misma manera se pueden obtener los desarrollos del arcocoseno (aunque bastar´ıa aplicar que arc cos(x) = π/2 − arcsin(x)) y de la arcotangente (v´ease el ejercicio 10.3.10). ♣ La demostraci´ on del teorema del binomio Para cualquier α, la funci´ on (1 + x)α es infinitamente derivable, al menos para valores de x suficientemente pr´ oximos a cero (digamos |x| < 1). La f´ ormula de Taylor nos dice que una funci´ on con n derivadas se puede escribir, en este caso cerca del 0, como f  (0) 2 f (n) (0) n x + ··· + x + Rn (x) , 2! n! donde la funci´ on Rn (x) es el llamado resto de Taylor. f (x) = f (0) + f  (0) x +

(versi´ on preliminar 29 de octubre de 2008)

10.3. Series de potencias y funciones generatrices

777

Si f (x) = (1 + x)α , se comprueba sin dificultad que, para cada n, α(α − 1)(α − 2) · · · (α − n + 1) f (n) (0) = , n! n! as´ı que los coeficientes tiene la forma que propon´ıamos en el enunciado del teorema 10.4. Para probar el resultado deber´ıamos comprobar que el resto (del que se puede obtener una expresi´on expl´ıcita en t´erminos de la funci´ on) tiende a 0 cuando n → ∞. Sin embargo, ´ese no es el enfoque que adoptaremos aqu´ı14 . Nuestra estrategia ser´a la siguiente: argumentaremos como si supi´eramos que la funci´ on (1 + x)α se puede desarrollar en serie de potencias, para comprobar que ´esta ha de tener una forma espec´ıfica. El paso final consistir´ a en probar algunas propiedades de la serie que obtendremos que nos permitir´ an on adecuada). deducir que, efectivamente, coincide con la funci´ on (1 + x)α (en la regi´ Empecemos descubriendo la expresi´on que deber´ıan tener los coeficientes de la serie, de la manera en la que lo habr´ıa hecho Newton, utilizando el m´etodo de los los coeficientes indeterminados. Esto supone escribir, para α ∈ R, (1 + x)α =

∞  n=0

cαn xn ,

cαn

son todav´ıa desconocidos. Por ahora entendemos esta igualdad (y los manejos donde los posteriores que haremos) en un sentido formal; ya los justificaremos m´ as adelante desde el punto de vista anal´ıtico. Obs´ervese (tomando x = 0) que cα0 = 1 para cualquier α. Primero, ∞  n=0

n α+1 cα+1 = (1 + x)α (1 + x) = (1 + x) n x = (1 + x)

∞  n=0

cαn xn =

∞  n=0

cαn xn +

∞  n=1

cαn−1 xn .

As´ı que, igualando coeficientes, obtenemos que = cαn + cαn−1 cα+1 n

si n ≥ 1.

Es decir, obtenemos una ley de recurrencia (por cierto, la misma que en el caso de los α coeficientes bin´omicos) que nos permite obtener la sucesi´on (cα+1 n ) a partir de (cn ). m Cuando α = m, con m un entero positivo, adem´ as de que cm 0 = 1, sabemos que cm = 1; y esto basta, v´ıa la construcci´ on del tri´ angulo de Tartaglia, para conocer la forma de los cm n. α as. La Pero en el caso general s´olo tenemos que c0 = 1. As´ı que debemos intentar algo m´ identidad

d (1 + x)α (1 + x) , α(1 + x)α = α(1 + x)α−1 (1 + x) = dx traducida a la serie (insistimos en que por ahora son c´ alculos formales), nos da α

∞  n=0

cαn xn = (1 + x)

∞  n=1

n cαn xn−1 =

∞ 

(n + 1)cαn+1 xn +

n=0

∞  n=1

n cαn xn .

14 V´ease, por ejemplo, en el texto An´ alisis Matem´ atico, T.M. Apostol, Ed. Revert´e, una discusi´ on de la convergencia de la serie bin´ omica estimando el resto.

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

778 Igualando coeficientes,

α−n α c . n+1 n Ahora tenemos una recurrencia que involucra coeficientes con el mismo α; como conocemos cα0 , on, deducimos esta nueva identidad nos permite calcular toda la sucesi´ on (cαn ). Por inducci´ que, para cada n,   α(α − 1) . . . (α − n + 1) α α = , cn = n! n donde hacemos uso, de nuevo, de la notaci´ on de los coeficientes bin´omicos generalizados. Por ahora hemos comprobado (al menos formalmente) que, al traducir las propiedades de la funci´ on en los hipot´eticos coeficientes, ´estos han de tener una forma determinada. A´ un hemos de probar que la serie con esos coeficientes representa, efectivamente, a la funci´on (1 + x)α . Llamemos ∞    α n x Bα (x) = n α cαn = (n + 1) cαn+1 + n cαn

o, equivalentemente,

cαn+1 =

n=0

a la serie de potencias que nos interesa. Apliqu´emosle el criterio del cociente:            α − n  α(α − 1) . . . (α − n) n! α n  α  n+1  .   = |x|  x  = |x|  x    n+1 (n + 1)! α(α − 1) . . . (α − n + 1)  n+1 n Es decir, si |x| < 1,

        α − n α n  α  n+1  = |x| < 1. x  = l´ım sup |x|  x l´ım sup   n+1 n n→∞  n + 1 n→∞

Esto supone que la serie de potencias converge uniformemente en cualquier intervalo de la forma [−a, a], donde a < 1. As´ı que podemos derivar la serie t´ermino a t´ermino (compru´ebese en especial la manipulaci´on de la segunda igualdad), ∞   ∞   ∞   ∞      α α α k  α n xn−1 = (α − k) xk = α x − k xk Bα (x) = n k k k n=1

k=0

k=0

k=0

para obtener la siguiente ecuaci´ on diferencial para Bα : Bα (x) = α Bα (x) − xBα (x)

=⇒

Bα (x)(1 + x) = αBα (x) .

Utilizando esta identidad, deducimos que   Bα (x)  Bα (x)(1 + x)α − Bα (x)α(1 + x)α−1 = = 0. (1 + x)α (1 + x)2α As´ı que

Bα (x) = (constante) (1 + x)α .

Pero como Bα (0) = 1, podemos concluir, finalmente, que Bα (x) = (1 + x)α para −1 < x < 1, como quer´ıamos demostrar. (versi´ on preliminar 29 de octubre de 2008)




10.3. Series de potencias y funciones generatrices

10.3.5.

779

De c´ omo Euler venci´ o a los Bernoulli

Nuestro objetivo es obtener el valor de la serie ∞  1 . n2 n=1

 1 ıa, Este c´alculo, una vez que se sab´ıa que la serie arm´onica ∞ n=1 n diverg´ fue uno de los grandes retos de la matem´atica del siglo XVIII. Por supuesto, la suma es finita, porque, como 2n2 ≥ n(n + 1) para cada n ≥ 1, y recordando el ejemplo 10.3.1, ∞ ∞   1 2 = 2. ≤ 2 n n(n + 1)

n=1

n=1

Figura 10.2: Johann Bernoulli

Esto ya lo sab´ıa Leibniz, quien, tras conseguir sumar los inversos de los n´ umeros n(n + 1)/2 (los n´ umeros triangulares, v´ease el ejercicio 1.2.3), se propuso sumar los inversos de los n´ umeros cuadrados. Pero no fue capaz, ni tampoco Jacob Bernoulli, que conceder´ıa que [. . . ] ser´ıa muy grande nuestro agradecimiento si alguien nos comunicara este c´ alculo que, hasta ahora, ha eludido nuestros esfuerzos.

A˜ nos despu´es de la muerte de Jacob, Euler fue capaz de completar el c´ alculo. Johann Bernoulli15 dir´ıa: De este modo el m´as ferviente deseo de mi hermano se hace realidad. . . ¡si estuviera aqu´ı!

Un primer intento, aprovechando que los coeficientes son positivos, ser´ıa considerar f (x) =

∞  1 n x , n2

n=1

serie de potencias que converge uniformemente si |x| < 1, y buscar el “valor” de f (x) en x = 1. Podremos derivarla (y multiplicarla por x) dos veces, y luego integrar para obtener x f  (x) = x+


 x2 x3 1 1 + +· · · =⇒ x f  (x) = 1+x+x2 +· · · = =⇒ x f  (x) = log . 2 3 1−x 1−x

Pero as´ı no vamos por buen camino, porque no hay una expresi´ on anal´ıtica u ´til para f (x), que permita luego calcular el valor f (1), al menos en el sentido del l´ımite x → 1. 15

Johann Bernoulli (1667-1748) era un “puro” Bernoulli: competitivo, celoso de los dem´ as miembros matem´ aticos de su familia, acab´ o enfrentado, tanto a su hermano Jacob como a su propio hijo Daniel (v´eanse sus notas biogr´ aficas en las p´ aginas 505 y 456, respectivamente). No crea el lector que estos enfrentamientos a los que nos referimos eran peleas en la cocina de casa: los bravos Bernoulli acostumbraban a airear sus disputas p´ ublicamente. Como otros miembros de la familia, fue obligado a estudiar Medicina (su disertaci´on doctoral vers´ o sobre un modelo matem´ atico del movimiento muscular), aunque pronto se decantar´ıa por las Matem´ aticas, de la mano (¡s´ olo al principio!) de su hermano Jacob. A Johann se le recuerda especialmente por sus aportaciones a lo que hoy conocemos como C´ alculo variacional (braquistocrona, problema isoperim´etrico), aunque tambi´en por sus trabajos en Mec´ anica y en la teor´ıa de los fluidos. Como ilustraci´ on de las maniobras que se gastaban estos Bernoulli, se dice que false´ o la fecha de publicaci´ on de obra Hydraulica (que aparecer´ıa en 1739, pero datada en 1732), para adelantarse as´ı a la Hydrodinamica de su hijo Daniel, de 1738.

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

780

Hace falta algo m´as. La sorpresa: Euler. Sabemos (v´ease el ejemplo 10.3.4) que   ∞  1 2n 1 x2n+1 para 0 < x < 1. arcsin(x) = 22n n 2n + 1 n=0

Como todos los t´erminos son positivos, podemos (v´ease la subsecci´on 10.3.1) obtener el valor de la funci´ on en x = 1:   ∞ 1 π  1 2n = . 2n 2 n=0 2 n 2n + 1 Vamos ahora a calcular la integral 

1

I= 0

arcsin(x) √ dx 1 − x2

de dos maneras diferentes: por un lado, integrando por partes, 

1

I= 0

1 arcsin(x)2  π2 . arcsin(x) d(arcsin(x)) = =  2 8 0

Y por otro16 ,       1 2n+1  1 ∞ ∞  1 2n 1 2n x 1 dx 1 2n+1 √ √ x = dx . I= 2n 2n 2 2 2 n 2n + 1 n 2n + 1 0 1−x 1 − x2 0 n=0 n=0 La u ´ltima integral ya la obtuvimos en el ejemplo 6.1.17:  1 2n+1 22n 1 x √ . dx =   2n 2n + 1 1 − x2 0 n De estos dos c´alculos concluimos que ∞

 1 π2 = . 8 (2n + 1)2 n=0

Ya estamos cerca: s´olo queda observar que ∞ ∞ ∞ ∞ ∞  1  1     1 1 1 1 1 1 = + = + = + , 2 2 2 2 2 2 n n n (2k) (2k + 1) 4 k (2k + 1)2 n par

n=1

de donde

n impar

k=1

k=0

k=1

k=0

∞ ∞  π2 4 4 π2 1 1 = . = = n2 3 (2k + 1)2 3 8 6 n=1 k=0

16

Queda como ejercicio para el lector con inclinaciones hacia el An´ alisis Matem´ atico comprobar que se pueden intercambiar los s´ımbolos de integraci´ on y sumaci´ on. Puede, por ejemplo, considerar la integral entre 0 y 1 − ε, donde tenemos convergencia uniforme, y concluir con un argumento de monoton´ıa.

(versi´ on preliminar 29 de octubre de 2008)

10.3. Series de potencias y funciones generatrices

781

A. La primera demostraci´ on de Euler La que hemos descrito no fue, en realidad, la primera demostraci´ on de Euler. Anteriormente hab´ıa propuesto la elegante prueba que pasamos a exponer. Partimos de la funci´ on sin(x) x2 x4 x5 + − + ··· = , 3! 5! 6! x entendida (al menos as´ı lo hac´ıa Euler) como un polinomio infinito. Claramente, P (0) = 1, y las ra´ıces de la ecuaci´on P (x) = 0 vienen dados por x = k π, para cada entero k = 0. Si aceptamos que a este “polinomio infinito” se le pueden aplicar los argumentos de factorizaci´on de los polinomios usuales17 , podemos escribir que  ∞ ∞    x   x   x  x2 = 1+ = 1− 1− 1− 2 2 . P (x) = kπ kπ kπ k π P (x) = 1 −

k=1

k∈Z\{0}

k=1

Si mantenemos nuestra fe en la validez de estos argumentos, podemos desarrollar el producto infinito en serie de potencias e igualarlo a la expresi´ on original de P (x), para obtener que   2 4 5 x x 1 1 1 1 x + − + ··· = 1 − + + + + · · · x2 + · · · 1− 3! 5! 6! π 2 4 π 2 9 π 2 16 π 2 Y ahora s´ olo resta igualar los coeficientes de x2 para obtener18 finalmente que   ∞  1 1 π2 1 1 1 1 + ··· =⇒ . = − =− 2 1+ + + 3! π 4 9 16 k2 6 k=1

A´ un dar´ıa Euler una tercera prueba, que mostramos con cierto detalle en el ejercicio ∞ 110.3.13. Y sigui´ o explotando estas ideas para obtener los valores de las series del tipo k=1 kp , para valores pares de p. As´ı, por ejemplo19 , ∞  π4 1 , = k4 90 k=1

∞  π6 1 , = k6 945 k=1

∞  π8 1 , = k8 9450 k=1

∞  π 10 1 . = k10 93555 k=1

17

Esto dista de ser un detalle trivial. Euler sab´ıa que la factorizaci´ on usando los ceros era correcta, en particular, para sen(x)/x. Pero esto no es un hecho general. Por ejemplo, la funci´ on ex sen(x)/x tiene los mismos ceros y no coincide con el producto infinito. 18 El mismo argumento permite obtener la f´ ormula de Wallis (que hemos visto con detalle en la subsecci´ on 2.4.4), al menos en la versi´ on en la que el propio Wallis la escrib´ıa. Si el lector eval´ ua la funci´ on P (x) = sin(x)/x en x = π/2, podr´ a obtener, tras unas cuantas manipulaciones, que 1×3 3×5 5×7 7×9 2 = ··· π 22 42 62 82 (comp´ arese con las expresiones de la subsecci´ on 2.4.4). 19 Contra lo que podr´ıan sugerir estos primeros casos, no siempre aparece un 1 en el numerador. Por ejem−12 = π 12 691/638512875. La f´ ormula involucra los llamados n´ umeros de Bernoulli (v´ease el plo, ∞ n=1 n ejercicio 10.7.5). Las sumas con exponente impar son mucho m´ as complicadas. Para dar idea de lo poco que ∞ 1 umero irracional. Ni se sabe de ellas, no fue hasta 1978 cuando R. Ap´ery demostr´ o que k=1 k3 era un n´ siquiera eso se sabe para los valores p = 5, 7, . . . . La demostraci´ on de Ap´ery usaba, en realidad, m´etodos que eran ya conocidos por los matem´ aticos del siglo XVIII, y por Euler en particular. Van der Poorten titulaba su recensi´ on del Math. Intelligencer 1 (1979) de la siguiente manera: A proof that Euler missed. . . Ap´ ery’s proof of the irrationality of ζ(3). V´ease, por ejemplo, el art´ıculo de Antonio C´ ordoba Disquisitio Numerorum (La Gaceta de la RSME 4 (2001), no. 1).





(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

782

´ 10.3 EJERCICIOS DE LA SECCION 10.3.1 Supongamos que f (x) y g(x) son dos series de potencias que convergen en intervalos (−R, R) y (−M, M ), respectivamente. ¿D´ onde convergen las series de potencias αf (x) + βg(x) y f (x)g(x)? ¿Y f (x)/(1 − x)? Compru´ebese que las series de potencias xm f (x) y f (m) (x) convergen en el mismo intervalo que la f (x) original. 10.3.2 Compru´ebese que, dada una sucesi´ on de n´ umeros (an ),        an+1   an+1  n n     ≤ l´ım inf |an | ≤ l´ım sup |an | ≤ l´ım sup  l´ım inf  n→∞ n→∞ an  an  n→∞ n→∞ 10.3.3 Sea (an ) una sucesi´ on de n´ umeros que cumplen que |an | ≤ C M n , donde C y M son ciertas ∞ constantes positivas. Compru´ebese que la serie de potencias n=0 an xn tiene un radio de convergencia R ≥ 1/M . 10.3.4 Util´ıcese un argumento similar al del ejemplo 10.3.1 para comprobar que ∞ 

1 = 1, F F n=2 n−1 n+1

donde (Fn ) es la sucesi´ on de Fibonacci.

10.3.5 Sea (a0 , a1 , a2 , a3 , . . . ) una cierta sucesi´ on de n´ umeros reales para la que l´ımn→∞ an = L. yn ) dadas, para cada n ≥ 0, por (a) Consideremos, en primer lugar, las sucesiones (yn ) y ( n   n 1  1  n ak e yn = n yn = ak . k n+1 2 k=0

k=0

Obs´ervese que la primera es la sucesi´ on de las medias aritm´eticas, y la segunda, la sucesi´ on de lo que llamar´ıamos las medias bin´ omicas. Compru´ebese que el l´ımite de ambas sucesiones es L. (b) M´ as generalmente, consideremos unos n´ umeros Mn,k positivos que cumplen que (1) Mn,k = 0 si n k > n; (2) k=0 Mn,k = 1 para cada n; y (3) l´ımn→∞ Mn,k = 0 para cada k. Demu´estrese que la sucesi´ on ∞  yn = Mn,k ak tiende a L cuando n → ∞. k=0

(c) Ahora, dos promedios con claro sabor probabil´ıstico. Consideramos y(p) =

∞ 

p(1 − p)k ak

e

y(λ) =

k=0

∞  k=0

e−λ

λk ak , k!

donde 0 < p < 1 y λ > 0. Compru´ebese que l´ımp→0 y(p) = L. ¿Qu´e ocurre cuando p → 1? ¿Qu´e ocurre con y(λ) cuando λ → ∞?  10.3.6 Demostraci´ on del Lema de Abel (Lema10.2). Sea f (x) = n an xn una serie de potenon (cn ) dada cias con radio n de convergencia 1 y supongamos que n an = A. Consideramos la sucesi´ por cn = k=0 ak . Obs´ervese que l´ımn→∞ cn = A. (a) Util´ıcese que a0 = c0 y an = cn − cn−1 si n ≥ 1 para comprobar que, para cualquier n ≥ 1, n  k=0

ak xk = (1 − x)

n−1 

ck xk + cn xn

para |x| < 1.

k=0

(versi´ on preliminar 29 de octubre de 2008)

10.3. Series de potencias y funciones generatrices Ded´ uzcase que f (x) = (1 − x)

∞ 

783

cn xn .

n=0

(b) Util´ıcese la representaci´ on anterior para deducir, finalmente, que l´ımx↑1 f (x) = A.  n 10.3.7 Partimosdel Lema de Abel (Lema 10.2): si es una serie de potencias con radio de  n annx  convergencia 1 y n an converge, entonces l´ımx↑1 n an x = n an .  n (a) Sea ahora  g(x) = n bn x una serie de potencias con radio de convergencia R > 0. Supongamos que n bn Rn converge. Compru´ebese que f (x) = g(Rx) es una serie de potencias  con radio de convergencia 1. Apl´ıquese el lema de Abel a f (x) para comprobar que l´ımx↑R g(x) = n bn Rn .   (b) Digamos que g(x) = n bn xn tiene radio de convergencia 1 y que n bn (−1)n converge. Util´ıcese  un argumento similar al del apartado anterior para comprobar que l´ımx↓−1 g(x) = n bn (−1)n . 10.3.8 Util´ıcese la f´ ormula de Taylor para encontrar los siguientes desarrollos en series de potencias: a) b) c) d)

x3 x4 x2 + − + ··· (v´ alida para −1 < x ≤ 1); 2 3 4 x3 x5 x7 sin(x) = x − + − + ··· (v´ alida para todo x); 3! 5! 7! x4 x6 x2 + − + ··· (v´ alida para todo x); cos(x) = 1 − 2! 4! 6! 2 (x log(a))3 (x log(a)) ax = 1 + x log(a) + + + ··· con a > 0 (v´ alida para todo x). 2! 3! log(1 + x) = x −

10.3.9 Util´ıcese el apartado a) del ejercicio anterior para comprobar que ∞ ∞   1 (−1)n+1 . = log(2) = n 2n n n=1 n=1

Ambas series infinitas dan, como resultado, log(2) = 0.6931471806 . . . Pero quiz´ as el lector quiera entretenerse en comprobar computacionalmente el diferente grado de aproximaci´ on que dan, sumando, por ejemplo, los 100 primeros t´erminos de las dos series. 10.3.10 (a) Sabiendo que 1 d arctan(x) = , dx 1 + x2 compru´ebese que arctan(x) =

∞  (−1)n 2n+1 x 2n + 1 n=0

 (b) La serie num´erica n (−1)n /(2n + 1) converge (recu´erdese el teorema 10.1). Apl´ıquese el lema de Abel a la funci´ on arcotangente para obtener el siguiente m´etodo de c´ alculo del n´ umero π:   1 1 1 π = 4 1 − + − + ··· 3 5 7 10.3.11 Pru´ebese que

∞  (−1)n+1 π2 . = n2 12 n=1

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

784

10.3.12 Obt´engase el desarrollo de (1 ± x)m/2 , con m entero.  1 2 10.3.13 Otra demostraci´ on de Euler de que ∞ n=1 n2 π /6. Partimos del siguiente polinomio de grado m:  m   2m + 1 (−1)j xm−j . Pm (x) = 2j + 1 j=0

Utilizando la f´ ormula de de Moivre (p´ agina 28) y la f´ ormula del binomio, se comprueba que ei (2m+1) θ = cos((2m + 1)θ) + i sin((2m + 1)θ) , 2m+1  2m + 1 i (2m+1) θ 2m+1 = (cos θ + i sin θ) = (cos θ)2m+1−k (sin θ)k ik . e k k=0

(a) Comp´ arense las partes imaginarias de las dos f´ ormulas anteriores para deducir que sin((2m + 1)θ) = (sin θ)2m+1 Pm (cot2 θ) . (b) Ded´ uzcase que los n´ umeros (reales)   kπ 2 , rk = cot 2m + 1 son las m ra´ıces del polinomio Pm (x). (c) Compru´ebese que Pm (x) = (2m + 1)

k = 1, . . . , m

m 

(x − rk ) .

k=1

(d) Ded´ uzcase, a partir del coeficiente de xm−1 de Pm (x), que   m m   m (2m − 1) kπ 2 = . rk = cot 2m + 1 3 k=1

k=1

(e) Ahora vamos a utilizar las dos siguientes estimaciones de tama˜ no de la funci´ on cotangente. Por un lado, 1 (si θ ∈ (0, π/2)). cot θ < θ Por otro, como sin θ < θ si θ ∈ (0, π/2), se tiene que cot2 θ =

1 1 cos2 θ = 2 2 − 1 > θ2 − 1 sin θ sin θ

(si θ ∈ (0, π/2)).

Util´ıcense estas dos estimaciones en la identidad del apartado anterior para deducir que m

π 2 4 m(m + 1) π 2 2m (2m − 1)  1 < < . 6 (2m + 1)2 k2 6 (2m + 1)2 k=1

(g) Por u ´ltimo, p´ asese al l´ımite m → ∞ en las desigualdades del apartado anterior para obtener el resultado deseado. (versi´ on preliminar 29 de octubre de 2008)

10.4. Resoluci´on de ecuaciones de recurrencia

10.4.

785

Resoluci´ on de ecuaciones de recurrencia

Ya tenemos la t´ecnica, y es hora de aplicarla a un problema concreto, como es el de la resoluci´on de ecuaciones de recurrencia. Ya vimos, en el cap´ıtulo 6, algunos m´etodos, de otra ´ındole, y nos disponemos ahora a tratarlas con el lenguaje de las funciones generatrices. on de recurrencia El punto de partida es una sucesi´ on (an ) que verifica una cierta ecuaci´ (y unas condiciones iniciales). Para resolver la recurrencia, esto es, para obtener una f´ ormula para an , seguiremos los siguientes pasos: primero, codificaremos la sucesi´on (an ) con una funci´ on generatriz, digamos f (x). El segundo paso consistir´a en utilizar la informaci´ on disponible sobre la sucesi´on (ecuaci´on de recurrencia y valores iniciales) para obtener una ecuaci´ on (algebraica, quiz´ as diferencial) para f (x). Si somos capaces de resolverla, tendremos una expresi´ on de f (x). Nos interesa obtener una f´ ormula para an , as´ı que el paso final ser´ a desarrollar en serie de potencias la funci´ on f (x). Todo esto se puede entender como un proceso puramente formal (as´ı lo haremos en la secci´on 10.7). No hay, por ejemplo, evaluaciones de la funci´ on en punto alguno, as´ı que podr´ıamos obviar toda menci´ on a la convergencia de las series de potencias que vayan apareciendo. A. Una sucesi´ on, un par´ ametro Parte de este proceso ya lo hicimos, para la sucesi´on de n´ umeros de Fibonacci, en la subsecci´on 10.1.1. As´ı que volvamos a tratar este caso, como ejemplo de una ecuaci´on de recurrencia lineal, homog´enea y con coeficientes constantes. Ejemplo 10.4.1 Consideremos la sucesi´ on de n´ umeros de Fibonacci (Fn ) dada por F0 = 0 y F1 = 1 y Fn = Fn−1 + Fn−2 para cada n ≥ 2. on generatriz, Empezamos asociando a los Fn su funci´ f (x) =

∞ 

Fn xn .

n=0

Transferimos ahora la informaci´ on de la ecuaci´ on de recurrencia y las condiciones iniciales a la funci´ on generatriz. Sus dos primeros coeficientes est´an fijados y los siguientes, del tercero en adelante, los reescribimos siguiendo la ecuaci´ on: f (x) = F0 + F1 x+ F2 x2 + F3 x3 + F4 x4 + · · · = !" # !" # !" # F2 x3 F3 x4 ··· F1 x2 + + + F1 x3 F2 x4 ··· F0 x2

 2 3 4 2 = F0 + F1 x + F1 x + F2 x + F3 x + · · · + F0 x + F1 x3 + F2 x4 + · · · Ahora, con ayuda de las reglas de desplazamiento de coeficientes, identificamos las dos series de potencias que han aparecido. Lo que queda, como el lector deber´ a comprobar, es que
 f (x) = F0 + F1 x + x [f (x) − F0 ] + x2 f (x) = x + f (x) x + x2 . (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

786

El lector que se encuentre c´omodo con la notaci´ on de los sumatorios puede hacer todo este proceso manipulando las series directamente: f (x) =

∞ 

Fn xn = F0 + F1 x +

n=0

= F0 + F1 x +

∞ 

∞ 

Fn xn = F0 + F1 x +

n=2

Fn−1 xn +

n=2 ∞ 

= F0 + F1 x + x

∞ 

Fn−2 xn = F0 + F1 x + x

n=1

∞ 

(Fn−1 + Fn−2 ) xn

n=2

n=2

Fn xn + x2

∞ 

∞ 

Fn−1 xn−1 + x2

n=2

∞ 

Fn−2 xn−2

n=2

Fn xn = F0 + F1 x + x [f (x) − F0 ] + x2 f (x)

n=0

Ahora que tenemos una ecuaci´on (algebraica) para f (x), la resolvemos. Aqu´ı, simplemente, se trata de “despejar” la f (x): 
f (x) = x + f (x) x + x2

=⇒


 f (x) 1 − x − x2 = x

=⇒

f (x) =

x 1 − x − x2

(esta expresi´ on es v´alida, en principio, en |x| < 1/τ ). Sigamos. Lo que nos interesan son los coeficientes de f (x), esto es, los n´ umeros de Fibo2 an ah´ı, encerrados en las tripas de la funci´ on x/(1−x−x ). S´ olo hay que sacarlos nacci Fn . Est´ a la luz, desarrollando la funci´ on en serie de potencias. Ahora sabemos hacerlo, aplicando el m´etodo de fracciones simples. La ecuaci´on 1 − x − x2 = 0 tiene dos ra´ıces, √ √ − 5−1 5−1 y β= , α= 2 2 de forma que 1 − x − x2 = −(x − α)(x − β) (cuidado con los signos). Y podremos escribir A B −x x = + . = 2 1−x−x (x − α)(x − β) (x − α) (x − β) √ Igualando coeficientes de los numeradores, determinamos A y B, que resultan ser A = ( 5 − √ 5)/10 y B = −( 5 + 5)/10. Con ellos, y tras ciertas manipulaciones, obtenemos que x = 1 − x − x2

√ √ √ √

∞  5+ 5 1 5−5 1 5+5 1 5− 5 1 − = + xn . 10 x − α 10 x − β n=0 10 αn+1 10 β n+1

De esta expresi´on, y utilizando los valores de α y β, leemos directamente el valor de los coeficientes: √  √  √  √  5 1+ 5 n 5 1− 5 n − , Fn = 5 2 5 2 la f´ ormula de Binet que ya conoc´ıamos (v´ease el ejemplo 6.2.1). (versi´ on preliminar 29 de octubre de 2008)

10.4. Resoluci´on de ecuaciones de recurrencia

787

Podr´ıamos haber intentado un enfoque alternativo, aprovechando que f (x) tiene un aspecto muy semejante a la serie geom´etrica: ∞  x x = x = (x + x2 )k . 1 − x − x2 1 − (x + x2 ) k=0

Si ahora utilizamos el teorema del binomio, podremos desarrollar el par´entesis interior: $ k   % $ k   % ∞ ∞   k   k x = x xk−l (x2 )l = x xk+l 1 − x − x2 l l k=0 l=0 k=0 l=0 % % $ $ n    ∞ ∞    n − l  k xn = xn+1 . = x l l l≤k n=0

n=0

l+k =n

l=0

As´ı llegamos a una f´ormula para el coeficiente que acompa˜ na a xn+1 en el desarrollo de f (x) que es, no puede ser otro, el n´ umero Fn+1 :  n   n−l , Fn+1 = l l=0

♣

expresi´on que ya obtuvimos, por ejemplo, en la subsecci´ on 6.3.5.

Los mismos argumentos que hemos utilizado aqu´ı se aplican a cualquier ecuaci´ on lineal homog´enea, con coeficientes constantes y grado k. Subamos el grado de dificultad: una ecuaci´on de recurrencia lineal y con coeficientes constantes, pero con un t´ermino no homog´eneo. Ejemplo 10.4.2 Queremos hallar la sucesi´ on de n´ umeros (an ) que verifica que a0 = 0, a1 = 1 y an = an−1 + an−2 + n si n ≥ 2. on que tenemos Construimos la funci´ on f (x) que genera los (an ) y traducimos la informaci´ sobre estos n´ umeros en una ecuaci´ on sobre f (x): f (x) = a0 + a1 x +

∞ 

n

(an−1 + an−2 + n)x = x + x

n=2

= x + x f (x) + x2 f (x) +



n−1

an−1 x

2

+x

n=2



1 −x (1 − x)2

∞ 

∞  n=2

n−2

an−2 x

+

∞ 

nxn

n=2

.

Hemos utilizado aqu´ı que conocemos bien la funci´ on asociada a la sucesi´on cuyo coeficiente n-´esimo es, precisamente, n. Ya tenemos la ecuaci´on para f (x), f (x) = x f (x) + x2 f (x) +

1 , (1 − x)2

de la que obtenemos que 1 . (1 − x)2 (1 − x − x2 ) Los coeficientes de esta funci´on se pueden obtener desarrollando en serie de potencias, utilizando fracciones simples, ejercicio que dejamos al lector. ♣ f (x) =

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

788

As´ı que, si tenemos t´erminos no homog´eneos, todo lo que necesitaremos ser´a sumar (obtener una expresi´ on anal´ıtica de) la o las series de potencias que provengan de la parte no homog´enea. Sin embargo, el que la ecuaci´ on siga siendo lineal de coeficientes constantes nos asegura que el tipo de ecuaci´ on que obtendremos para f (x) seguir´ a siendo algebraica. Para ver lo que puede ocurrir al manejar ecuaciones lineales con coeficientes no constantes, consideremos el siguiente ejemplo: Ejemplo 10.4.3 Consideramos la sucesi´ on de n´ umeros (an ) dada por a0 = 1 y (n + 1) an+1 = 3 an +

2n , n!

para cada n ≥ 0.

Como siempre, empezamos introduciendo la funci´on generatriz f (x) asociada a la sucesi´on: f (x) =

∞ 

an xn .

n=0

Tal como viene escrita la recurrencia, conviene no “despejar” el t´ermino de mayor ´ındice (en alida para cada este caso, an+1 ), sino trabajar directamente con ella. Como la recurrencia es v´ n ≥ 0, se cumplir´ a que ∞ 

(n + 1) an+1 xn = 3

n=0

∞ 

an xn +

n=0

∞  2n n=0

n!

xn .

Si identificamos las series que aparecen (la propia f (x), su derivada y la funci´ on e2x ), obtenemos la ecuaci´on que debe verificar la funci´ on generatriz: f  (x) = 3 f (x) + e2x . ´ Esta es una ecuaci´ on diferencial para f (x), cuya soluci´ on general viene dada20 por f (x) = C e3x − e2x , on extra donde C es una constante. El que a0 = 1 exige que f (0) = 1; y con esta informaci´ podemos concluir que f (x) = 2 e3x − e2x . Desarrollar esta funci´ on en serie de potencias, y con ello, obtener los n´ umeros an , es sencillo: f (x) = 2

∞  3n n=0

n!

xn −

∞  2n n=0

n!

xn ,

de donde obtenemos

1 (2 × 3n − 2n ) , n! abamos buscando. la expresi´on de los an que and´ an =

20


= f (x) e

♣




Se puede emplear, por ejemplo, un truco de factor integrante. Obs´ervese que f (x)e−3x





−3x

− 3f (x)e−3x = e−3x f  (x) − 3f (x) = e−3x e2x = e−x ,

Integrando esta expresi´ on, llegamos a la soluci´ on general del texto.

(versi´ on preliminar 29 de octubre de 2008)

10.4. Resoluci´on de ecuaciones de recurrencia

789

En algunas de las ecuaciones de recurrencia que vimos en la secci´on 6.1, un cierto t´ermino de la sucesi´on depend´ıa de todos los anteriores: umero Ejemplo 10.4.4 En el ejemplo 6.1.11 ve´ıamos que los n´ umeros Mn , que contaban el n´ de posibles montones con n barriles en la primera fila, cumpl´ıan que Mn = 1 +

n−1 

(n − j)Mj

para cada n ≥ 2,

j=1

junto con la condici´ on inicial M1 = 1. Consid´erese la funci´on generatriz M (x) asociada a la sucesi´on (Mn ). Utilizamos la condici´on inicial y la ecuaci´ on de recurrencia para escribir que M (x) =

∞ 

∞  n−1 ∞ ∞ n−1       (n − j)Mj xn = x + xn + (n − j)Mj xn 1+

Mn xn = x +

n=1

=x+

=

n=2

x2 1−x

x + 1−x

+

∞ 

∞  j=1

Mj

(n − j)xn =

n=j+1 ∞  j k

Mj x

j=1

n=2

j=1 ∞ 

kx =

k=1

x + 1−x

x x + 1 − x (1 − x)2

∞ 

Mj xj

j=1 ∞ 

n=2 j=1 ∞ 

(n − j)xn−j

n=j+1

x x + M (x) , 1 − x (1 − x)2

Mj xj =

j=1

de donde

x(1 − x) . 1 − 3x + x2 Ya s´olo resta desarrollar en serie de potencias (o revisar el ejercicio 10.2.6) para concluir que ♣ Mn = F2n−1 para cada n ≥ 1, donde (Fn ) es la sucesi´on de Fibonacci. M (x) =

Si la ecuaci´ on no es lineal, las dificultades aumentan enormemente, y s´olo en casos muy particulares vamos a disponer de m´etodos de resoluci´on expl´ıcita. Por su especial relevancia en cuestiones combinatorias, veamos el siguiente ejemplo. Ejemplo 10.4.5 La sucesi´ on de los n´ umeros de Catalan (Cn ) viene definida por Cn = C0 Cn−1 + C1 Cn−2 + · · · + Cn−2 C1 + Cn−1 C0 =

n−1 

Ck Cn−1−k

para cada n ≥ 1,

k=0

si convenimos en que C0 = 1. En el ejemplo 3.1.3 obtuvimos ya una f´ ormula para estos n´ umeros. Ahora abordamos la cuesti´on utilizando funciones generatrices. Si C(x) es la funci´ on generatriz de la sucesi´ on (Cn ),     ∞ ∞ k−1 ∞ k−1      Ck xk = 1 + Cj Ck−1−j xk = 1 + x Cj Ck−1−j xk−1 C(x) = k=0

= 1+x

∞  n  n=0

k=1

j=0



k=1

j=0

Cj Cn−j xn == 1 + x C 2 (x) ,

j=0

pues la u ´ltima suma entre par´entesis es el coeficiente n-´esimo de la funci´on C 2 (x). (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

790

Esta ecuaci´ on de segundo grado (para C(x)) tiene dos posibles soluciones: √ √ 1 − 1 − 4x 1 + 1 − 4x o bien . 2x 2x El que C0 = 1, esto es, C(0) = 1, descarta la primera posibilidad (pero no la segunda, como se puede comprobar, por ejemplo, con ayuda de la regla de L’Hˆ opital). As´ı que la funci´ on generatriz de los n´ umeros de Catalan es la que aparece a la derecha. Ahora s´olo tenemos que irnos al ejemplo 10.3.3 y revisar el c´ alculo con el teorema del binomio que hicimos all´ı para tener la f´ ormula para los n´ umeros de Catalan. ♣ B. Una sucesi´ on, dos par´ ametros Como ya hemos visto en ocasiones, las ecuaciones de recurrencia pueden involucrar m´as de un par´ ametro: es el caso de las que obtuvimos para los coeficientes bin´omicos, los distintos n´ umeros de Stirling, etc. Nos planteamos ahora c´ omo tratar estas ecuaciones mediante las funciones generatrices. Para ilustrarlo, recurriremos a los n´ umeros C(n, k), que cuentan el n´ umero de subconjuntos de tama˜ no k que podemos extraer de {1, . . . , n}, y de los que ya disponemos de una f´ ormula expl´ıcita, la dada por los coeficientes bin´omicos. Digamos que n y k son enteros no negativos. Recordemos que las condiciones iniciales eran C(n, 0) = 1 y C(n, n) = 1 (el caso (C(0, 0) = 1 es, simplemente, una convenci´on). La ecuaci´ on de recurrencia, si n ≥ 1 y 0 < k ≤ n, es C(n, k) = C(n − 1, k − 1) + C(n − 1, k) . on generatriz Podemos empezar considerando, para cada n fijo, la funci´ fn (x) =

∞ 

C(n, k) xk .

k=0

El caso n = 0 es especial: f0 (x) = C(0, 0) = 1. Para n ≥ 1, ∞ ∞     k C(n, k) x = C(n, 0) + C(n − 1, k − 1) + C(n − 1, k) xk fn (x) = k=0

= 1+x

∞ 

k=1 k−1

C(n − 1, k − 1) x

k=1

= 1+x

∞  j=0

C(n − 1, j) xj +

∞ 

+

∞ 

C(n − 1, k) xk

k=1

C(n − 1, k) xk − C(n − 1, 0) ,

k=0

de donde obtenemos una ecuaci´on de recurrencia para las funciones fn (x): fn (x) = (1 + x) fn−1 (x)

para cada n ≥ 1.

Si ahora iteramos esta relaci´on hasta llegar al valor inicial, f0 (x), obtenemos que fn (x) = (1 + x)n . Y utilizando la f´ ormula del binomio, obtenemos la expresi´on habitual de los C(n, k). (versi´ on preliminar 29 de octubre de 2008)

10.4. Resoluci´on de ecuaciones de recurrencia

791

Aunque tambi´en podr´ıamos considerar, para cada k fijo, la siguiente funci´ on generatriz: gk (x) =

∞ 

C(n, k) xn .

n=0

De nuevo, el caso k = 0 es especial: g0 (x) =

∞ 

C(n, 0) xn =

n=0

∞ 

xn =

n=0

1 . 1−x

Para k ≥ 1, gk (x) =

∞ 

C(n, k) xn = C(0, k) +

n=0 ∞ 

= x = x

n=1 ∞ 

∞    C(n − 1, k − 1) + C(n − 1, k) xn n=1

C(n − 1, k − 1) xn−1 + x C(n, k − 1) xn +

n=0

∞ 

∞ 

C(n − 1, k) xn−1

n=1

C(n, k) xn ,

n=0

de donde gk (x) = x gk−1 (x) + x gk (x) ; esto es,

x gk−1 (x) para cada k ≥ 1. 1−x De nuevo, iterando, llegamos a que 2 k   x x x xk = gk−2 (x) = · · · = g0 (x) = . gk (x) = gk−1 (x) 1−x 1−x 1−x (1 − x)k+1 gk (x) =

De manera que   ∞  ∞  ∞    xk k + j j  k + j j+k  n n k =x = x = x x . gk (x) = (1 − x)k+1 k k k j=0

j=0

n=k

Parece que hemos obtenido el mismo resultado, pero fij´emonos en que          n n n n n ←→ , , ,..., , 0, 0, . . . , fn (x) = (1 + x) 0 1 2 n mientras que xk gk (x) = (1 − x)k+1

 ←→

       k k+1 k+2 0, 0, . . . , 0, , , ,... , k k k

angulo de Para cada n fijo, fn (x) codifica los coeficientes bin´omicos de un “piso” del tri´ Tartaglia (en realidad, un n´ umero finito de coeficientes). Para k fijo, gk (x) contiene los de una diagonal (por eso es una verdadera sucesi´ on infinita de n´ umeros). (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

792

En un alarde de valent´ıa y entusiasmo, podemos intentar un tercer enfoque. Se trata de codificar todos los coeficientes bin´omicos a la vez, aunque para ello necesitaremos recurrir a un objeto m´ as general, como es una funci´ on de dos variables, digamos x e y: F (x, y) =

∞  ∞ 

C(n, k) xn y k .

n=0 k=0

Para obtener una expresi´ on manejable de esta funci´on, utilizamos de nuevo la informaci´on sobre los C(n, k), separando los casos en que los ´ındices valgan 0: F (x, y) =

∞  k=0

k

C(0, k) y + 

= 1+

= =

∞ 

n

C(n, 0) x +

n=1

1 1−x

1 +xy 1−x

∞  ∞ 

C(n, k) xn y k

n=1 k=1

 ∞ ∞   n k −1 + C(n − 1, k − 1) x y + C(n − 1, k) xn y k n,k=1 ∞ 

C(n, k) xn y k + x

n,k=1 ∞ ∞  

C(n, k) xn y k

n=0 k=1

n,k=0

  1 1 + x y F (x, y) + x F (x, y) − , 1−x 1−x

de donde, despejando, 1 . 1 − x − xy Para desarrollarla en serie, aprovechamos que es una serie geom´etrica (y luego utilizamos el teorema del binomio): n   ∞ ∞ ∞ ∞ n       n k  n n k 1 n n n n = (x + xy) = x (1 + y) = x y = x y , 1 − x − xy k k n=0 n=0 n=0 n=0 k=0 k=0
 de donde, por comparaci´ on, deducimos que C(n, k) = nk . El uso de funciones generatrices en dos variables es muy u ´til en ciertos contextos (v´ease, por ejemplo, el cap´ıtulo 13). F (x, y) =

C. Dos sucesiones, un par´ ametro (sistemas de ecuaciones) Veamos por u ´ltimo c´ omo se manejan, con funciones generatrices, sistemas de ecuaciones de recurrencia. El m´etodo que seguiremos es an´alogo al utilizado para una u ´nica ecuaci´ on. Ahora necesitaremos una funci´ on generatriz por cada sucesi´ on de n´ umeros de inter´es, y el sistema de ecuaciones de recurrencia se transformar´a en un sistema de ecuaciones para esas funciones generatrices. Al resolverlo obtendremos las expresiones de las funciones, para, finalmente, desarrollar en serie cada una de ellas. Lo vemos en un ejemplo. Ejemplo 10.4.6 Queremos encontrar las sucesiones (an ) y (bn ) que verifican que  an = 3 an−1 + bn−1 , para cada n ≥ 1, bn = 2 an−1 + bn−1 , junto con las condiciones iniciales a0 = 1, b0 = 1. (versi´ on preliminar 29 de octubre de 2008)

10.4. Resoluci´on de ecuaciones de recurrencia

793

´ En la subsecci´ on 6.2.3 vimos c´omo resolver estos sistemas con las herramientas del Algebra lineal. Introducimos ahora las funciones generatrices asociadas a las sucesiones (an ) y (bn ). A(x) =

∞ 

an xn

y

B(x) =

n=0

∞ 

bn xn .

n=0

La primera ecuaci´ on, escrita en t´erminos de estas dos funciones, viene a ser A(x) = a0 +

∞  n=1

(3an−1 + bn−1 ) xn = 1+3x

∞ 

an−1 xn−1 +x

n=1

∞ 

bn−1 xn−1 = 1+x A(x)+x B(x) .

n=1

Procediendo de manera an´ aloga con la segunda ecuaci´ on, llegamos a que las funciones generatrices verifican el sistema de ecuaciones siguiente:  A(x)(1 − 3x) = 1 + xB(x) , B(x)(1 − x) = 2x A(x) (recu´erdese que las “inc´ognitas” son aqu´ı las series A(x) y B(x)). Resolviendo este sistema obtenemos que 2x 1−x y B(x) = 2 . A(x) = 2 x − 4x + 1 x − 4x + 1 Finalmente, desarrollamos en serie de potencias para obtener la soluci´on del problema: √ √  ∞   √ n 3− 3 √ n 3+ 3 (2 + 3) + (2 − 3) xn A(x) = 6 6 n=0 √  ∞ √  √ n √ n 3 3 (2 + 3) − (2 − 3) xn B(x) = 3 3 n=0 Los coeficientes de A(x) y de B(x) son, respectivamente, las sucesiones (an ) y (bn ) que satisfacen el sistema de ecuaciones y las condiciones iniciales. ♣

´ 10.4 EJERCICIOS DE LA SECCION 10.4.1 Para cada n ≥ 1, sea an el n´ umero de n-listas con s´ımbolos {0, 1, 2, 3} que tienen un n´ umero uzcase, utilizando impar de ceros. Compru´ebese que a1 = 1 y que an+1 = 2an +4n para cada n ≥ 1. Ded´ funciones generatrices, que an = 12 (4n − 2n ). 10.4.2 Consideremos la sucesi´ on de n´ umeros (an )∞ n=0 que satisface la recurrencia:   100 an = an−2 + , n ≥ 2, n junto con las condiciones iniciales a0 = 1 y a1 = 100. (a) Calc´ ulese la funci´ on generatriz de esta sucesi´ on. (b) Escr´ıbase una f´ ormula para an y calc´ ulese a200 .

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

794

10.4.3 Consid´erense las dos siguientes sucesiones de n´ umeros:

a1 = 1 A0  A ak = 1 + ak−1 + k−1 a para cada k ≥ 2. n j=1 j

=  1 n = k=0 kAn−k ,

n ≥ 1.

Obt´enganse las respectivas funciones generatrices y compru´ebese que an = An = F2n para cada n ≥ 1. 10.4.4 Para cada n, k ≥ 0, llamemos b(n, k) al n´ umero de subconjuntos de {1, 2, . . . , n} de tama˜ no k que no contienen enteros consecutivos (esta cuesti´ on ya la tratamos en el ejercicio 3.1.15 y, con un lenguaje distinto, pero equivalente, en la subsecci´ on 6.3.5). N´ otese que b(n, k) = 0 si k > n y que b(n, 0) = 1 si n ≥ 1, b(0, k) = 0 si k ≥ 1 y b(n, 1) = n si n ≥ 1. Definamos b(0, 0) = 1. (a) Pru´ebese que b(n, k) = b(n − 2, k − 1) + b(n − 1, k) si n ≥ 2, k ≥ 1. (b) Llamemos Fk (x) a la funci´ on generatriz de los b(n, k) para cada k fijo. Compru´ebese que F0 (x) =

1 , 1−x

F1 (x) =

x , (1 − x)2

Fk (x) =

x2 Fk−1 (x), 1−x

si k ≥ 2.

(c) Resu´elvase la recurrencia para las funciones Fk (x) y ded´ uzcase que   n−k+1 b(n, k) = . k 10.4.5 Para k ≥ 1 fijo, consideramos la sucesi´ on de n´ umeros de Stirling de segunda especie (S(n, k))∞ n=1 y su funci´ on generatriz asociada: Fk (x) =

∞ 

S(n, k)xn

(n´ otese que la suma empieza realmente en n = k).

n=1

(a) Pru´ebese, utilizando la ecuaci´ on de recurrencia que verifican los n´ umeros de Stirling de segunda especie, S(n, k) = S(n − 1, k − 1) + kS(n − 1, k), que x y Fk (x) = x Fk−1 (x) + k x Fk (x) si k ≥ 2. F1 (x) = 1−x (b) Resu´elvase la recurrencia y, utilizando fracciones simples, verif´ıquese que Fk (x) = xk

k  j=1

k  1 γj = xk , 1 − jx 1 − jx j=1

donde

k−j

γj = (−1)

j k−1 . (j − 1)! (k − j)!

(c) Desarr´ ollense los t´erminos 1/(1−jx) para deducir la habitual f´ ormula para los n´ umeros de Stirling   k k (−1)k  S(n, k) = (−1)m mn . m k! m=1 10.4.6 Vamos ahora a cambiar el punto de vista, para considerar, para n ≥ 1 fijo, la funci´ on generatriz (n´ o tese que ahora es k el ´ ı ndice de la sucesi´ on), (en realidad, un polinomio) de la sucesi´ on (S(n, k))∞ k=1 Gn (x) =

∞ 

S(n, k) xk .

k=1

En lugar de seguir el procedimiento del ejercicio anterior, vamos a considerar la funci´ on Tn (x) =

∞  mn m x . m! m=1

(versi´ on preliminar 29 de octubre de 2008)

10.4. Resoluci´on de ecuaciones de recurrencia (a) Util´ıcese la identidad kn =

k    k

j

j=1

795

j! S(n, j)

(v´ease el ejemplo 3.3.3) para demostrar que Tn (x) = Gn (x) ex . (b) As´ı que Gn (x) = e−x Tn (x) (¡curioso!, el producto de dos series infinitas como ex y Tn (x) resulta ser un polinomio). Util´ıcese esta relaci´ on para obtener la f´ ormula para los S(n, k) del ejercicio 10.4.5. (c) El n´ umero de Bell B(n), B(n) =

n 

para cada n ≥ 1,

S(n, k)

k=1

cuenta el n´ umero de particiones en bloques no vac´ıos del conjunto {1, 2, . . . , n}, Sustit´ uyase x = 1 en la expresi´ on del apartado (b) para obtener la f´ ormula de Dobinski: ∞

B(n) =

1  jn e j=1 j!

para cada n ≥ 1,

que permite calcular B(n) en t´erminos de una serie infinita que converge muy r´ apidamente. Por ejemplo, B(10) = 115975, mientras que la suma de los 15 primeros t´erminos de la serie da ≈ 115974, 978. 10.4.7 Util´ıcese el ejercicio anterior para comprobar que, si definimos B(0) = 1, ∞  B(n) n x = exp (ex − 1) . n! n=0

10.4.8 Consideremos los n´ umeros de Bell ordenados: n    B(0) = 1 y B(n) = S(n, k) k!

para cada n ≥ 1.

k=1

Estos n´ umeros verifican la ecuaci´ on de recurrencia siguiente (v´ease el ejercicio 3.3.4): n    n   B(n − j) para cada n ≥ 1 B(n) = j j=1 (a) Compru´ebese que, si llamamos  B(x) = entonces

∞   B(n) n x , n! n=0

  = 2B(x) − 1. ex B(x)

(b) As´ı que 1 . 2 − ex Desarr´ ollese en serie de potencias esta funci´ on para obtener la siguiente f´ ormula “a la Dobinski”:  B(x) =

 B(n) =

∞  jn . 2j+1 j=0

(versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

796

10.5.

Otras aplicaciones

La utilidad de las funciones generatrices no se limita a la resoluci´ on de ecuaciones de recurrencia. Se prestan tambi´en al c´alculo de sumas (ya hemos visto alg´ un ejemplo de ello), al de medias, desviaciones est´andar (en general, momentos de una sucesi´ on de n´ umeros; estos c´alculos los veremos en detalle, y con el lenguaje probabil´ıstico correspondiente, en el cap´ıtulo 11); e incluso permiten entender de otra manera el principio de inclusi´ on/exclusi´ on (y versiones m´as generales de ´el). Ve´amoslo.

10.5.1.

El m´ etodo curalotodo

En p´ aginas anteriores hemos conseguido calcular el valor de diversas sumas. En ocasiones, utilizando las reglas de manipulaci´ on de funciones generatrices (v´eanse algunos ejemplos de la secci´on 10.2); en otras, evaluando ciertas funciones generatrices en x = 1, quiz´ as apelando al Lema de Abel (v´eanse, por ejemplo, varios ejercicios de la secci´on 10.3). Lo que vamos a proponer aqu´ı es un procedimiento “mec´anico” para obtener el valor de sumas del tipo  bkn . an = k

Para no perder generalidad, admitimos que los n´ umeros bkn puedan ser expresiones dependientes del ´ındice de sumaci´ on k, e incluso de n. Tampoco fijamos a priori los l´ımites de sumaci´on, que podr´ıan depender de n. El paso clave del m´etodo que a continuaci´ on presentamos, y al que nos referiremos como on, que por cierto hemos el m´ etodo curalotodo21 , es el intercambio en el orden de sumaci´ empleado ya en varias ocasiones en p´aginas anteriores. Este procedimiento, una gu´ıa ordenada de c´omo utilizar todas nuestras habilidades con las funciones generatrices para la evaluaci´on de sumas, consta de los siguientes pasos: on generatriz, 1. Empezamos, por supuesto, codificando la sucesi´ on (an ) con una funci´  n f (x) = n an x .  n 
 2. Funci´ on que reescribimos como f (x) = n k bkn x . 3. Con las precauciones que cada caso requiera, procedemos a intercambiar el orden de sumaci´on:  bkn xn . f (x) = n

k

4. Identificamos la serie de potencias interior y obtenemos una funci´ on (que quiz´ as dependa de k) que llamamos gk (x):  gk (x). f (x) = k

5. Hecho esto, evaluamos la suma de funciones para conseguir una expresi´ on para f (x). 6. El paso final consiste en desarrollar en serie de potencias la funci´ on f (x) para obtener los an , sus coeficientes. 21

En homenaje poco disimulado al snake oil method de Wilf.

(versi´ on preliminar 29 de octubre de 2008)

10.5. Otras aplicaciones

797

Ve´amoslo en acci´on en un primer ejemplo sencillo. Ejemplo 10.5.1 Calculemos de nuevo la conocida suma an = Empezamos con f (x) =

∞ 

n

k=0 k.

 ∞  n  an x = k xn . n

n=0

n=0

k=0

Ahora intercambiamos el orden de sumaci´ on. Estamos sumando primero en k, con 0 ≤ k ≤ n, y luego en n, con 0 ≤ n ≤ ∞. Al cambiar el orden, sumaremos primero en n (y, por tanto, el ´ındice n deber´ a cumplir que k ≤ n ≤ ∞) y luego en k, con 0 ≤ k ≤ ∞. El resto son manipulaciones bien conocidas: f (x) =

∞  k=0

k

∞ 

xn =

n=k

∞ 

k xk

k=0

∞ 

xn−k =

n=k

∞ 

k xk

k=0

∞ 

xn =

n=0

∞

1  k kx . 1−x k=0

De nuevo esta serie de potencias es conocida, es la que obtenemos al aplicar x d/dx a la serie b´ asica 1/(1 − x):   ∞ 1 1 x 1  k x kx = = . f (x) = 1−x 1−x 1−x (1 − x)3 k=0

Ya tenemos una expresi´on expl´ıcita de f (x), que desarrollamos serie de potencias:     ∞  ∞  ∞  ∞   n + 3 − 1 n  n + 2 n+1  k + 1 k  k + 1 k x =x = x = x x = x . (1 − x)3 3−1 2 2 2 n=0

n=0

k=1

k=0

De aqu´ı deducimos, finalmente, el bien conocido resultado ak =


k+1 2

= k(k + 1)/2.

♣

Ejemplo 10.5.2 Calculemos las siguientes sumas (algo m´ as complicadas): an =

 ∞   n+k k=0

2k

2n−k ,

n = 0, 1, 2, . . .

Observemos que la suma llega, en realidad, hasta k = n. Seguimos el procedimiento habitual: f (x) =

∞  n=0

n

an x =

 ∞  n   n+k n=0

k=0

2k

n−k

2



n

x =

∞ 

−k

2

k=0

 ∞   n+k n=k

2k

(2x)n .

Queremos estimar la suma en n; si el coeficiente bin´omico tuviera 2k arriba, casi lo tendr´ıamos, porque conocemos el siguiente desarrollo (recordemos el ejemplo 10.1.1):  ∞   n + 2k 1 = (2x)n . (1 − 2 x)2 k+1 n=0 2k (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

798

Ser´ a cuesti´on de hacer que aparezca ese 2k arriba, a ver qu´e pasa. Pasa algo bueno:   ∞  ∞  ∞ ∞     2k + n − k 2k + n − k −k n −k k 2 2 (2x) (2x) = (2x)n−k f (x) = 2k 2k k=0 n=k k=0 n=k  ∞  ∞ ∞    1 j + 2k = 2−k (2x)k xk (2x)j = (1 − 2x)2k+1 2k j=0 k=0 k=0 k ∞   x 1 1 1 1 − 2x . = = = x 2 (1 − 2x) (1 − 2x) (1 − 2x) 1 − (1−2x)2 (1 − 4x)(1 − x) k=0

Ya tenemos la expresi´on de f (x) (la hemos escrito separando las ra´ıces del polinomio del numerador). S´ olo resta desarrollarla en serie, para lo que utilizamos fracciones simples:  ∞ ∞ ∞  2/3 1/3 2 1 n  2 n 1 1 − 2x n = + = 4 + xn . (4x) + x = f (x) = (1 − 4x)(1 − x) 1 − 4x 1 − x 3 3 3 3 n=0

n=0

n=0

Identificando los coeficientes de f (x) como los an , terminamos: an =

10.5.2.

22n+1 + 1 2 n 1 4 + = . 3 3 3

♣

Verificaci´ on de identidades

Partimos de un par de sucesiones (an ) y (bn ), y nuestro objetivo es probar que en realidad son la misma. Para ello, basta verificar que sus respectivas funciones generatrices coinciden. Veamos un ejemplo. Ejemplo 10.5.3 Comprobemos que los n´ umeros de Fibonacci satisfacen la relaci´ on F0 + F1 + · · · + Fn = Fn+2 − 1

para cada n ≥ 0.

´ Esta es una identidad ya conocida, que se puede probar combinando inducci´ on y la ecuaci´ on de recurrencia de los Fn , como propon´ıamos en el ejercicio 6.3.3. Abord´emosla con funciones on generatriz de los (Fn ). generatrices. Recordemos que x/(1 − x − x2 ) es la funci´ Por un lado,  ∞  n  x 1 Fj xn = , 1 − x 1 − x − x2 n=0 j=0

pues, recordemos, el efecto de multiplicar por la serie b´asica 1/(1 − x) es recuperar las sumas parciales de los coeficientes. Por otro lado, ∞ 

∞ 

∞ 

∞ 1  1 Fn+2 xn+2 − 2 x n=0 1−x n=0 n=0 n=0

1 x 1 1 x x 1 = 2 = . − F0 − F1 x − −x − = 2 x 1−x−x2 1−x x 1−x−x2 1−x (1 − x)(1−x−x2 )

(Fn+2 − 1)xn =

Fn+2 xn −

xn =

Y ya est´a: las funciones generatrices coinciden, as´ı que sus coeficientes tambi´en. (versi´ on preliminar 29 de octubre de 2008)

♣

10.5. Otras aplicaciones

799

Ejemplo 10.5.4 Otra identidad para los n´ umeros de Fibonacci:   n n  n−k  k  = para cada n ≥ 0. Fn+1 = k n−k k=0

k=0

La identidad de la izquierda la obtuvimos, con argumentos combinatorios, en la subsecci´on 6.3.5; y ya con funciones generatrices, en el ejemplo 10.4.1. Si el lector escribe con detalle las dos sumas de la derecha, comprobar´ a que efectivamente estamos sumando los mismos coeficientes bin´omicos, aunque en distinto orden. Para abordar la cuesti´ on con funciones generatrices, recordamos ahora dos series ya conocidas que aparecer´an durante los c´ alculos:       ∞ ∞ ∞    m+k j k xk k m j k = x = y (1 + x) = x x xj . k+1 (1 − x) k k j m=0

j=0

j=0

Las sumas las abordamos con el m´etodo curalotodo. Para la primera,   ∞  ∞   ∞  ∞ ∞ ∞       n−k n−k m m n k n−k k x = x x = x x f (x) = k k k n=0 k=0 m=0 k=0 n=k k=0 k ∞ ∞   1 1 1  1 xk x2 = = xk = = . 1−x 1−x 1 − x 1 − x2 /(1 − x) 1 − x − x2 (1 − x)k+1 k=0

k=0

Y para la segunda,   ∞  ∞   ∞  ∞  ∞ ∞      k k k n k n−k k x = x x = x xm g(x) = n−k n−k m =

n=0 k=0 ∞  k

∞ 

k=0

k=0

x (1 + x)k =

k=0

n=k

[x (1 + x)]k =

k=0

m=0

1 1 = . 1 − x (1 − x) 1 − x − x2

As´ı que las tres cantidades son, despu´es de todo, la misma.

10.5.3.

♣

Funciones generatrices y principio de inclusi´ on/exclusi´ on

El objeto de esta subsecci´on es aplicar las herramientas de las funciones generatrices para responder a cuestiones que van algo m´ as all´a de nuestro bien conocido principio de inclusi´on/exclusi´ on, que luego aplicaremos al estudio de objetos familiares, como los desbarajustes o las aplicaciones sobreyectivas. La herramienta b´asica que emplearemos ser´a la sustituci´ on de unas series de potencias en otras, que describ´ıamos en la regla 8 de la secci´on 10.2. Planteemos ya la cuesti´on que nos interesa: tenemos un conjunto X finito y una serie de subconjuntos suyos, digamos A1 , A2 , . . . , An . Para fijar ideas, identifiquemos cada subconjunto con una cierta propiedad. Esto es, Ak = {x ∈ X : x cumple la propiedad k}

para cada k = 1, 2, . . . , n.

La pregunta a la que responde el principio de inclusi´ on/exclusi´ on habitual es Pregunta 1 ¿Cu´ antos elementos de X cumplen al menos una de esas propiedades? (versi´ on preliminar 29 de octubre de 2008)

Cap´ıtulo 10. Funciones generatrices

800

La respuesta es bien conocida: hemos de hallar el tama˜ no de la uni´ on de los Ak : |A1 ∪ A2 ∪ · · · ∪ An | =

n 

(−1)r+1 αr ,

r=1

donde



αr =

|Ai1 ∩ Ai2 ∩ · · · ∩ Air |

para cada 1 ≤ r ≤ n.

1≤i1