Pasar de recurrencias a una fórmula cerrada.
El método para resolver recurrencias con Funciones Generatrices Ordinarias (OGF) es una técnica algebraica muy potente que sirve para transformar una relación recursiva en una expresión de forma cerrada. En lugar de analizar la sucesión $a_0, a_1, a_2, \dots$ directamente, defines una serie de potencias formal $A(x) = \sum_{n=0}^{\infty} a_n x^n$. Al realizar operaciones con esta serie, conviertes la relación de recurrencia de $a_n$ en una ecuación algebraica que involucra a la función $A(x)$.
Esta técnica es súper importante en las matemáticas de competencia porque te da un algoritmo sistemático para resolver no solo recurrencias lineales homogéneas (como la de Fibonacci), sino también recurrencias no homogéneas y sistemas de recurrencias que son difíciles de resolver con ecuaciones características o inducción. Básicamente transforma un problema de "cálculo discreto" (diferencias finitas) en un problema de álgebra. Una vez que encuentras una fórmula explícita para $A(x)$ —que suele ser una función racional— recuperas la forma cerrada para el $n$-ésimo término $a_n$ expandiendo $A(x)$ de nuevo en una serie, normalmente usando descomposición en fracciones parciales.
La idea clave se basa en la "propiedad de desplazamiento" de las funciones generatrices. Si $A(x)$ genera la sucesión ${a_n