Cómo probar este bonito límite de $\lim_{n\to\infty}\frac{a_{n}}{n}=\frac{12}{\log{432}}$

Question

Problema:

Deje $a_{0}=1$ y $$a_{n}=a_{\left\lfloor n/2\right\rfloor}+a_{\left\lfloor n/3 \right\rfloor}+a_{\left\lfloor n/6\right\rfloor}.$$ Mostrar que

$$\lim_{n\to\infty}\dfrac{a_{n}}{n}=\dfrac{12}{\log{432}},$$

donde $\lfloor x \rfloor$ es el mayor entero no mayor que $x$.

Se dice que este problema fue creado por Paul Erdős, y no puedo encontrar esta solución del problema, ¿alguien tiene alguna agradable métodos? Gracias.

Answer 1

He aquí una prueba probabilística. Vamos $X_t$ ($t=0,1,\ldots$) ser un proceso de Markov en los enteros positivos con $X_0=1$ y, para cada una de las $t\ge0$, $$ X_{t+1}=\begin{cases} 2X_t,&\text{with probability }1/2,\\ 3X_t,&\text{with probability }1/3,\\ 6X_t,&\text{with probability }1/6. \end{casos} $$ Si dejamos $p_t(n)=\mathbb{P}(X_t=n)$, entonces podemos ver que $$ p_{t+1}(n)=1_{\{2\mediados n\}}p_t(n/2)/2+1_{\{3\a mediados n\}}p_t(n/3)/3+1_{\{6\a mediados n\}}p_t(n/6)/6. $$ Suma más de $t$ da la probabilidad de que $X$ alguna vez visitas de estado $n$. $$ p(n)=\mathbb{E}\left[\sum_t1_{\{X_t=n\}}\right]=\sum_t\mathbb{P}(X_t=n)=\sum_tp_t(n). $$ Esto satisface $$ p(n)=\frac121_{\{2\mediados n\}}p(n/2)+\frac131_{\{3\mediados n\}}p(n/3)+\frac161_{\{6\mediados n\}}p(n/6) $$ para$n\gt1$$p(1)=1$. Ahora, vamos a $a_n$ ser la secuencia definida en la pregunta, y establecer $b_n=a_n-a_{n-1}$. Esto satisface $b_1=2$$b_n=1_{\{2\mid n\}}b_{n/2}+1_{\{3\mid n\}}b_{n/3}+1_{\{6\mid n\}}b_{n/6}$$n > 1$. Vemos entonces que el $b_n$ cumple la misma condición inicial y de la recurrencia de la relación como $2np(n)$, lo $b_n=2np(n)$. Por lo tanto, $$ \begin{array}{ccr} \begin{align} \frac{a_N-1}{N}&=\frac2N\sum_{n=1}^Nnp(n)=\frac2N\sum_{n=1}^N\mathbb{E}\left[\sum_tn1_{\{X_t=n\}}\right]\\ &=\frac2N\mathbb{E}\left[\sum_tX_t1_{\{X_t\le N\}}\right]. \end{align}&&{\rm(1)} \end{array} $$ La última igualdad se obtiene mediante el movimiento de la suma de $n$ dentro de la expectativa y los desplazamientos con la integral.

Podemos calcular (1) en el límite de $N\to\infty$ mediante la renovación de la teoría. Las variables aleatorias $U_t=\log(X_t/X_{t-1})$ son independientes e idénticamente distribuidas con $\mathbb{P}(U_t=\log a)=a^{-1}$$a\in\{2,3,6\}$. Ha decir $c\equiv\mathbb{E}[U_t]=(\log 432)/6$. En términos del proceso de $Y_t=U_1+\cdots+U_t$, (1) se convierte en $$ \frac{a_N}N=2\mathbb{E}\left[\sum_t 1_{\{Y_t-\log N\le0\}}e^{Y_t-\log N}\right]+\frac1N. $$ La renovación teorema dice que, en el límite de $\log N\to\infty$, esto converge a $$ 2c^{-1}\int_{-\infty}^\infty 1_{\{y\le0\}}e^ydy=\frac2c=\frac{12}{\log 432}. $$ Estoy usando la versión de la renovación teorema declaró en Kallenberg, Bases de la Moderna Probabilidad (Segunda Ed.), Teorema 9.20, y también se conoce como la Clave de la Renovación Teorema. La condición previa para la distribución de $U_t$ para este (y otros de integrabilidad) es que su apoyo no está contenido en $\alpha\mathbb{Z}$ cualquier $\alpha$. Esto es cierto como los cocientes de las $\log2,\log3,\log6$ no son todos racionales.

Answer 2

Este es un muy bonito problema!

Como se discute en la pregunta/comentario/una de las respuestas acerca de la historia de este problema, permítanme relatar aquí lo que he encontrado. Estoy haciendo esto en la comunidad de la wiki, ya que no es exactamente una respuesta a la pregunta.

En las Matemáticas de la Revista, que se publica cinco veces al año por la Asociación Matemática de América, en el noviembre de 1982 problema (Vol. 55, Nº 5), en la sección de problemas (p. 300), los siguientes (mucho más fácil) problema se planteó de forma anónima (o más bien, por "Anon, erewhon pur-en-español del Río", que parece un prolífico colaborador) como la resolución 1158 (he cambiado la notación un poco):

Set $a_0 = 1$ y para $n \ge 1$, $a_n = a_{\lfloor n/2 \rfloor} + a_{\lfloor n/3 \rfloor}$. Encontrar $\lim_{n\to\infty} a_n/n$.

Esto es mucho más fácil problema, como $\frac12 + \frac13 \neq 1$. (Sugerencia: pruebe el polinomio de crecimiento.)

Las soluciones a este problema 1158 fueron dadas en el enero de 1984 problema (Vol. 57, Nº 1)'s sección de Problemas (pp 49-50), bajo el título de Un Pseudo-Fibonacci Límite, donde fue resuelto por una multitud de personas.

Uno de ellos fue Daniel A. Rawsthorne, Wheaton, Maryland, que en la misma sección de la misma edición (p. 42), propuso el más difícil problema *1185. El asterisco significa que propuso el problema sin dar una solución a sí mismo.

Set $a_0 = 1$ y para $n \ge 1$, $a_n = a_{\lfloor n/2 \rfloor} + a_{\lfloor n/3 \rfloor} + a_{\lfloor n/6 \rfloor}$. Encontrar $\lim_{n\to\infty} a_n/n$.

Este es un problema mucho más difícil, ya que tenemos que determinar no sólo la tasa de crecimiento ("linear"), pero también la constante factor de proporcionalidad.

Soluciones se han dado en el enero de 1985 problema (Vol. 58, Nº 1), en la sección de Problemas (pp 51-52), bajo el título de Un Muy Lentamente la Convergencia de la Secuencia, por (juntos) P. Erdős, R. Hildebrand, A. Odlyzko, P. Pudaite, y B. Reznick.

Tenga en cuenta que la misma página también dice:

También resuelto por Noam Elkies (estudiante), que usa de la serie de Dirichlet y el teorema de los residuos; y parcialmente (bajo el supuesto de que el límite existe) de Don Calderero, que dio la fórmula explícita $$ a_n = 1 + 2 \sum \frac{(r+s+t)!}{r!s!t!} $$ donde la suma se extiende sobre todos los triples $(r, s, t)$ de los números enteros no negativos tales que $2^r3^s6^t \le n$.

De todos modos, en su solución, los autores EHOPR también decir

Estamos escribiendo un artículo inspirado por este problema y sus generalizaciones.

y dar resultados generales, tales como los siguientes (he simplificado el numerador un poco):

Supongamos $a_0 = 1$, e $a_n = \sum_{i=1}^{s} \lambda_i a_{\lfloor n/m_i \rfloor}$$n \ge 1$. Supongamos también que no todas las $m_i$s (entero) que los poderes de algunos entero. Entonces $$ \lim_{n\to\infty} \frac{a_n}{n^{\tau}} = \frac{ \sum_{i=1}^{s} \lambda_i - 1}{\tau \sum_{i=1}^{s} p_i \log m_i} $$ donde $\tau$ es el único número real de satisfacciones $\sum_{i=1}^{s} \lambda_i / m_i^\tau = 1$, e $p_i = \lambda_i / m_i^\tau$ (asumiendo $\tau \neq 0$).

Así que en este caso, tenemos $$ \lim_{n\to\infty} \frac{a_n}{n} = \frac{3 - 1}{\frac12\log 2 + \frac13\log 3 + \frac16\log 6} = \frac{12}{\log 432} \approx 1.977 $$ La secuencia es OEIS A007731.

Para el problema anterior (1158), tenemos, con $\tau \approx 0.78788$ la solución a $(1/2)^x + (1/3)^x = 1$, $p_1 = \frac1{2^\tau}$, y $p_2 = \frac1{3^\tau} = 1 - p_1$, la proporción $\frac{1}{\tau 2^{-\tau}\log 2 + 3^{-\tau}\log 3} \approx 1.469$, lo $$a_n \sim 1.469 n^{0.78788}.$$

El papel en el que escribió fue publicado como:

P. Erdős, R. Hildebrand, A. Odlyzko, P. Pudaite, y B. Reznick,
El comportamiento asintótico de una familia de secuencias,
Pacífico Diario de las Matemáticas, Vol. 126, Nº 2 (1987), pp 227-241: Enlace 1 (PDF), Enlace 2

Answer 3

Este es un lugar absolutamente increíble problema cuya solución puede ser conseguido a través de Tauberian y teoremas de convolución. La parte difícil es mostrar la existencia del límite. Ver a este viejo AoPS post aquí para una discusión de este problema y de usuario "fedja" la solución que se puede encontrar en dos de sus puestos de trabajo, uno para la existencia, y uno para una ruta sugerida de cálculo:

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=70&t=28832&hilit=Tauberian

PS: Esta es la primera vez que he oído que este problema fue diseñado por Erdős (aunque de alguna manera no me sorprende). Si alguien tiene una referencia, que sería genial!