Para un número entero positivo dado $M$ la secuencia $\{a_n\}$ comienza a partir de $a_{2M+1}=M(2M+1)$ y $a_k$ es el mayor múltiplo de $k$ no más de $a_{k+1}+M$ es decir $$a_k=k\left\lfloor\frac{a_{k+1}+M}{k}\right\rfloor,\quad k=1,2,\cdots,2M.$$ El problema original me pide que demuestre que $a_1<4M^2$ para $M\ge 3$ . Luego escribo un programa para comprobar grandes $M$ s como $M\sim10000000$ y sorprendentemente encontramos que $$\lim_{M\rightarrow\infty}\frac{a_1}{M^2}=\pi.$$ ¿Es esto cierto y por qué ocurre?
Respuesta
¿Demasiados anuncios?
steevc
Puntos
211
Tenga en cuenta que $a_k$ es siempre múltiplo de $k$ (en particular, esta estructura desbarata el modelo aleatorio propuesto en los comentarios). Podemos explotar esta estructura para simplificar la recurrencia y aclarar la dinámica haciendo que el cambio de variables $a_k = k (b_k - M)$ (el desplazamiento por $M$ es conveniente eliminar algunos términos de orden inferior), entonces $b_{2M+1} = 2M$ El $b_k$ son números enteros, y para $k=1,\dots,2M$ se tiene \begin{align*} b_k &= \frac{a_k}{k} + M\\ &= \left\lfloor \frac{a_{k+1}+M}{k} \right\rfloor + M \\ &= \left\lfloor \frac{(k+1)(b_{k+1}-M)+M}{k} \right\rfloor + M\\ &= (b_{k+1}-M) + \left\lfloor \frac{(b_{k+1}-M) + M}{k} \right\rfloor + M\\ &= b_{k+1} + \left\lfloor \frac{b_{k+1}}{k}\right \rfloor \end{align*} y así hemos llegado a la ecuación de diferencia $$ b_{k+1} - b_k = - \left\lfloor \frac{b_{k+1}}{k} \right\rfloor.$$ Así, como $k$ disminuye de $k+1$ , $b_k$ se incrementará en $1$ en el régimen $k \leq b_{k+1} < 2k$ , por dos en el régimen $2k \leq b_{k+1} < 3k$ etc. Se trata de una recurrencia bastante estable y puede analizarse mediante la técnica estándar de pasar a un límite reescalado y estudiar la ecuación diferencial asintótica resultante. Para simplificar, argumentamos heurísticamente. Esperamos $b_k$ tener magnitud $M$ cuando $k \sim M$ por lo que es natural introducir un reescalado $$ b_k = 2M f_M(\frac{k}{2M})$$ entonces tenemos la condición inicial $f_M(1 + \frac{1}{2M})=1$ y para $k = 2Mt$ para $0 \leq t \leq 1$ un múltiplo de $\frac{1}{2M}$ tenemos entonces tras un breve cálculo $$ \frac{f_M(t+\frac{1}{2M}) - f_M(t)}{1/2M} = - \left\lfloor \frac{f_M(t+\frac{1}{2M})}{t} \right\rfloor.$$ Pasar formalmente al límite $M \to \infty$ por lo que esperamos $f_M$ para converger en algún sentido adecuado a una función continua y diferenciable a trozos $f: [0,1] \to {\bf R}$ con $f(1)=1$ que resuelve la EDO $$ f'(t) = - \left\lfloor \frac{f(t)}{t} \right\rfloor$$ para todos $0 \leq t \leq 1$ . (Para hacer esto riguroso, se puede, por ejemplo, reescribir tanto la ecuación en diferencias como la supuesta EDO limitante como ecuaciones de suma parcial y ecuaciones integrales respectivamente para mejorar la estabilidad, y luego aplicar un teorema de compacidad como el teorema de Arzela-Ascoli para concluir, en el espíritu de la construcción de varias soluciones suaves o débiles en EDP). Se puede pensar intuitivamente en la gráfica de $f$ como la trayectoria de un rayo de luz que atraviesa diferentes medios y se desplaza en línea recta hasta chocar con una de las fronteras planas. $f(t)=t$ , $f(t)=2t$ , $f(t)=3t$ etc., en cuyo punto se "refracta" con una pendiente diferente. (Un diagrama numérico de los gráficos de $f$ y $f_M$ para algunos razonablemente grandes $M$ sería bastante revelador, pero en estos momentos no dispongo de tiempo para generar estos gráficos).
Se puede resolver esta EDO explícitamente a partir de la condición inicial $f(1)=1$ como una función lineal continua a trozos. Si definimos la secuencia $1 = t_0 > t_1 > t_2 > \dots$ mediante la recursión $$ t_n = \frac{2n}{2n+1} t_{n-1}$$ para que $t_n$ es un semiproducto de Wallis parcial $$ t_n = \frac{2}{3} \cdot \frac{4}{5} \cdot \dots \cdot \frac{2n}{2n+1} = \frac{(n! 2^n)^2}{(2n+1)!}$$ (que ya empieza a insinuar la aparición de $\pi$ ) entonces se puede demostrar por inducción que $$ f(t) = n t_{n-1} + n(t_{n-1}-t) = (n+1) t_n - n (t-t_n)$$ para $t_n \leq t \leq t_{n-1}$ y todos $n \geq 1$ . En particular $$ f(t_n) = (n+1) t_n.$$
A partir de la aproximación de Stirling tenemos para grandes $n$ que $$ t_n = \frac{(n! 2^n)^2}{(2n+1)!} \sim \frac{\sqrt{\pi}}{2\sqrt{n}}.$$ Observamos que esta asíntota también puede derivarse de (y de hecho es equivalente a) la Producto Wallis $\frac{\pi}{2} = (\frac{2}{1} \cdot \frac{2}{3}) \cdot (\frac{4}{3} \cdot \frac{4}{5}) \cdot (\frac{6}{5} \cdot \frac{6}{7}) \cdot \dots$ tras algunas manipulaciones algebraicas rutinarias.
Así, si $k \approx 2M t_n \approx 2M \frac{\sqrt{\pi}}{2\sqrt{n}}$ entonces $$ b_k \approx 2M f(t_n) \approx (n+1) 2M \frac{\sqrt{\pi}}{2\sqrt{n}}$$ y por lo tanto \begin{align*} a_k &\approx k(b_k-M) \\ &\approx 2M \frac{\sqrt{\pi}}{2\sqrt{n}} ((n+1) 2M \frac{\sqrt{\pi}}{2\sqrt{n}} - M )\\ &\approx M^2 (\pi + O(n^{-1/2})). \end{align*} Envío de $n \to \infty$ moralmente obtenemos $$ a_1 \approx M^2 \pi$$ como se esperaba.
Es probable que una contabilidad cuantitativa más cuidadosa de los términos de error pueda convertir el análisis heurístico anterior en un argumento riguroso, pero dejo esto al lector interesado.
Observamos también que esta recurrencia puede utilizarse para obtener un algoritmo (bastante ineficiente) para calcular $\pi$ en una simple máquina sumadora, básicamente implementando la fórmula del producto de Wallis de forma bastante pedestre.
