Sucesiones tipo Fibonacci, resueltas mediante su ecuación característica.
Una relación de recurrencia lineal homogénea con coeficientes constantes es una ecuación que define el $n$-ésimo término de una sucesión, $a_n$, como 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}$. Estas relaciones aparecen por todos lados en las matemáticas de competencia, sobre todo en combinatoria (por ejemplo, problemas de mosaicos o conteo de caminos) y en teoría de números. El ejemplo más famoso es la sucesión de Fibonacci, donde cada término es la suma de los dos anteriores.
El poder de esta técnica está en que te permite transformar un proceso recursivo en uno algebraico. Si supones que la solución tiene la forma de una progresión geométrica $a_n = r^n$, puedes obtener un polinomio que llamamos la ecuación característica. Las raíces de este polinomio te dan las "piezas básicas" para armar la solución general. Como la recurrencia es lineal, cualquier combinación lineal de estas soluciones básicas también es una solución. Esto te permite encontrar una expresión cerrada (una fórmula explícita) para $a_n$ en términos de $n$, sin tener que calcular todos los términos intermedios.
Dominar las relaciones de recurrencia lineales es esencial para exámenes como el AIME y el USAMO. Aunque las recurren