Recursiones no lineales: técnicas de análisis

Por qué las recursiones no lineales son difíciles

Una recursión lineal como $a_{n+1} = \alpha a_n + \beta$ tiene solución explícita inmediata. Las recursiones no lineales, en cambio, raramente admiten fórmula cerrada. La pregunta olímpica típica no pide "¿cuánto vale $a_n$?" sino "¿es siempre entero?", "¿converge?", "¿es acotada?", "¿qué valores toma?".

El ejemplo canónico es $a_{n+1} = a_n^2 - 2$. Si $a_1 = 2\cos\theta$, entonces $a_n = 2\cos(2^{n-1}\theta)$ — esto se ve sustituyendo $a_n = 2\cos\phi_n$ y usando $2\cos^2\phi - 2 = 2\cos(2\phi)$. Esta sustitución trigonométrica lineariza la recursión: convierte $a_{n+1} = a_n^2 - 2$ en $\phi_{n+1} = 2\phi_n$.

La lección central: ante una recursión no lineal, la primera pregunta es **¿existe una sustitución $a_n = f(b_n)$ que la linealice?** Las sustituciones más útiles son trigonométricas, hiperbólicas, o vía potencias.

Catálogo de sustituciones linealizantes

**Tipo $a_{n+1} = \frac{\alpha a_n + \beta}{\gamma a_n + \delta}$ (Möbius / fracción lineal).** Toda transformación de Möbius es conjugada (en $\mathbb{C}$ o en $\mathbb{R}$ extendido) a una dilatación, traslación, o rotación, según sus puntos fijos. Si la transformación tiene dos puntos fijos $r, s$, la sustitución $b_n = \frac{a_n - r}{a_n - s}$ convierte la recursión en $b_{n+1} = \lambda b_n$ (lineal multiplicativa). Si tiene un punto fijo doble $r$, la sustitución $b_n = \frac{1}{a_n - r}$ da $b_{n+1} = b_n + c$ (lineal aditiva).

**Tipo $a_{n+1} = 2a_n^2 - 1$.** Sustitución: $a_n = \cos\theta_n$. Entonces $a_{n+1} = 2\cos^2\theta_n - 1 = \cos(2\theta_n)$, así $\theta_{n+1} = 2\theta_n$.

**Tipo $a_{n+1} = a_n^2$.** Sustitución: $a_n = e^{b_n}$, lo que da $b_{n+1} = 2b_n$, con solución $b_n = 2^{n-1}b_1$.

**Tipo $a_{n+1} = a_n + \frac{1}{a_n}$ (recursión del tipo armónico).** Esta no se linealiza directamente. Pero se puede demostrar que $a_n^2 \approx 2n$ para $n$ grande: basta notar que $a_{n+1}^2 = a_n^2 + 2 + \frac{1}{a_n^2}$, así $a_n^2 = a_1^2 + 2(n-1) + \sum_{k=1}^{n-1}\frac{1}{a_k^2}$, y el último término es $O(\log n)$ si $a_k^2 \sim 2k$.

**Tipo $a_{n+2} = \frac{a_{n+1}^2 + c}{a_n}$ (Somos-like). Estas recursiones pueden ser enteras por el teorema de Laurent**: si los valores iniciales y los coeficientes son enteros, $a_n$ es siempre un polinomio de Laurent en $a_1, a_2$ con coeficientes enteros. Esta es una de las maravillas de la combinatoria algebraica moderna.

Puntos fijos y su papel en el análisis cualitativo

Sea $a_{n+1} = f(a_n)$ con $f$ continua. Un punto fijo es $r$ tal que $f(r)=r$. Si $|f'(r)| < 1$ el punto fijo es atractor: toda órbita que empiece suficientemente cerca de $r$ converge a $r$. Si $|f'(r)|>1$ es repulsor.

Demostración de convergencia por puntos fijos atractores. Supongamos $f:[a,b]\to[a,b]$ con $|f'(x)|\leq L < 1$ para todo $x\in[a,b]$. Entonces $f$ es una contracción y tiene un único punto fijo $r\in[a,b]$ (Banach). Además $|a_{n}-r|\leq L^{n-1}|a_1-r|\to 0$.

En olimpiadas, el uso típico es: se define la sucesión $a_{n+1}=f(a_n)$, se encuentra el único punto fijo $r$ de $f$ en el intervalo relevante, y se demuestra por inducción que $a_n\in[r-\varepsilon, r+\varepsilon]$ para todo $n$ (y luego que $a_n\to r$).

Ejemplo. Sea $a_1=2$ y $a_{n+1}=\frac{1}{2}\left(a_n+\frac{2}{a_n}\right)$ (método de Newton para $\sqrt{2}$). El punto fijo satisface $r=\frac{1}{2}(r+2/r)$, es decir $r^2=2$. Como $a_n>0$ para todo $n$, el punto fijo relevante es $r=\sqrt{2}$. Verificamos $|f'(x)| = \frac{1}{2}|1-\frac{2}{x^2}|$; para $x\geq\sqrt{2}$ esto es $\leq \frac{1}{2}$. Convergencia cuadrática: $a_{n+1}-\sqrt{2} \approx \frac{(a_n-\sqrt{2})^2}{2\sqrt{2}}$.

Funciones de Lyapunov y monotonía

Cuando no hay convergencia a un punto fijo sino acotación, la herramienta clave es una función de Lyapunov: una función $V(a_n)$ que sea decreciente (o no creciente) a lo largo de la órbita y acotada inferiormente.

Método. Para demostrar que $a_n$ está acotada: buscar $V:\mathbb{R}\to\mathbb{R}$ tal que $V(a_{n+1})\leq V(a_n)$ y $V(x)\geq C$ para todo $x$ relevante. Entonces $\{V(a_n)\}$ converge, y si $V$ es inyectiva o estrictamente convexa, esto fuerza que $\{a_n\}$ sea de Cauchy.

Ejemplo olímpico (IMO 2006, P5 variante). Sea $a_1, a_2 > 0$ y $a_{n+2} = \frac{1+a_{n+1}}{a_n}$. Calcular $V_n = a_n + a_{n+1} + \frac{1}{a_n a_{n+1}}$. Sustituyendo: $V_{n+1} = a_{n+1}+\frac{1+a_{n+1}}{a_n}+\frac{a_n}{a_{n+1}(1+a_{n+1})}$... la cuenta directa muestra que $V_n$ es constante (invariante de la recursión). Esto es típico: cuando la recursión es "integralmente cerrada", existe un invariante exacto en lugar de una función decrece.

Criterio de comparación. Si $a_n\leq b_n$ para todo $n$ y la sucesión $(b_n)$ cumple la misma recursión (o una más rápida), y $(b_n)$ converge, entonces $(a_n)$ está acotada. Esta idea de "sandwiching" o "squeeze" se combina con inducción fuerte para muchos problemas olímpicos.

Técnica de la derivada discreta. Si $d_n = a_{n+1} - a_n$ y se puede demostrar que $|d_n|\leq r^n$ con $r<1$, entonces $\sum |d_n| < \infty$ y por tanto $(a_n)$ es de Cauchy, luego convergente.

Problema IMO resuelto: recursión cuadrática y enteros

Problema (IMO Shortlist 2007, A2). Sea $a_0$ un entero positivo. Definimos $a_{n+1} = a_n + \lfloor \sqrt{a_n} \rfloor$ para $n\geq 0$. Demostrar que existe un índice $N$ tal que para todo $n\geq N$, $a_n$ es un cuadrado perfecto.

Solución. Sea $a_n = k^2 + r$ con $0\leq r < 2k+1$ (escritura única). Entonces $\lfloor\sqrt{a_n}\rfloor = k$, y $a_{n+1} = k^2+r+k$.

Caso 1: $r=0$. Entonces $a_n = k^2$ es cuadrado perfecto. $a_{n+1}=k^2+k$. Seguimos desde ahí.

Caso 2: $r\geq 1$. Iterar: $a_{n+j} = k^2 + r + jk$ para $j$ pequeño (mientras $a_{n+j}$ no supere $(k+1)^2 = k^2+2k+1$). El umbral se alcanza cuando $r+jk\geq 2k+1$, es decir $j\geq \lceil(2k+1-r)/k\rceil$. Para $j=2$: $a_{n+2}=k^2+r+2k = (k+1)^2 + (r-1)$. ¡El resto decreció en 1! Inductivamente, el resto $r$ disminuye en 1 por cada dos pasos (mientras $r\geq 1$), así que después de a lo más $2r\leq 2(2k)=4k$ pasos, se llega a un cuadrado perfecto. Pero cuando llegamos a $(k+1)^2$, la nueva "base" es $k+1$ y el proceso se repite.

Más precisamente: desde $a_n = k^2$ (cuadrado), $a_{n+1}=k^2+k$, $a_{n+2}=k^2+2k = (k+1)^2-1$, $a_{n+3}=(k+1)^2-1+k+1 = (k+1)^2+k$, $a_{n+4}=(k+1)^2+2(k+1)-1=(k+2)^2-1$, ... El patrón muestra que si alguna vez $a_n = m^2-1$ para $m$ grande, se repite indefinidamente: $a_{n+2}=(m+1)^2-1$. Esto contradice la hipótesis de que se llega a un cuadrado eventualmente, a menos que lleguemos a $r=0$ antes.

El análisis correcto: sea $r_n = a_n - \lfloor\sqrt{a_n}\rfloor^2$. Si $r_n=0$: cuadrado, $r_{n+1} = \lfloor\sqrt{a_n}\rfloor = k$. Si $r_n=k$ (con $k=\lfloor\sqrt{a_n}\rfloor$): $a_{n+1}=k^2+2k=(k+1)^2-1$, $r_{n+1}=2k+1-(k+1)\cdot 0$... se verifica directamente que en dos pasos más se llega al cuadrado $(k+1)^2$. Así hay infinitos cuadrados perfectos en la sucesión, y a partir del primero todos lo son eventualmente. $\blacksquare$