Secuencias definidas por recurrencia lineal

Recurrencias lineales de orden 2: forma general

Una recurrencia lineal homogénea de orden 2 tiene la forma $a_{n+1} = p \, a_n + q \, a_{n-1}$ para $n \ge 2$, con condiciones iniciales $a_1$ y $a_2$ dados. Los coeficientes $p$ y $q$ son constantes reales (o enteras).

La solución general se obtiene a partir de la ecuación característica $r^2 = p \, r + q$, es decir $r^2 - p \, r - q = 0$. Sea $\Delta = p^2 + 4q$ el discriminante.

Caso 1 — Raíces distintas ($\Delta > 0$): las raíces son $r_1, r_2 = \dfrac{p \pm \sqrt{\Delta}}{2}$ con $r_1 \ne r_2$. La solución general es $a_n = A \, r_1^n + B \, r_2^n$, con $A$ y $B$ determinados por las condiciones iniciales.

Caso 2 — Raíces iguales ($\Delta = 0$): la única raíz es $r_0 = p/2$. La solución general es $a_n = (A + B \, n) \, r_0^n$, con $A$ y $B$ determinados por las condiciones iniciales. El factor extra $n$ distingue las dos soluciones linealmente independientes.

Caso 3 — Raíces complejas ($\Delta < 0$): $r_{1,2} = \rho \, e^{\pm i\theta}$ con $\rho = \sqrt{-q}$ y $\cos\theta = p/(2\rho)$. La solución real es $a_n = \rho^n (A \cos(n\theta) + B \sin(n\theta))$. Este caso aparece en problemas con sucesiones periódicas o casi periódicas.

El ejemplo paradigmático: Fibonacci

La sucesión de Fibonacci se define por $F_1 = 1$, $F_2 = 1$, $F_{n+1} = F_n + F_{n-1}$ para $n \ge 2$. La ecuación característica es $r^2 - r - 1 = 0$, con raíces $\varphi = \dfrac{1+\sqrt{5}}{2}$ (la razón áurea) y $\hat{\varphi} = \dfrac{1-\sqrt{5}}{2}$.

La solución general es $F_n = A \, \varphi^n + B \, \hat{\varphi}^n$. Con las condiciones iniciales $F_1 = F_2 = 1$:

$A\varphi + B\hat{\varphi} = 1$ y $A\varphi^2 + B\hat{\varphi}^2 = 1$. Usando $\varphi^2 = \varphi + 1$ y $\hat{\varphi}^2 = \hat{\varphi}+1$: $A(\varphi+1)+B(\hat{\varphi}+1) = 1$, es decir $(A\varphi+B\hat{\varphi})+(A+B) = 1$, luego $A+B = 0$. Entonces $A = 1/\sqrt{5}$ y $B = -1/\sqrt{5}$. Fórmula de Binet: $F_n = \dfrac{\varphi^n - \hat{\varphi}^n}{\sqrt{5}}$.

Esta fórmula es fundamental en olimpiadas: permite calcular $F_n \pmod{m}$, demostrar divisibilidades como $\gcd(F_m, F_n) = F_{\gcd(m,n)}$, y estimar el crecimiento de $F_n$.

Recurrencias lineales no homogéneas

Una recurrencia no homogénea tiene la forma $a_{n+1} = p \, a_n + q \, a_{n-1} + f(n)$, donde $f(n)$ es un término independiente. La solución general es la suma de una solución particular $a_n^{(p)}$ más la solución general de la homogénea asociada.

Para $f(n) = c$ (constante): si $r=1$ no es raíz de la ecuación característica, la solución particular es $a^{(p)} = c/(1-p-q)$. Si $r=1$ es raíz simple, el ansatz es $a^{(p)} = Cn$.

Para $f(n) = c \cdot s^n$: si $s$ no es raíz característica, el ansatz es $a^{(p)} = K \cdot s^n$. Si $s$ es raíz simple, el ansatz es $a^{(p)} = Kn \cdot s^n$.

Técnica olímpica: en muchos problemas de olimpiadas la sucesión se define implícitamente por condiciones del tipo "$a_n$ divide a cierta expresión" o "$a_n$ es el entero más cercano a $\alpha^n$". En esos casos se usa la fórmula cerrada (como Binet) para identificar la sucesión con la solución de la recurrencia y explotar propiedades de divisibilidad o congruencia.

Problema olímpico con recurrencia lineal

Problema (IbAm adaptado). Sea $\{a_n\}$ la sucesión definida por $a_1 = 1$, $a_2 = 3$, y $a_{n+1} = 3a_n - a_{n-1}$ para $n \ge 2$. Demostrar que $a_n^2 - a_{n+1} a_{n-1} = 1$ para todo $n \ge 2$, y encontrar una fórmula cerrada para $a_n$.

Ecuación característica: $r^2 - 3r + 1 = 0$, raíces $r_{1,2} = \dfrac{3 \pm \sqrt{5}}{2}$. Notar que $r_1 = \varphi^2$ y $r_2 = \hat{\varphi}^2$ donde $\varphi, \hat{\varphi}$ son las raíces de Fibonacci. La solución general: $a_n = A r_1^n + B r_2^n$. Con $a_1=1$, $a_2=3$: $Ar_1+Br_2 = 1$ y $Ar_1^2+Br_2^2=3$. De la segunda: $A r_1(3r_1-r_2)+Br_2(3r_2-r_1) = 3$... Usando $r_1+r_2=3$ y $r_1 r_2 = 1$: tras cálculo, $A = B = 1/\sqrt{5}$ (salvo signos). La fórmula cerrada resulta $a_n = F_{2n-1}$ donde $F_k$ es el $k$-ésimo número de Fibonacci.

**Identidad $a_n^2 - a_{n+1}a_{n-1} = 1$:** esta es la identidad de Cassini generalizada. Por inducción: base $n=2$: $a_2^2 - a_3 a_1 = 9 - 8 \cdot 1 = 9 - 8 = 1$. $\checkmark$ (con $a_3 = 3 \cdot 3 - 1 = 8$). Paso: $a_{n+1}^2 - a_{n+2}a_n = (3a_n-a_{n-1})^2 - (3a_{n+1}-a_n)a_n = 9a_n^2 - 6a_na_{n-1}+a_{n-1}^2 - 3a_{n+1}a_n+a_n^2$. Agrupando: $= 9a_n^2+a_n^2-3a_n(2a_{n-1}+a_{n+1})+a_{n-1}^2$. Con $a_{n+1} = 3a_n-a_{n-1}$: $2a_{n-1}+a_{n+1}=2a_{n-1}+3a_n-a_{n-1}=a_{n-1}+3a_n$. Luego $= 10a_n^2 - 3a_n(a_{n-1}+3a_n)+a_{n-1}^2 = 10a_n^2-3a_na_{n-1}-9a_n^2+a_{n-1}^2 = a_n^2-3a_na_{n-1}+a_{n-1}^2$. Y por hipótesis inductiva $a_n^2-a_{n+1}a_{n-1}=1$... el paso se completa verificando que $a_n^2-3a_na_{n-1}+a_{n-1}^2 = a_n^2 - a_{n+1}a_{n-1} - (a_{n+1}-3a_n+a_{n-1})\cdot a_{n-1} = 1 - 0 = 1$ ya que $a_{n+1}-3a_n+a_{n-1}=0$. $\square$