Convergencia y periodicidad en sucesiones olímpicas

Dicotomía: convergencia vs. periodicidad

Para una sucesión $\{a_n\}\subset S$ con $S$ finito, la sucesión es siempre eventualmente periódica (palomar: infinitas visitas a un conjunto finito obligan a repetir). Para $S$ infinito, convergencia y periodicidad son posibilidades distintas.

Criterio de periodicidad (palomar). Si la sucesión toma valores en un conjunto finito $S = \{s_1, \ldots, s_m\}$, entonces existe $N$ y $T\geq 1$ tal que $a_{n+T}=a_n$ para todo $n\geq N$.

Criterio de convergencia. Si $\{a_n\}$ es monótona y acotada (en $\mathbb{R}$), converge. Si $\{a_n\}$ es de Cauchy, converge.

Criterio mixto: acotada + casi periódica. Si $|a_{n+T}-a_n|\leq c^n$ con $c<1$, la sucesión converge (la "periodicidad" se amortigua exponencialmente hacia un límite).

En olimpiadas, es habitual demostrar primero que la sucesión está acotada (Lyapunov / comparación), luego que es de Cauchy o que las diferencias $a_{n+1}-a_n$ son de signo alternante y módulo decreciente (telescopio convergente).

Invariantes exactos y primeras integrales

Una cantidad $I_n = I(a_n, a_{n+1}, \ldots)$ que no varía a lo largo de la sucesión se llama invariante exacto o primera integral. Si existe tal $I_n$, las órbitas están confinadas en los conjuntos de nivel $\{I=c\}$.

Ejemplo clásico (IMO 2006, P5). Sea $a_1,a_2$ reales positivos y $a_{n+2}=\frac{1+a_{n+1}}{a_n}$ para $n\geq 1$. Demostrar que la sucesión es periódica de período 5.

Solución. Calculamos directamente:

$a_3 = \frac{1+a_2}{a_1}$

$a_4 = \frac{1+a_3}{a_2} = \frac{1+\frac{1+a_2}{a_1}}{a_2} = \frac{a_1+1+a_2}{a_1 a_2}$

$a_5 = \frac{1+a_4}{a_3} = \frac{1+\frac{a_1+1+a_2}{a_1 a_2}}{\frac{1+a_2}{a_1}} = \frac{\frac{a_1 a_2 + a_1 + 1 + a_2}{a_1 a_2}}{\frac{1+a_2}{a_1}} = \frac{a_1 a_2 + a_1 + a_2 + 1}{a_2(1+a_2)} = \frac{(1+a_1)(1+a_2)}{a_2(1+a_2)} = \frac{1+a_1}{a_2}$

$a_6 = \frac{1+a_5}{a_4} = \frac{1+\frac{1+a_1}{a_2}}{\frac{1+a_1+a_2}{a_1 a_2}} = \frac{\frac{a_2+1+a_1}{a_2}}{\frac{1+a_1+a_2}{a_1 a_2}} = \frac{a_1 a_2 (1+a_1+a_2)}{a_2(1+a_1+a_2)} = a_1$

$a_7 = \frac{1+a_6}{a_5} = \frac{1+a_1}{\frac{1+a_1}{a_2}} = a_2$.

Luego $a_6=a_1$ y $a_7=a_2$: la sucesión es periódica de período 5. $\blacksquare$

Semi-invariantes y convergencia garantizada

Si no hay un invariante exacto, buscamos un semi-invariante (Lyapunov): $V_n$ con $V_{n+1}\leq V_n$ y $V_n\geq 0$.

Lema de Lyapunov discreto. Si $V_n\geq 0$ y $V_{n+1}\leq V_n$ para todo $n\geq N_0$, entonces $V_n$ converge a algún $L\geq 0$. Si además $V_{n+1}\leq V_n - \varepsilon$ cuando $a_n\notin E$ (con $E$ un conjunto "de equilibrio"), entonces $a_n$ entra en $E$ en tiempo finito.

Ejemplo (sucesión de Heron). $a_1 > 0$, $a_{n+1} = \frac{1}{2}\left(a_n + \frac{A}{a_n}\right)$ para $A>0$ fijo. Sea $V_n = a_n - \sqrt{A}$. Entonces $V_{n+1} = a_{n+1}-\sqrt{A} = \frac{1}{2}(a_n+A/a_n)-\sqrt{A} = \frac{(a_n-\sqrt{A})^2}{2a_n} = \frac{V_n^2}{2a_n} \geq 0$. Además $V_{n+1} = V_n\cdot\frac{V_n}{2a_n}\leq V_n\cdot\frac{V_n}{2\sqrt{A}} < V_n$ para $V_n < 2\sqrt{A}$, que se cumple para todo $n\geq 2$ (ya que $a_2\geq\sqrt{A}$). Convergencia cuadrática hacia $\sqrt{A}$.

Técnica del telescopio con signo alternante. Si $(-1)^n(a_{n+1}-a_n)\geq 0$ y $|a_{n+1}-a_n|\leq |a_n-a_{n-1}|/2$, la sucesión converge (serie alternante con términos que tienden a 0). Esto aparece en sucesiones de tipo "valor absoluto": $a_{n+1} = |a_n - a_{n-1}|$, donde se puede demostrar convergencia a 0.

Invariante de paridad. Para sucesiones en $\mathbb{Z}$, la paridad de $a_n$ puede ser invariante o alternar, lo que restringe los posibles puntos fijos y períodos. Si $a_{n+1}\equiv a_n+1 \pmod{2}$ siempre, la paridad alterna y no hay puntos fijos enteros.

Periodicidad en sucesiones de enteros: palomar y órbitas finitas

Principio del palomar para sucesiones. Si $\{a_n\}\subset\{0,1,\ldots,M\}$ para algún $M$ finito, necesariamente $a_i = a_j$ para algún $i < j$. Si la sucesión es determinista (el próximo término depende solo del actual), esto implica periodicidad eventual.

**Recursión módulo $m$.** Si $a_{n+1} \equiv f(a_n) \pmod{m}$ (con $f$ determinada), la sucesión de residuos módulo $m$ es eventualmente periódica. Esto se usa para demostrar divisibilidades o para probar que ciertos valores son imposibles.

Ejemplo. Sea $a_1=1$ y $a_{n+1} = a_n^2 + 1$. Módulo 3: $a_1\equiv 1$, $a_2 = 2 \equiv 2$, $a_3 = 5\equiv 2$, $a_4 = 26\equiv 2$. La sucesión de residuos módulo 3 entra en el ciclo $(2)$ desde $n=2$. Luego $3\nmid a_n$ para $n\geq 2$ (ya que $a_n\equiv 2\pmod 3$). Esto prueba que ningún $a_n$ con $n\geq 2$ es divisible por 3.

Periodicidad de la sucesión completa. Es mucho más exigente: requiere que la sucesión sea periódica en $\mathbb{Z}$, no solo módulo $m$. Para recursiones en conjuntos finitos (como permutaciones o estados), es automática. Para recursiones en $\mathbb{Z}$, solo ocurre si la función $f$ tiene puntos periódicos con todos los valores iniciales en una órbita periódica.

Distinción importante. La sucesión $a_{n+1}=\frac{1+a_{n+1}}{a_n}$ (lección anterior) es periódica en $\mathbb{R}_{>0}$: todas las condiciones iniciales positivas dan órbitas de período 5. La sucesión $a_{n+1}=a_n^2-2$ solo es periódica si $a_1 = 2\cos(\pi p/q)$ con $p,q$ enteros.

Problema IMO resuelto: periodicidad de sucesión entera

Problema (IMO Shortlist 2010, A1). Sea $a_1, a_2, \ldots$ una sucesión de enteros con la propiedad de que $i\mid a_i$ para todo $i\geq 1$, y $|a_i-a_j|\leq i+j$ para todo $i\neq j$. Demostrar que si $a_1\geq 0$ y la sucesión está acotada superiormente, entonces $a_n = n$ para todo $n$ suficientemente grande.

Solución. De $i\mid a_i$ y $|a_i-a_j|\leq i+j$: poner $j=1$: $|a_i - a_1|\leq i+1$. Poner $j=i-1$: $|a_i-a_{i-1}|\leq 2i-1$. Poner $i=j+1$: $|a_{j+1}-a_j|\leq 2j+1$.

Sea $b_i = a_i/i$ (racional). La condición $i\mid a_i$ dice $b_i\in\mathbb{Z}$, y la acotación dice $b_i\in[C_1, C_2]$ para algún intervalo. La condición $|a_i-a_j|\leq i+j$ con $j=\lfloor i/2\rfloor$ da $|a_i - a_{i/2}|\leq 3i/2$, es decir $|ib_i - \frac{i}{2}b_{i/2}|\leq 3i/2$, así $|b_i - b_{i/2}/2|\leq 3/2 +$ corrección.

La clave es que $a_i \equiv 0 \pmod i$ y la acotación implican que para $i$ grande, $a_i/i$ está cerca de un entero fijo. Con $j=1$: $a_i = a_1 + O(i)$ no da unicidad. Pero $i\mid a_i$ y $a_i = i\cdot k_i$ con $k_i$ entero acotado. La condición $|ik_i - jk_j|\leq i+j$ con $i\neq j$ grandes y $i/j\to 1$ fuerza $k_i=k_j$ eventualmente. Si $k_i = k$ para todo $i$ grande, entonces $a_i = ki$ y la condición $|ki - kj|\leq i+j$, es decir $|k||i-j|\leq i+j$, se cumple con $k=1$ (y falla para $|k|\geq 2$ cuando $i$ y $j$ tienen misma paridad y $|i-j|$ es grande). Luego $k=1$ y $a_n=n$ para todo $n$ suficientemente grande. $\blacksquare$