Recursiones lineales

Recursiones lineales de orden 2: la ecuación característica

Una recursión lineal homogénea de orden 2 tiene la forma $a_n = p \, a_{n-1} + q \, a_{n-2}$ con condiciones iniciales $a_1, a_2$ dadas y coeficientes $p, q$ constantes. Para resolver esta recursión, se busca una solución de la forma $a_n = r^n$: sustituyendo, $r^n = p r^{n-1} + q r^{n-2}$, y dividiendo por $r^{n-2}$: $r^2 = pr + q$. La ecuación característica es $r^2 - pr - q = 0$.

Si la ecuación característica tiene dos raíces distintas $r_1 \neq r_2$, la solución general es $a_n = A r_1^n + B r_2^n$, donde $A$ y $B$ se determinan con las condiciones iniciales. Si tiene una raíz doble $r_1 = r_2 = r$, la solución general es $a_n = (A + Bn) r^n$.

Ejemplo: resuelve $a_n = 5a_{n-1} - 6a_{n-2}$ con $a_1 = 2$, $a_2 = 5$. Ecuación característica: $r^2 - 5r + 6 = 0 \Rightarrow (r-2)(r-3) = 0 \Rightarrow r_1 = 2, r_2 = 3$. Solución general: $a_n = A \cdot 2^n + B \cdot 3^n$. Condiciones: $a_1 = 2A + 3B = 2$ y $a_2 = 4A + 9B = 5$. Restando: $2A + 6B = 3 \Rightarrow B = 1/2, A = 1/4$. Solución: $a_n = \dfrac{2^n}{4} + \dfrac{3^n}{2} = \dfrac{2^n + 2 \cdot 3^n}{4}$.

La sucesión de Fibonacci y la fórmula de Binet

La sucesión de Fibonacci está definida por $F_1 = 1$, $F_2 = 1$, $F_n = F_{n-1} + F_{n-2}$ para $n \geq 3$: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$ La ecuación característica es $r^2 = r + 1$, es decir $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 fórmula de Binet da el $n$-ésimo número de Fibonacci explícitamente: $F_n = \dfrac{\varphi^n - \hat{\varphi}^n}{\sqrt{5}}$. A pesar de involucrar irracionales, el resultado siempre es un entero positivo. Esto es porque $|\hat{\varphi}| = \dfrac{\sqrt{5}-1}{2} < 1$, por lo que $\dfrac{\hat{\varphi}^n}{\sqrt{5}} \to 0$ y $F_n$ es el entero más próximo a $\dfrac{\varphi^n}{\sqrt{5}}$.

Propiedades olímpicas de Fibonacci: $F_1 + F_2 + \cdots + F_n = F_{n+2} - 1$ (telescopa con $F_{k+2} - F_{k+1} = F_k$). $F_1^2 + F_2^2 + \cdots + F_n^2 = F_n F_{n+1}$. La identidad de Cassini: $F_{n-1} F_{n+1} - F_n^2 = (-1)^n$. Estas se demuestran por inducción o telescopaje.

La identidad de Cassini $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ es especialmente útil en concursos. Para $n=2$: $F_3 F_1 - F_2^2 = 2 \cdot 1 - 1 = 1 = (-1)^2$ ✓. Prueba por inducción: supuesto válido para $n$, se tiene $F_{n+2}F_n - F_{n+1}^2 = (F_{n+1}+F_n)F_n - F_{n+1}^2 = F_{n+1}F_n + F_n^2 - F_{n+1}^2 = F_n^2 - F_{n+1}(F_{n+1}-F_n) = F_n^2 - F_{n+1}F_{n-1} = -(-1)^n = (-1)^{n+1}$ ✓.

Recursiones no homogéneas y cambio de variable

Una recursión no homogénea tiene la forma $a_n = p a_{n-1} + q a_{n-2} + f(n)$, donde $f(n)$ es una función dada. La solución general es la suma de la solución homogénea (de $a_n = p a_{n-1} + q a_{n-2}$) más una solución particular. Para encontrar la particular, se prueba una forma similar a $f(n)$.

Ejemplo: resuelve $a_n = 2a_{n-1} + 3$ con $a_1 = 1$. Este es un caso de orden 1. La solución homogénea es $A \cdot 2^n$; para la particular, probamos $a_n^{(p)} = C$ (constante): $C = 2C + 3 \Rightarrow C = -3$. Solución general: $a_n = A \cdot 2^n - 3$. Con $a_1 = 2A - 3 = 1 \Rightarrow A = 2$. Luego $a_n = 2^{n+1} - 3$. Verificación: $a_1 = 4-3=1$ ✓, $a_2 = 2+3=5 = 2 \cdot 4 - 3$ ✓.

Otra técnica frecuente: el cambio de variable $b_n = a_n - L$ para encontrar un punto fijo $L$ de la recursión. Si $a_n = p a_{n-1} + c$, el punto fijo satisface $L = pL + c \Rightarrow L = c/(1-p)$ (si $p \neq 1$). Con $b_n = a_n - L$, la recursión se convierte en $b_n = p b_{n-1}$ (geométrica). Esto aplica al ejemplo anterior: $L = -3$, $b_n = a_n + 3$, $b_n = 2 b_{n-1}$, $b_n = b_1 \cdot 2^{n-1} = 4 \cdot 2^{n-1} = 2^{n+1}$, luego $a_n = 2^{n+1} - 3$ ✓.

Problemas olímpicos con recursiones

Problema 1 (ONEM tipo): Una sucesión satisface $a_1 = 1$, $a_2 = 3$ y $a_n = a_{n-1} + a_{n-2}$ para $n \geq 3$. Prueba que $a_n < 2^n$ para todo $n$. Por inducción: base: $a_1 = 1 < 2$ ✓ y $a_2 = 3 < 4$ ✓. Paso: $a_n = a_{n-1} + a_{n-2} < 2^{n-1} + 2^{n-2} = 2^{n-2}(2+1) = 3 \cdot 2^{n-2} < 4 \cdot 2^{n-2} = 2^n$ ✓.

Problema 2: Sea $a_n = 3a_{n-1} - 2a_{n-2}$ con $a_1 = 2$, $a_2 = 4$. Halla $a_n$. Ec. característica: $r^2 - 3r + 2 = (r-1)(r-2) = 0$, raíces $r_1 = 1$, $r_2 = 2$. $a_n = A + B \cdot 2^n$. Condiciones: $A + 2B = 2$ y $A + 4B = 4$. Entonces $2B = 2 \Rightarrow B = 1$, $A = 0$. Respuesta: $a_n = 2^n$. Verificación: $a_1 = 2$ ✓, $a_2 = 4$ ✓, $a_3 = 3 \cdot 4 - 2 \cdot 2 = 8 = 2^3$ ✓.

Problema 3 (concurso): Una rana salta escalones de $1$ o $2$ en $1$ o $2$. ¿De cuántas maneras puede subir $n$ escalones? Sea $f(n)$ el número de maneras. $f(1) = 1$, $f(2) = 2$ (1+1 ó 2), y $f(n) = f(n-1) + f(n-2)$ (el último salto fue de 1 ó de 2). Esta es exactamente la sucesión de Fibonacci desplazada: $f(n) = F_n$ donde $F_1 = 1, F_2 = 1, \ldots$ Así $f(10) = F_{10} = 55$.