Resolver an = c₁a(n-1) + c₂a(n-2) + ...
Una relación de recurrencia lineal homogénea con coeficientes constantes es una ecuación que define una sucesión ${a_n}$ donde cada término es una combinación lineal de los $k$ términos anteriores. Específicamente, tiene la forma $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$ para constantes $c_i$. Estas recurrencias aparecen por todos lados en combinatoria y sirven para modelar fenómenos que van desde el crecimiento poblacional (números de Fibonacci) hasta problemas de mosaicos y enumeración de cadenas. El "orden" de la recurrencia es $k$, y para tener una solución única necesitas $k$ condiciones iniciales (valores para $a_0, \dots, a_{k-1}$).
Aunque a veces puedes adivinar recurrencias simples, el método sistemático para resolverlas se basa en la conexión entre las recurrencias lineales y las funciones generatrices racionales. La idea fundamental es que una sucesión cumple una recurrencia lineal con coeficientes constantes si y solo si su Función Generatriz Ordinaria (FGO), $A(x) = \sum_{n=0}^{\infty} a_n x^n$, es una función racional $P(x)/Q(x)$, donde $P$ y $Q$ son polinomios.
Resolver estas recurrencias implica encontrar las raíces de un polinomio derivado de la recurrencia, al que llamamos ecuación característica. Si las raíces son distintas, la solución cerrada para $a_n$ es una combinación lineal de las $n$-ésimas potencias de estas raíces. Si hay raíces repetidas, la solución incluye factores polinomiales en $n$. Esta técnica transforma una definición recursiva en una fórmula directa, lo que te permite calcular rápidamente $a_n$ para valores grandes de $n$ y analizar el comportamiento asintótico de la sucesión.
La Recurrencia General Si tienes 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 ecuación característica es: $$r^k - c_1 r^{k-1} - c_2 r^{k-2} - \dots - c_k = 0$$
Solución General (Raíces Distintas) Si la ecuación característica tiene $k$ raíces distintas $r_1, r_2, \dots, r_k$, la solución general es: $$a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \dots + \alpha_k r_k^n$$ donde las $\alpha_i$ son constantes que determinas con las condiciones iniciales.
Solución General (Raíces Repetidas) Si una raíz $r$ tiene multiplicidad $m$, aporta $m$ términos a la solución general de esta forma: $$(\beta_0 + \beta_1 n + \beta_2 n^2 + \dots + \beta_{m-1} n^{m-1}) r^n$$
Forma de la Función Generatriz La Función Generatriz Ordinaria $A(x) = \sum_{n=0}^{\infty} a_n x^n$ para una sucesión de este tipo es: $$A(x) = \frac{P(x)}{1 - c_1 x - c_2 x^2 - \dots - c_k x^k}$$ donde $P(x)$ es un polinomio de grado menor a $k$ que determinas con las condiciones iniciales $a_0, \dots, a_{k-1}$.
Teorema: Si una sucesión ${a_n}$ cumple la recurrencia lineal $a_n = c_1 a_{n-1} + \dots + c_k a_{n-k}$ para $n \ge k$, entonces puedes expresar $a_n$ como una suma de términos que vienen de las raíces del polinomio característico.
Demostración mediante Funciones Generatrices:
Define la Función Generatriz Toma $A(x) = \sum_{n=0}^{\infty} a_n x^n$. Multiplica la relación de recurrencia por $x^n$ y suma sobre todos los valores válidos de $n$ (específicamente $n \ge k$): $$\sum_{n=k}^{\infty} a_n x^n = \sum_{n=k}^{\infty} \left( \sum_{j=1}^{k} c_j a_{n-j} \right) x^n$$
Expresa en términos de $A(x)$ El lado izquierdo es simplemente $A(x) - \sum_{n=0}^{k-1} a_n x^n$. En el lado derecho, distribuye la suma y cambia los índices. Para cada término $j$: $$c_j $$