De una recurrencia a una función racional.
Encontrar la forma cerrada de una Función Generatriz Ordinaria (FGO) es una técnica muy poderosa que sirve para transformar una sucesión definida por recurrencia en una expresión algebraica compacta, que normalmente es una función racional. La idea central es que tú definas una serie de potencias $A(x) = \sum_{n=0}^{\infty} a_n x^n$ basada en la sucesión ${a_n}$ y luego manipules esta serie usando la relación de recurrencia que te den. Si multiplicas la función generatriz por potencias de $x$ y constantes lineales, puedes alinear los términos de la serie de tal forma que la recurrencia haga que casi toda la suma infinita se cancele y se vuelva cero.
Este método es fundamental en combinatoria porque conecta las relaciones de recurrencia discretas con el análisis continuo. Ya que estableces una forma cerrada $A(x) = \frac{P(x)}{Q(x)}$, puedes usar la descomposición en fracciones parciales y expansiones en series de Taylor para encontrar una fórmula explícita para el término $n$-ésimo, $a_n$. Esto funciona súper bien para las Recurrencias Lineales Homogéneas con Coeficientes Constantes (RLHCC), como la sucesión de Fibonacci, pero también lo puedes adaptar para casos no homogéneos y sistemas de recurrencias.
El truco clave está en la propiedad de "desplazamiento" de las funciones generatrices. Si $A(x)$ genera a ${a_n}$, entonces $x^k A(x)$ genera la misma sucesión pero movida $k$ posiciones a la derecha (poniendo ceros al principio). Al armar una combinación lineal de $A(x)$ y sus desplazamientos que coincida con la relación de recurrencia, reduces la complejidad infinita de la sucesión a un cálculo de polinomios finitos que solo depende de las condiciones iniciales.
Definición de FGO $$A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots$$
Relación de Recurrencia Lineal Para una sucesión definida por $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$ para $n \ge k$:
La Forma Cerrada Racional La función generatriz es una función racional: $$A(x) = \frac{P(x)}{Q(x)}$$ donde:
Serie Geométrica Generalizada (para extraer términos) Cuando ya tienes la forma cerrada, extraes los coeficientes usando: $$\frac{1}{(1-rx)^m} = \sum_{n=0}^{\infty} \binom{n+m-1}{m-1} r^n x^n$$ Caso especial ($m=1$): $$\frac{1}{1-rx} = \sum_{n=0}^{\infty} r^n x^n$$
Teorema: Sea ${a_n}{n \ge 0}$ una sucesión que cumple la recurrencia lineal $a_n = \sum{i=1}^k c_i a_{n-i}$ para todo $n \ge k$, con valores iniciales arbitrarios $a_0, \dots, a_{k-1}$. Entonces la función generatriz ordinaria $A(x) = \sum_{n=0}^\infty a_n x^n$ es una función racional de la forma $\frac{P(x)}{Q(x)}$.
Demostración:
Toma $A(x) = \sum_{n=0}^{\infty} a_n x^n$. La idea es aislar $A(x)$ usando la relación de recurrencia para cancelar los términos de orden alto.
Considera el polinomio $Q(x) = 1 - \sum_{i=1}^k c_i x^i$. Ahora fíjate en el producto $A(x)Q(x)$:
$$ \begin{aligned} A(x)Q(x) &= \left( \sum_{n=0}^{\infty} a_n x^n \right) \left( 1 - c_1 x - c_2 x^2 - \dots - c_k x^k \right) \ &= A(x) - c_1 x A(x) - c_2 x^2 A(x) - \dots - c_k x^k A(x) \end{aligned} $$
Puedes escribir los términos de estas sumas de forma explícita para agruparlos por potencias de $x$: $$ \begin{aligned} A(x) &= a_0 + a_1 x + \dots + a_{k-1} x^{k-1} + \sum_{n=k}^{\infty} a_n x^n \ -c_1 x A(x) &= \quad - c_1 a_0 x - \dots - c_1 a_{k-2} x^{k-1} - \sum_{n=k}^{\infty} c_1 a_{n-1} x^n \ &\vdots \ -c_k x^k A(x) &= \quad \quad \quad \quad \quad \quad \quad - c_k a_0 x^k \dots - \sum_{n=k}^{\infty} c_k a_{n-k} x^n \end{aligned} $$
Ahora, mira el coeficiente de $x^n$ en el producto $A(x)Q(x)$. Para cualquier $n \ge k$, el coeficiente es: $$ x^n = a_n - c_1 a_{n-1} - c_2 a_{n-2} - \dots - c_k a_{n-k} $$ Como la sucesión cumple la recurrencia $a_n = \sum_{i=1}^k c_i a_{n-i}$, esta expresión es igual a $a_n - a_n = 0$.
Por lo tanto, todos los términos que tienen $x^n$ con $n \ge k$ desaparecen. Los únicos términos que no son cero y que sobran son aquellos donde la potencia de $x$ es menor a $k$. Sea $P(x)$ el polinomio formado por estos términos que sobraron: $$ P(x) = \sum_{n=0}^{k-1} \left( a_n - \sum_{j=1}^{n} c_j a_{n-j} \right) x^n $$ (Nota: Los límites de la suma interna dependen de los términos específicos que tengas para valores pequeños de $n$).
Como $A(x)Q(x) = P(x)$ y $P(x)$ es un polinomio de grado a lo más $k-1$, puedes despejar $A(x)$: $$ A(x) = \frac{P(x)}{Q(x)} $$ Así, la función generatriz es una función racional. $\square$