Sea $a_1, a_2, a_3, ...$ una secuencia de enteros positivos satisfaciendo las siguientes condiciones $$a_1=1,$$ $$a_{n+1}=a_n+a_{\lfloor \sqrt{n}\rfloor} \text{ para todo } n\geq 1$$ Pruebe que para cada entero positivo $k$ existe un término $a_i$ que es divisible por $k$.
Nota: El símbolo $\lfloor x \rfloor$ denota al mayor número entero que es menor o igual a $x$.
Que raro, porque vi este mismo problema pero de Brasil... Brazil TST cono 2020 P3
Incluso es la misma prueba y del mismo año, solo cambia el número de problema
Sea $x$ la diferencia entre $a_{n+1}$ y $a_n$, lo que va aumentando. Por enunciado, $x = a_{\sqrt{n}}$
Primeros elementos de la secuencia:
$1, 2, 3, 4, 6, 8, 10, 12, 14, 17, 20, 23, 26, 29, 32, 35, 39...$
Un elemento tiene un tal $x$ si se utilizó $x$ más el anterior para formarlo. Del 2 al 4 inclusive, $x = 1$. Del 6 al 14 inclusive, $x = 2$. Del 17 al 35 inclusive, $x = 3$. Y así en adelante, $x$ va aumentando de uno en uno ya que $x$ es la raíz de $n$ (por lo menos la parte entera) y $n$ va aumentando de uno en uno. En cuanto $n$ supera o iguala a un cuadrado, $x$ aumenta 1.
Como la secuencia es infinita, $x$ va a tomar el valor de cada número. Sea $a_y$ el primer elemento con $x = k$.
Voy a utilizar notación modular, en la cual $a \equiv b \pmod{c}$ implica que $a$ tiene el mismo resto que $b$ a la hora de dividir por $c$. Ejemplo: $7 \equiv 10\pmod{3}$.
Nosotros queremos conseguir desde un $a_y$ con cualquier resto, siempre llegar a un resto $0$, es decir a un múltiplo de $k$. Sea $z$ el resto de $a_y$ módulo $k \to a_y \equiv z \pmod k$. Desde $a_y$, se empieza a sumar $k$ varias veces. Pero como $k \equiv 0 \pmod k$, la suma de varias $k$ nunca variará el resto módulo $k$, $z$ se mantiene.
Sin embargo, en algún punto, $x$ pasa a ser igual a $k+1$. Y desde ahí se empiezan a sumar muchos $k+1$, y lo que nos importa en los restos, muchos 1. Sea $q$ la cantidad de unos que tenemos, es decir la cantidad de elementos cuyo $x = k+1$ Si tenemos suficientes unos tal que $z+1q = k$, entonces el resto sería $0$, y obtendríamos un múltiplo de $k$.
$z$ es un resto, por lo que está dentro del rango $(1,2,3,...(k-2),(k-1))$ Entonces, lo que le falta para llegar a $k$ (los posibles $q$), son también $k-1$ posibilidades. Volvamos a analizar la secuencia:
$1, 2, 3, 4, 6, 8, 10, 12, 14, 17, 20, 23, 26, 29, 32, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 76, 81, 86, 91, 96, 101, 106, 111, 116, 121, 126, 132, 138, 144, 150, 156, 162, 168, 174, 180 $
3 elementos con $x = 1 (2, 3, 4)$ . 5 elementos con $x = 2 (6, 8, 10, 12, 14)$. 7 elementos con $x = 3 (17, 20, 23, 26, 29, 32, 35)$ 9 elementos con $x = 4 (39, 43, 47, 51, 55, 59, 63, 67, 71)$
Se puede ver la secuencia: $x$ aumenta de uno en uno (como habíamos dicho antes) y $q$ aumenta de dos en dos, formando todos los impares excepto el 1. Por lo que: $2x+1 = q$
¿Pero cómo sabemos que no es solo una coincidencia del comienzo? Porque lo que dictamina qué números tienen qué x son los cuadrados, mejor dicho los números entre los cuadrados. Cuanto más diferencia hay entre dos cuadrados, más números entre medio tendrán un $n$ que todavía no llega al próximo cuadrado y por lo tanto tiene el $x$ del anterior. Los cuadrados tienen una propiedad: son sumas de impares consecutivos.
$1 = 1^2$
$1 + 3 = 2^2$
$1 + 3 + 5 = 3^2$
$1 + 3 + 5 + 7 = 4^2$
$1 + 3 + 5 + 7 + 9 = 5^2$
Al ver esto, es posible darse cuenta que la diferencia entre dos de ellos es siempre un impar y va de manera progresiva, aumentando cada vez más. Por esto, podemos realmente comprobar que $2x+1 = q$
Volviendo a lo anterior, en el momento que necesitamos más de $k-1$ unos, $x = k+1 \to 2(k+1) = q \to 2k+k = q$
Definitivamente, $2k+k>k-1$, por lo que vamos a tener la cantidad de unos que necesite $z$ para cualquier $z$, logrando un múltiplo de k.
Pero ahora me doy cuenta que eso si la secuencia fuera con diferencia $\sqrt{n}$, y no con $a_\sqrt{n}$
Supongamos que $k$ es tal que no existe $n$ tal que $k \mid a_n$. Lo siguiente es obvio.
1. Si $0 \leq r \leq 2n + 1$ entonces $a_{n^2 + r} = a_{n^2} + r a_n$.
2. Si $n \geq k$ y $0 \leq r \leq 2n + 1$ entonces $(a_n, k) \nmid (a_{n^2 + r}, k)$.
Prueba. Por el absurdo. Supongamos que $(a_n, k) \mid (a_{n^2 + r}, k)$. Tenemos $d = (a_n, k) \mid a_{n^2 + r}$. Por 1, $d \mid a_{n^2}$, por lo que $a_{n^2 + t}/d = a_{n^2}/d + t a_n/d$ para todo $t$ con $0 \leq t \leq 2n + 1$. Tenemos $(a_n/d, k/d) = 1$, por lo que hay $t$ con $0 \leq t < k/d \leq 2n + 1$ tal que $k/d \mid a_{n^2}/d + t a_n/d$. Esto implica $k/d \mid a_{n^2 + t}/d$, por lo que $k \mid a_{n^2 + t}$, absurdo.
3. Si $n \geq k$ hay $r \geq 0$ tal que $(a_{n^2 + r}, k) < (a_n, k)$.
Prueba. Usamos el siguiente procedimiento. Empezamos con $d = 1$, y nos aseguramos que en cada paso $d$ divide a $k$, $a_n$ y $a_{n^2 + r}$ para todo $r$ con $0 \leq r \leq 2n + 1$.
Tomemos $r = \prod_{p \mid k/d, p \nmid a_{n^2}/d} p$, el producto de los primos que dividen a $k/d$ pero no dividen a $a_{n^2}/d$. Notar que $r \leq k \leq n$, asi que podemos usar 1. Dos casos:
I. Si $(a_{n^2 + r}/d, k/d) = 1$ entonces $(a_{n^2 + r}, k) = d$, y $d \mid (a_n, k)$ por hipotesis, luego $(a_{n^2 + r}, k) \mid (a_n, k)$. Por 2, no puede ser $(a_n, k) \mid (a_{n^2 + r}, k)$, asi que $(a_{n^2 + r}, k) < (a_n, k)$ y terminamos.
II. Si $(a_{n^2 + r}/d, k/d) > 1$ sea $p$ primo con $p \mid (a_{n^2 + r}/d, k/d)$. O bien $p \mid a_{n^2}/d$ o bien $p \mid r$. Si $p \mid r$ entonces $p \mid a_{n^2}/d$ ya que $a_{n^2 + r}/d = a_{n^2}/d + r a_n/d$, pero esto es absurdo por la definicion de $r$. Entonces $p \mid a_{n^2}/d$. Por 1 esto implica $p \mid a_n/d$, y $p \mid k/d$ por la definicion de $p$. Luego tomando $d \leftarrow pd$ podemos repetir el procedimiento.
Notar que en cada paso $d$ aumenta, pero $d \leq k$ ya que $d \mid k$, luego en algun momento esto termina, y obtenemos $(a_{n^2 + r}, k) < (a_n, k)$, como queriamos.
Conclusion. Tomamos $n \geq k$. Usando 3 repetidamente obtenemos una secuencia $n_t$ creciente con $(a_{n_t}, k)$ decreciente. Esto es imposible porque $(a_{n_t}, k) > 0$.
