Recurrencia lineal homogénea

Ensayar la solución \(a_n=r^n\) convierte la recurrencia en una ecuación algebraica: se divide entre \(r^{n-k}\) y queda la ecuación característica \(r^k=c_1r^{k-1}+\cdots+c_k\). Para \(a_n=5a_{n-1}-6a_{n-2}\) resulta \(r^2-5r+6=0\), con raíces 2 y 3, y por eso \(2^n\) y \(3^n\) son soluciones.

Como la ecuación es lineal, toda combinación de soluciones también lo es. Si las raíces son distintas, la solución general es \(a_n=\alpha_1r_1^n+\cdots+\alpha_kr_k^n\); si una raíz \(r\) se repite \(m\) veces aporta \((\alpha_0+\alpha_1n+\cdots+\alpha_{m-1}n^{m-1})r^n\); y las raíces complejas dan sucesiones que oscilan, como las de \(a_n=-a_{n-2}\). Los \(k\) coeficientes se fijan con los \(k\) valores iniciales resolviendo un sistema lineal.

Con \(a_0=1\) y \(a_1=5\) la recurrencia anterior da \(a_n=3^{n+1}-2^{n+1}\), de modo que \(a_{10}\) se obtiene sin calcular los nueve términos previos. Para Fibonacci las raíces son \(\tfrac{1\pm\sqrt5}{2}\) y de ahí sale la fórmula de Binet. Un error común es olvidar la raíz doble: \(2^n\) y \(n2^n\) son soluciones independientes, y usar solo \(2^n\) no basta para cumplir dos valores iniciales.