Asintótica de una relación de recurrencia

Question

La secuencia $(a_n)_{n \ge 0}$ se satisface, $a_0 = a_1 = 1$ y la relación de recursión:

$$a_n = \sum\limits_{k=0}^{[n/2]} \frac{a_k}{(n-2k)!}$$

donde, $[x]$ es el número entero más cercano a $x$ sin excederla.

Como alternativa, defina $a_n$ como:

$$\sum\limits_{n=1}^{\infty} a_nx^n = \exp\left(\sum\limits_{n=0}^{\infty} x^{2^n}\right)$$

Tenemos que demostrarlo: $$\liminf_{n \to \infty} \frac{\log a_n}{\log n} \le \frac{1}{\ln 2} - 1 \le \limsup_{n \to \infty} \frac{\log a_n}{\log n}$$

¿Cómo investigamos la asintótica de este tipo de relación de recursión?

Answer 1

No es difícil demostrar los límites que se desean mediante técnicas puramente de variable real. Primero hay que tener en cuenta que el $a_n$ son no negativos para todos los $n$ . Para una secuencia general no negativa $a_n$ y los números reales $N>0$ , poned $$ F(N) = \sum_{n=0}^{\infty} a_n e^{-n/N}, $$ y asumir que hay constantes $\alpha >1$ y las constantes positivas $c_1$ y $c_2$ tal que para todos los grandes $N$ tenemos $$ c_1 N^{\alpha }\le F(N) \le c_2 N^{\alpha}. $$ Entonces afirmo que $$ \min_{N\le n\le 2N} a_n \le A_1 N^{\alpha-1}, \qquad \text{and} \qquad \max_{n\le N} a_n \ge A_2 N^{\alpha-1}, $$ para algunas constantes positivas $A_1$ y $A_2$ .

Para demostrarlo, primero hay que tener en cuenta que $$ c_2 N^{\alpha} \ge F(N) \ge \sum_{N\le n\le 2N} a_n e^{-n/N} \ge e^{-2} \sum_{N\le n\le 2N} a_n \ge e^{-2} N \min_{N\le n\le 2N} a_n, $$ y a continuación se obtiene el límite del mínimo. A continuación, dejemos que $K$ sea un número real fijo convenientemente grande, y observe que \begin{align*} F(N) &\le \sum_{n\le KN} a_n + \sum_{n>KN} a_n e^{-n/N} \le \sum_{n\le KN} a_n + e^{-K/2} \sum_{n> KN} a_n e^{-n/(2N)}\\ &\le KN \max_{n\le KN} a_n + e^{-K/2} F(2N). \end{align*} Ahora, al elegir $K$ grande, podemos garantizar que $e^{-K/2}F(2N) \le F(N)/2$ y entonces se deduce para alguna constante $B>0$ $$ BN^{\alpha} \le KN \max_{n\le KN} a_n, $$ y esto establece nuestro límite inferior para el máximo.

Volviendo al problema que nos ocupa, aquí tenemos $$ F(N) = \exp\Big( \sum_{n=0}^{\infty} e^{-2^n/N}\Big), $$ y es evidente que $$ \sum_{n=0}^{\infty} e^{-2^n/N} = \frac{\log N}{\log 2} + O(1). $$ Así que podemos utilizar nuestro trabajo anterior con $\alpha=1/\log 2$ y algunos $c_1$ y $c_2$ y obtener los límites deseados para lim sup y lim inf (de forma un poco más precisa). En este caso uno debería ser capaz de hacer más trabajando más, pero probablemente será un poco complicado.

Answer 2

Dejemos que $A(x)$ denotan la función generadora formal de $\{ a_n\}$ . La relación de recurrencia puede escribirse como $A(x)=e^x A(x^2)$ . Aplicando esto repetidamente, encontramos $A(x) = e^x e^{x^2} \cdots = e^{f(x)}$ , donde $f(x) = \sum_{i \ge 0} x^{2^i}$ .

Asintótica de $[x^n] e^{P(x)}$ donde $P$ es un polinomio con coeficientes positivos son "fáciles", por ejemplo se siguen por el método de Hayman, ver este trabajo de Odlyzko y Richmond y este documento de Wilf.pdf) para ver un ejemplo elaborado.

Como dijo Jeffery, ya que $a_n \ge [x^n] e^{P_m(x)}$ donde $P_m(x) = \sum_{i \le m} x^{2^i}$ para cualquier $m$ este método le proporciona límites inferiores.

En cuanto a los límites superiores, ya que $[x^n] e^{f(x)} \le [x^n] e^{\frac{x}{1-x}}$ y $e^{\frac{x}{1-x}}$ es admisible para Hayman (véase página 90 aquí ), el método de Hayman se aplica de nuevo y da una cota superior de la forma $a_n = O(n^{3/4})$ .

No me sorprendería que $e^{f(x)}$ ya es admisible por Hayman, pero la elaboración de la asintótica mediante este método requiere aproximar la solución de la ecuación $\sum_{i \ge 0} t^{2^i} 2^i=n$ ( $0<t<1$ ) para cada $n$ lo que no es fácil de hacer de manera uniforme para todos $n$ .

Answer 3

No debería ser difícil demostrar límites superiores e inferiores de la forma $n^c$ para alguna constante $c< 1$ para $a_n$ . (Probablemente diferentes $c$ para el límite superior e inferior).

La idea básica es que, a efectos prácticos, las relaciones de recurrencia son $a_{2n} = a_n + a_{n-1}/2 + a_{n-2}/24$ y $a_{2n+1} = a_n + a_{n-1}/6 + a_{n-2}/120$ (donde he omitido los términos de orden inferior). Esto significa que (a grandes rasgos) $a_n$ va a ser mayor que $a_{n/2}(1+ 1/6)$ por lo que al iterar esto obtenemos que $a_n > (7/6)^{\log_2 n}$ , lo que da $a_n > n^c$ . Para el límite superior, el límite $a_{n-k}$ por $a_n$ y utilizar el hecho de que la suma de factoriales inversos está limitada por $e$ .

Los mínimos locales deben estar cerca de $n = 2^k - 2$ y los máximos locales cerca de $n = \lfloor 2^k/3 \rfloor$ .

Answer 4

Cada vez que lo miro obtengo una respuesta ligeramente diferente, así que espero que lo siguiente esté bien. No voy a poner los puntos sobre las íes en el análisis de errores.

Dejemos que $F(t)=\sum_{i=0}^\infty a_i(t)$ , donde $a_i(t)=t^{2^i}2^i$ . Queremos encontrar la solución a $F(t)=n$ como $n\to\infty$ . Como dice Ofir, esto es necesario en el método de Hayman, o en una aplicación artesanal del método del punto de silla si las condiciones de Hayman no se cumplen con precisión.

Para $0\lt t\lt 1$ el término máximo se produce cerca de $i=i_0=\log_2\log_2(1/t)$ y encontramos que $a_{i_0+x}(t) = 2^{-2^x+x}/\log_2(1/t)$ . La función $2^{-2^x+x}$ decae muy rápidamente en ambas direcciones, y $\int_{-\infty}^{\infty} 2^{-2^x+x}\,dx=1/(\ln 2)^2$ . Así que dejemos $Q(t) = \sum 2^{-2^x+x}$ donde la suma es sobre todos los $x$ (positivo y negativo) tal que $i_0+x$ es un número entero. Esto depende claramente sólo de la parte fraccionaria de $i_0$ por lo que es periódica con periodo 1 en función de $i_0$ . Experimentalmente oscila entre $0.9999901/(\ln 2)^2$ y $1.0000098/(\ln 2)^2$ . El error de incluir valores negativos de $i_0+x$ es muy pequeño para los grandes $n$ ; seré perezoso y lo ignoraré.

Ahora tenemos que $F(t)\approx Q(t)/\log_2(1/t)$ que es igual a $n$ cuando $t=2^{-Q(t)/n}$ . Se trata de un mapeo fuertemente contratante. Escribe $Q(t)=R(n)$ Entonces $R(n)$ oscila entre $0.9999901/(\ln 2)^2$ y $1.0000098/(\ln 2)^2$ en función de la parte fraccionaria de $\log_2 n$ .

Answer 5

He aquí un esbozo del planteamiento estándar de un problema de este tipo; su ampliación será probablemente de la solución de Lucía.

Si en la respuesta de Jeff Shallit se introduce el relacionado monótona creciente secuencia $A_n=\sum_{k=0}^na_n$ entonces se pueden utilizar las relaciones de diferencia para demostrar que $$C^kA_{\max\{0,[n/2^k]-5\}}\le A_n\le C^kA_{[n/2^k]+1}$$ para cualquier $k$ con la elección $C=1+1/2+1/24+1+1/6+1/120=163/60$ . Un argumento inductivo muestra entonces que $C_1n^\xi\le A_n\le C_2n^\xi$ con $\xi=1/\log(2)$ y algunos positivos $C_1,C_2$ y el pasaje final de $A_n$ a $a_n$ puede realizarse con la ayuda del teorema de Stolz-Cesàro.