Funciones generadoras para resolver recurrencias

Para analizar el coste de un recursivo de una variable vimos varias posibilidades, como desarrollar la recurrencia hasta el caso trivial o equipararla a una ecuación característica. Son técnicas básicas para recurrencias simples como T(n). Pero si la recurrencia es más compleja o incluye dos variables T(n, k), entonces hemos de aplicar la técnica de la función generadora que veremos en estos temas.

En el tema siguiente veremos recurrencias de dos variables como T(n, k) que resolveremos con la función generadora. Previamente para practicar esta técnica resolveré algunos ejemplos simples con una variable, tomando los mismos problemas expuestos en los temas de recursivos que señalamos antes.

Como vemos en Wikipedia, la función generadora o generatriz es una serie formal de potencias cuyos coeficientes codifican información sobre una sucesión a_n cuyo índice corre sobre los enteros no negativos. Una definición que podemos entender mejor con la función generadora que vemos en la Figura:

Esta es una serie geométrica sobre la que entraremos con más detalle en un apartado más abajo. Por ahora observe que

donde tenemos la sucesión de coeficientes a_n = 1, 1, 1, ... que se pueden generar con la serie ∑_n≥0 1 xⁿ, serie que se obtiene a partir del desarrollo de la función generadora. Este desarrollo puede hacerse usando la fórmula Taylor:

donde las derivadas f ⁿ(x) son las siguientes:

Con sólo estos términos podemos ver que particularizando para x=0 solo nos queda la secuencia de numeradores 1, 1, 2, 6, 24, ... = 0!, 1!, 2!, 3!, 4!, ... = n!, así que para todo n tenemos

de tal forma que

Si tuviéramos una recurrencia como la siguiente

La función generadora y su serie serían precisamente esas. Y el término general a_n = 1 en la serie es la solución a la recurrencia, es decir, T(n) = 1 es la solución, lo que puede parecer obvio, pero es lo que se deduce de esta técnica. En los problemas siguientes veremos soluciones no tan obvias.

Pasos para aplicar la función generadora a una recurrencia

Resumimos los pasos para aplicar la función generadora para resolver una recurrencia. Pondremos como ejemplo los obtenidos en el problema del factorial que veremos en el apartado siguiente:

1. Plantear la recurrencia: T(n) = T(n-1) + 1, definiendo las condiciones iniciales T(0)= 1.
2. Ajustar la recurrencia para evitar índices negativos: T(n+1) = T(n) + 1, T(0) = 1.
3. Definir la función generadora: G_n(x) = ∑_n≥0 T(n) xⁿ.
4. Determinar las condiciones iniciales de la función generadora: G₀(x) = 1.
5. Multiplicar por xⁿ y sumar todos los términos de la recurrencia:
   ∑_n≥0 T(n+1) xⁿ = ∑_n≥0 T(n) xⁿ + ∑_n≥0 xⁿ
6. Identificar G_n(x) así como también expresando T(n+1) en función de T(n) y a su vez en función de G_n(x).
7. Identificar series directamente como la geométrica que vimos en el primer apartado:

   ∑n≥0 xn =	1
   	1-x

8. Finalmente llegaremos a una expresión que nos permitirá despejar G_n(x):

   1	(Gn(x) - 1) = Gn(x) +	1
   x		1-x

9. Despejaremos G_n(x) para obtener siempre un cociente de polinomios:

   Gn(x) =	1
   	(1-x)2

10. Expresar G_n(x) = ∑_n≥0 f(n) xⁿ como una serie. Cuando lo tengamos podemos deducir que el término general f(n) de este serie es igual que el que estamos buscando T(n). Para determinar esa serie es recomendable simplificar G_n(x) en fracciones simples y buscar una serie para cada término más fácilmente. Una forma de determinar una serie es usando el desarrollo de Taylor que ya vimos en el apartado anterior:

    f(x) = ∑n≥0	f n(0)	xn
    	n!

11. Finalmente tendremos la solución:
    G_n(x) = ∑_n≥0 (n+1) xⁿ ⇒ T(n) = n+1

El factorial: resolver con función generadora

En la serie de temas sobre los recursivos vimos cómo calcular el coste de la función recursiva factorial. Este recursivo es muy simple, pues n! = n × (n-1)! con la condición inicial 0! = 1. Su simplicidad nos pemitirá exponer la técnica de la función generadora para calcular el coste.

Empecemos por recordar el algoritmo y la recurrencia:

function factorial(n){
    if (n===0){
        return 1;
    } else {
        return n*factorial(n-1);
    }
}

O puesta de manera compacta podemos expresarla así:

Esta recurrencia también podemos expresarla así para evitar el índice n-1 (más abajo explicaremos el motivo):

Definimos una función generadora

Para ser coherentes deberíamos denominar G_n(x) a la función generadora. También lo he visto escrito como G(a_n; x). Pero para simplificar omitimos la n. A veces necesitaremos expresarlo así, como con las condiciones iniciales:

Multiplicamos la recurrencia T(n+1) = T(n) + 1 en ambos lados por xⁿ:

Y sumamos ambos lados

Antes de seguir, vea que si no hubiésemos evitado el índice n-1 podríamos tener un problema al aplicar la función generadora, pues tendríamos un término T(-1) que no está definido en la recurrencia ni, por tanto, en el algoritmo:

En la parte derecha de [1] tenemos ∑_n≥0 T(n) xⁿ = G(x). Y el otro sumando es una serie geométrica que converge para |x|<1:

Veamos el lado izquierdo

Multiplicando por x/x

Sumamos y restamos T(0)

Lo resaltado es G(x) y como T(0) = 1 queda finalmente

Con esto la expresión final [1] queda como sigue:

Para encontrar el término general para T(n) hemos de expandir G(x) usando series. Podemos descomponer en fracciones simples el primer término de la expresión de la derecha:

Con lo que finalmente nos queda:

Una vez que tengamos la función generadora tenemos que expresarla como una serie

A partir de aquí tenemos varias posibilidades. Una de ellas es usando el desarrollo de Taylor que ya vimos en el primer apartado:

Calculamos las primeras derivadas:

Con sólo estos términos podemos ver que particularizando para x=0 solo nos queda la secuencia de numeradores 1, 2, 6, 24, 120, ... = 1!, 2!, 3!, 4!, 5!, ... = (n+1)!, así que para todo n≥0 tenemos

Esta hipótesis habría que demostrarla usando alguna técnica, como la demostración por inducción. Puede ver un ejemplo en el siguiente apartado. Una vez demostrado podemos asegurar que la serie que le corresponde a G(x) es:

Alternativamente podemos usar otras técnicas como la siguiente. Ya vimos que la suma geométrica era

Si derivamos las expresiones tenemos:

Por lo tanto

Sea de una forma u otra, finalmente hemos obtenido la solución de la recurrencia:

Como partimos definiendo G(x) = ∑_n≥0 T(n) xⁿ resulta que el término general de la recurrencia que buscamos es:

Y este es el mismo resultado que encontramos usando la ecuación característica.

Las torres de Hanoi: resolver con función generadora

Veamos ahora la recurrencia de las torres de Hanoi, otro problema que ya resolvimos usando la técnica de la ecuación característica.

El problema se basa en que tenemos 3 postes y un número n de discos de diferentes radios en uno de los postes, de tal forma que están ordenados de mayor a menor. Tenemos que pasar esos discos a otro poste pero con la restricción de que en cada movimiento sólo podemos pasar un disco. Y que en ningún caso podrá haber un disco de mayor radio sobre otro menor, es decir, siempre tendrán que estar ordenados de forma decreciente.

Este era el algoritmo que utilizábamos:

function hanoi(postes, i=0, j=1, n=postes[i].length){
    if (n===0) {
        //caso trivial
    } else {
        let p = n-1;
        let k = 3-i-j;
        hanoi(postes, i, k, p);
        postes[j].push(postes[i].pop());
        hanoi(postes, k, j, p);
    }
}

Y así definíamos la recurrencia:

Esta recurrencia también podemos expresarla así para evitar el índice n-1, cuya necesidad ya explicamos en el apartado anterior:

Definimos una función generadora:

Determinamos las condiciones iniciales:

Multiplicamos la recurrencia por xⁿ y sumamos

Veamos la parte izquierda ∑_n≥0 T(n+1) xⁿ como hicimos en el desplegable del primer apartado

De donde

Agrupamos [2] y [3]

Despejando obtenemos:

Descomponemos el cociente de polinomios

Por lo que

Una vez obtenida la función generadora, hemos de equipararla a una serie para localizar el término general. En la parte derecha tenemos la función generadora de la suma geométrica, cuya serie conocemos:

Desarrollemos con Taylor el otro componente que denominaremos f(x):

Calculamos las primeras derivadas:

Particularizadas para x=0 tenemos

En la sucesión anterior 2, 4, 16, 96,... hemos hecho una suposición para el término general 2ⁿ⁺¹ n!, pudiendo demostrarse por inducción matemática el término general de la derivada n-ésima:

Y este término particularizado para n=0 es:

Entonces el desarrollo de Taylor queda:

Tomando [5] y [6] y sustituyendo en [4] y operando la suma de series:

Como partimos definiendo G(x) = ∑_n≥0 T(n) xⁿ resulta que el término general de la recurrencia que buscamos es:

Y este es el mismo resultado que encontramos usando la ecuación característica.

Fibonacci: resolver con función generadora

En el tema de Fibonacci vimos esta función recursiva que se define como f(0)=0, f(1)=1 y f(n) = f(n-1) + f(n-2) para n≥2. Los primeros téminos de la sucesión son 0, 1, 1, 2, 3, 5, 8, 13, 21,... La espiral de Fibonacci de la Figura representa esta sucesión como arcos de cuadrante inscritos en rectángulos cuyos lados siguen esta sucesión.

En ese tema usamos la técnica de la ecuación característica para obtener la solución. Repetimos este problema usando la técnica de la función generadora. El algoritmo usado era el siguiente:

function fibonacci(n){
    if (n<2){
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

Definíamos la recurrencia así:

Evitamos los índices negativos, pudiendo entonces expresar la recurrencia así:

Usamos la misma función generadora que en los ejemplos anteriores:

Las condiciones iniciales son:

Aplicamos xⁿ a la recurrencia y sumamos:

Como en casos anteriores, en la derecha tenemos la suma geométrica:

Expresemos el término T(n+2) en función de T(n):

Obteniendo el término T(n+2)

Y ahora el término T(n+1)

Por lo tanto

Sustituyendo [7], [9], [10] y [11] en [8]

Obteniendo la función generadora siguiente:

No parece fácil aplicar el desarrollo de Taylor a esta expresión para deducir su serie. Intentemos simplificar:

Entonces

Por lo tanto de la primera ecuación A = -1 y de la segunda B = 1-A = 2, valores que cumplen la tercera ecuación A+B = 2-1 = 1. Entonces la función generadora [12] nos queda así:

El primer término ya sabemos que es la serie geométrica ∑_n≥0 xⁿ. Hemos de obtener una serie para el segundo término. Como 1-x-x² = -(x²+x-1) buscaremos las raíces de la ecuación de segundo grado x²+x-1:

Sea

Observe estas propiedades de Φ y δ, pues algunas de ellas nos servirán posteriormente:

• Φ+δ = 1
• Φ-δ = √5
• Φδ = -1 ⇒ Φ = - ⅟δ ∧ δ = - ⅟Φ

Entonces

Con esto el segundo término de la función generadora [13] nos queda así, donde nuevamente desarrollamos en fracciones:

Ahora estamos en condiciones de encontrar una serie para cada uno de los términos entre paréntesis. Vease que una serie geométrica de razón ax es:

Viendo que Φ-δ = √5 nos queda

Sin usar el "truco" que nos permitió obtener 1-Φx y 1-δx que nos facilitó el uso de series geométricas, podemos aplicar cálculos usando Taylor y desarrollando hasta alcanzar el mismo resultado, aunque con más esfuerzo, como se muestra en el siguiente desplegable.

Finalmente, volviendo a la función generadora [13]:

Por lo tanto el término general es

Y este el mismo resultado que obtuvimos con la ecuación característica, aunque con mucho más trabajo.

Recurrencia de la función Fibonacci

No debe confundirse nuestra recurrencia que se define a partir del algoritmo como:

con la recurrencia para resolver la función de Fibonacci:

Ajustamos esta función para evitar índices negativos:

Con esta función las condiciones iniciales son diferentes:

Vea que G₀ es cero cuando en nuestro problema era uno. Además esta recurrencia no tiene el término 1 señalado más arriba, con lo que la expresión [8] que vimos en nuestro problema quedaría así:

Haciendo el mismo proceso para obtener F(n+2) y F(n+1) como hicimos en nuestro problema, pero ahora teniendo en cuenta que la condición inicial G₀(x) = 0 es distinta, llegaríamos a la expresión siguiente, ligeramente diferente a la que obtuvimos:

Al resolverla obtenemos esto, también algo diferente, aunque con el mismo polinomio en el denominador 1-x-x²:

Con esa expresión aplicando las mismas raíces Φ, δ como hicimos en el apartado anterior llegaríamos a obtener esta solución, también diferente en algunas cosas con la nuestra:

Relación entre la función generadora y la ecuación característica

En este apartado vamos a analizar para los tres ejemplos lo que resolvimos con la ecuación característica y como lo resolvimos en este tema con la función generadora. Intentaré saber cuál es el motivo de que no siempre aparezca exactamente la misma ecuación característica en el denominador de la función generadora. Si es que hay alguna relación entre ambas cosas.

El factorial

Empecemos por el tema del factorial, donde obtuvimos la ecuación característica siguiente:

cuyas raices r = 1 de multiplicidad 2 nos permitían obtener la solución general

Obteníamos las constantes a partir de las condiciones iniciales, obteniendo finalmente la solución exacta siguiente

Esa solución es la misma que la obtenida con la técnica de la función generadora

Observe que la ecuación característica es "casi" la misma que el polinomio del denominador. Es la misma pues (x-1)² = (1-x)² es una potencia par, donde se iguala el posible signo negativo interior. Pero esa "leve" diferencia entre x-1 y 1-x tiene una razón de ser que explicaremos mejor con el siguiente ejemplo.

Torres de Hanoi

En el ejemplo torres de Hanoi obteníamos esta ecuación característica que vamos a denominar R(x):

Las raíces r = 1, r = 2, ambas de multiplicidad uno, nos daban la solución general y la solución exacta al aplicar las condiciones iniciales:

Esa solución exacta es la misma que la que obtuvimos con la función generadora:

Al estar esta fracción de polinomios ya en un estado de irreducible, P(x) es necesariamente de un grado inferior a Q(x). Entonces ¿qué relación hay entre R(x) y Q(x)? Las raíces de Q(x) son q = 1, q = ½ ambas de multiplicidad uno, pero diferente una de ellas de las de R(x). Para resolverlo necesitamos la siguiente definición.

Dos polinomios Q(x) y R(x) son polinomios recíprocos o reflejados si para cada término se cumple que a_i xⁱ = a_n-i xⁱ lo que supone invertir los coeficientes:

Dos polinomios Q(x) y R(x) recíprocos cumplen estas propiedades:

• d = deg R = deg Q (El operador deg es el grado del polinomio)
• R(x) = x^d Q(⅟x)
• r es raíz de R ⇔ ⅟r es raíz de Q
• Si R(x)≠x ⇒ R es irreducible ⇔ Q es irreducible
• R es primitivo ⇔ Q es primitivo

Nuestros dos polinomios son recíprocos, pues tienen los coeficientes invertidos:

Se cumple que ambos tienen el mismo grado:

Se cumple que las raíces de uno son las recíprocas del otro:

También se cumple R(x) = x^d Q(⅟x), pues aplicándolo a Q(x) = 1-3x+2x²

También podemos aplicarlo a cada término de Q(x) = (1-x)(1-2x) así:

En estas condiciones podemos decir que R(x) = (x-2)(x-1) = x²-3x+2 es la única ecuación característica de la recurrencia de las Torres de Hanoi que habíamos planteado. Cada recurrencia tiene una única ecuación característica y, al revés, a cada ecuación característica le corresponde una única recurrencia. En el polinomio del denominador de la función generadora tenemos el recíproco de la ecuación característica.

Fibonacci

Lo mismo sucede con el problema de Fibonacci, donde teníamos la siguiente ecuación característica:

Con tres raíces de multiplicidad uno:

Siendo

En este tema hemos obtenido la siguiente función generadora:

Obteníamos la misma solución con ambas técnicas:

El cociente de polinomios P(x) / Q(x) está ya expresado de una forma irreducible, con el grado del numerador deg P(x) = 2 menor que el del denominador deg Q(x) = 3:

Vemos que Q(x) y R(x) son recíprocos pues tienen los coeficientes invertidos. Se observa mejor si los ponemos así:

Las raíces de Q(x) son q₁ = 1, q₂ = -Φ = ⅟δ , q₃ = -δ = ⅟Φ que son las recíprocas de las de R(x). Recuerde que vimos en el apartado de la función generadora de Fibonacci las propiedades de Φ y δ.

Ademas se cumple R(x) = x^d Q(⅟x):

Al ser R(x) y Q(x) recíprocos entonces R(x) es la única ecuación característica que le corresponde a la recurrencia dada en nuestro problema.