Codificando información: funciones generatrices (II)

En la entrada anterior vimos que multitud de sucesiones numéricas podían codificarse en funciones simples, gracias a la teoría de las series de Taylor.

Es corriente que estas sucesiones vengan dadas por una relación de recurrencia, es decir, que los términos a_k de la sucesión satisfagan ecuaciones de la forma,

\displaystyle a_{k+1} - a_{k-1} = a_{k+2} a_{k-2}

Una de las sucesiones más conocidas, dada por una relación de este tipo, es la sucesión de Fibonacci. Los elementos de esta sucesión cumplen la relación,

\displaystyle a_{k+2} = a_{k+1} + a_k

Esta ecuación no determina de manera única la sucesión: es necesario aportar una serie de valores iniciales para poner en marcha la sucesión. Dependiendo del orden de la recurrencia se necesitarán más o menos de estos valores.

Por ejemplo, la sucesión de Fibonacci clásica se obtiene al elegir a_0=1 y a_1=1. Podemos comprobar que al usar estos valores en la ecuación anterior se obtiene,

\displaystyle a_2=a_1+a_0=2,\quad a_3=a_2+a_1=3,\quad a_4=a_3+a_2=5,\quad\ldots

Aunque pueden calcularse explícitamente los términos de la sucesión de Fibonacci, supondremos que únicamente podemos calcularlos a partir de la recurrencia, que es realmente lo que ocurre con la mayoría de las recurrencias.

La pregunta es,

¿podemos obtener la función generatriz que codifica una sucesión, a partir de la recurrencia que la define?

La respuesta en general no la sé. En la mayoría de los casos dependerá de nuestra habilidad manipulando series.

Pero en el caso de la sucesión de Fibonacci sale muy sencillo. Supongamos que la sucesión de Fibonacci está codificada en la función F(x),

\displaystyle F(x) = \sum_{k=0}^\infty a_k x^k=a_0+a_1 x+\sum_{k=2}^\infty a_k x^k = 1 + x + \sum_{k=2}^\infty a_k x^k

En la última igualdad hemos usando las condiciones iniciales para la serie de Fibonacci clásica. Para el sumatorio que aparece al final de la línea se tiene,

\displaystyle \sum_{k=2}^\infty a_k x^k=\sum_{k=2}^\infty (a_{k-1}+a_{k-2}) x^k=\sum_{k=2}^\infty a_{k-1} x^k+\sum_{k=2}^\infty a_{k-2} x^k

Para los dos últimos sumatorios se puede escribir,

 \displaystyle \sum_{k=2}^\infty a_{k-1} x^k+\sum_{k=2}^\infty a_{k-2} x^k=x(F(x)-1)+x^2 F(x)

En la igualdad anterior hemos usado que F(x)-a_0=\sum_{k=1}^\infty a_k x^k. Usando todo lo que hemos obtenido se tiene la siguiente igualdad,

\displaystyle F(x)=1+x+\left(x(F(x)-1)+x^2 F(x)\right)=1+xF(x)+x^2F(x)

o lo que es lo mismo,

\displaystyle F(x)=\frac{1}{1-x-x^2}

¡Toda la sucesión de Fibonacci empaquetadita en esa función! 

…ahora ya sí que sí, ¿no? Quiero decir…

…¿qué las funciones generatrices no dan más de sí? Bueno, ya veremos…

Anuncios
Esta entrada fue publicada en Uncategorized y etiquetada , , , , , . Guarda el enlace permanente.

One Response to Codificando información: funciones generatrices (II)

  1. Pingback: Recursividad « morvalets

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s