Relaciones de Recurrencia

Teoría

Una relación de recurrencia es una ecuación que define una sucesión de forma recursiva; o sea, cada término de la sucesión se define como una función de los términos anteriores. Aunque las sucesiones aritméticas y geométricas son ejemplos sencillos de recurrencias, el tema generalmente se refiere a dependencias más complejas, como la sucesión de Fibonacci donde cada término es la suma de los dos anteriores. En las matemáticas de olimpiada, el objetivo principal suele ser convertir una definición recursiva en una expresión de "forma cerrada" — una fórmula que te permite calcular directamente el $n$-ésimo término sin tener que calcular todos los términos intermedios.

Las relaciones de recurrencia aparecen por todos lados en combinatoria, teoría de números y análisis de algoritmos. Surgen seguido en problemas de conteo que involucran caminos, teselados o arreglos donde un problema de tamaño $n$ se puede dividir en subproblemas más pequeños de tamaño $n-1$ o $n-2$. Por ejemplo, el número de formas de cubrir un tablero de $2 \times n$ con dominós se describe con una recurrencia lineal. Entender cómo resolver estas relaciones te da un puente muy útil entre los procesos recursivos discretos y las funciones algebraicas.

El tipo más común de recurrencia que sale en concursos como el AMC 12 y el AIME es la Relación de Recurrencia Lineal Homogénea con Coeficientes Constantes. El truco clave para resolverlas es el método de la "Ecuación Característica". Muy parecido a como se resuelven las ecuaciones diferenciales, supones que la solución tiene la forma de una sucesión geométrica ($r^n$), lo que transforma la recurrencia en una ecuación polinomial. Las raíces de este polinomio determinan la estructura de la solución de forma cerrada.

Fórmulas Clave

Recurrencia Lineal Homogénea General Para una sucesión definida por $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$, la ecuación característica es: $$r^k - c_1 r^{k-1} - c_2 r^{k-2} - \dots - c_k = 0$$

Recurrencia Lineal de Segundo Orden Para el caso específico $a_n = A a_{n-1} + B a_{n-2}$ con términos iniciales $a_0$ y $a_1$: La ecuación característica es: $$r^2 - Ar - B = 0$$

Soluciones basadas en las Raíces Sean $r_1$ y $r_2$ las raíces de la ecuación característica.

1. Raíces Reales Distintas ($r_1 \neq r_2$): La solución general es: $$a_n = c_1 (r_1)^n + c_2 (r_2)^n$$ donde $c_1$ y $c_2$ son constantes determinadas por las condiciones iniciales $a_0$ y $a_1$.

2. Raíz Real Repetida ($r_1 = r_2 = r$): La solución general es: $$a_n = c_1 r^n + c_2 n r^n$$

Identidades Útiles (Fibonacci) Para la sucesión de Fibonacci ($F_0=0, F_1=1, F_n = F_{n-1} + F_{n-2}$): $$F_n = \frac{\phi^n - \psi^n}{\phi - \psi} = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right]$$ Esta se conoce como la Fórmula de Binet.

Demostración

Teorema: Para una relación de recurrencia $a_n = A a_{n-1} + B a_{n-2}$ con raíces distintas $r_1, r_2$ de la ecuación característica $r^2 - Ar - B = 0$, la solución general es $a_n = c_1 r_1^n + c_2 r_2^n$.

Demostración:

Paso 1: El Ansatz (Suposición) Busca soluciones que tengan la forma de una sucesión geométrica, $a_n = r^n$ para alguna constante $r$ distinta de cero. Al sustituir esto en la relación de recurrencia obtienes: $$r^n = A r^{n-1} + B r^{n-2}$$

Suponiendo que $r \neq 0$, puedes dividir toda la ecuación entre $r^{n-2}$: $$r^2 = A r + B \implies r^2 - Ar - B = 0$$ Este polinomio es la ecuación característica.

Paso 2: Existencia de Soluciones Como ya sabes que la ecuación característica tiene dos raíces distintas, $r_1$ y $r_2$, tanto $r_1^n$ como $r_2^n$ son soluciones válidas para la relación de recurrencia. Por ejemplo, al checar $r_1$: $$A(r_1)^{n-1} + B(r_1)^{n-2} = (r_1)^{n-2}(A r_1 + B) = (r_1)^{n-2}(r_1^2) = r_1^n$$

Paso 3: Linealidad El operador de recurrencia $L(a_n) = a_n - A a_{n-1} - B a_{n-2} = 0$ es lineal. Esto significa que si $x_n$ y $y_n$ son soluciones, entonces cualquier combinación lineal $z_n = c_1 x_n + c_2 y_n$ también es una solución. Demostración de la linealidad: $$ \begin{aligned} z_n &= c_1 x_n + c_2 y_n \ &= c_1 (A x_{n-1} + B x_{n-2}) + c_2 (A y_{n-1} + B y_{n-2}) \ &= A(c_1 x_{n-1} + c_2 y_{n-1}) + B(c_1 x_{n-2} + c_2 y_{n-2}) \ &= A z_{n-1} + B z_{n-2} \end{aligned} $$ Así que $a_n = c_1 r_1^n + c_2 r_2^n$ es una solución para cualesquiera constantes $c_1, c_2$.

Paso 4: Completitud (Base) Una sucesión definida por una recurrencia de segundo orden queda determinada de forma única por sus primeros dos términos, $a_0$ y $a_1$. Para mostrar que todas las soluciones tienen la forma $c_1 r_1^n + c_2 r_2^n$, hay que mostrar que para cualquier par de valores iniciales arbitrarios $a_0, a_1$, puedes encontrar constantes únicas $c_1, c_2$ que los cumplan.

Si tomas $n=0$ y $n=1$: $$ \begin{cases} c_1(1) + c_2(1) = a_0 \ c_1 r_1 + c_2 r_2 = a_1 \end{cases} $$ Este es un sistema de ecuaciones lineales para $c_1$ y $c_2$. El determinante de la matriz de coeficientes es: $$ \det \begin{pmatrix} 1 & 1 \ r_1 & r_2 \end{pmatrix} = r_2 - r_1 $$ Como las raíces son distintas ($r_1 \neq r_2$), el determinante no es cero. Por lo tanto, existe un par único $(c_1, c_2)$ para cualquier valor inicial $a_0, a_1$.

Por lo tanto, la fórmula $a_n = c_1 r_1^n + c_2 r_2^n$ cubre todas las soluciones posibles. $\square$