Asymptotics of a recurrence relation

Question

The sequence $(a_n)_{n \ge 0}$ satisfies, $a_0 = a_1 = 1$ and the recursion relation:

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

where, $[x]$ is the nearest integer to $x$ not exceeding it.

Alternatively define $a_n$'s as:

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

We need to show that: $$\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}$$

How do we investigate the asymptotics of this type of recursion relation?

Answer 1

It is not hard prove the bounds you want by purely real variable techniques. First note that the $a_n$ are non-negative for all $n$. For a general non-negative sequence $a_n$, and real numbers $N>0$, put $$ F(N) = \sum_{n=0}^{\infty} a_n e^{-n/N}, $$ and assume that there are constants $\alpha >1$, and positive constants $c_1$ and $c_2$ such that for all large $N$ we have $$ c_1 N^{\alpha }\le F(N) \le c_2 N^{\alpha}. $$ Then I claim that $$ \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}, $$ for some positive constants $A_1$ and $A_2$.

To prove these, first note that $$ 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, $$ and the bound on the minimum follows. Next, let $K$ be a fixed suitably large real number, and note that \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*} Now by choosing $K$ large, we can guarantee that $e^{-K/2}F(2N) \le F(N)/2$, and then it follows for some constant $B>0$ $$ BN^{\alpha} \le KN \max_{n\le KN} a_n, $$ and this establishes our lower bound for the max.

Returning to the problem at hand, here we have $$ F(N) = \exp\Big( \sum_{n=0}^{\infty} e^{-2^n/N}\Big), $$ and it is straightforward that $$ \sum_{n=0}^{\infty} e^{-2^n/N} = \frac{\log N}{\log 2} + O(1). $$ So we may use our work above with $\alpha=1/\log 2$ and some $c_1$ and $c_2$, and obtain the desired bounds on the lim sup and lim inf (in slightly more precise form). In this case one should be able to do more by working harder, but it'll probably be a bit tricky.

Answer 2

Let $A(x)$ denote the formal generating function of $\{ a_n\}$. The recurrence relation can be written as $A(x)=e^x A(x^2)$. Applying this repeatedly, we find $A(x) = e^x e^{x^2} \cdots = e^{f(x)}$, where $f(x) = \sum_{i \ge 0} x^{2^i}$.

Asymptotics of $[x^n] e^{P(x)}$ where $P$ is a polynomial with positive coefficients are "easy", for example they follow by Hayman's method, see this paper of Odlyzko and Richmond, and this paper of Wilf for a worked out example.

As Jeffery remarked, since $a_n \ge [x^n] e^{P_m(x)}$ where $P_m(x) = \sum_{i \le m} x^{2^i}$ for any $m$, this method provides you lower bounds.

As for upper bounds - since $[x^n] e^{f(x)} \le [x^n] e^{\frac{x}{1-x}}$ and $e^{\frac{x}{1-x}}$ is Hayman-admissible (see page 90 here), Hayman method applies again and gives an upper bound of the form $a_n = O(n^{3/4})$.

I won't be surprised if $e^{f(x)}$ is already Hayman-admissible, but working out the asymptotics via this method requires one to approximate the solution to the equation $\sum_{i \ge 0} t^{2^i} 2^i=n$ ($0<t<1$) for each $n$, which is not easy to do uniformly for all $n$.

Answer 3

It should not be hard to prove upper and lower bounds of the form $n^c$ for some constant $c< 1$ for $a_n$. (Probably different $c$ for upper and lower bound.)

The basic idea is that, for all practical purposes, the recurrence relations are $a_{2n} = a_n + a_{n-1}/2 + a_{n-2}/24$ and $a_{2n+1} = a_n + a_{n-1}/6 + a_{n-2}/120$ (where I've omitted lower order terms). This means that (roughly speaking) $a_n$ is going to be greater than $a_{n/2}(1+ 1/6)$, so by iterating this we get that $a_n > (7/6)^{\log_2 n}$, which gives $a_n > n^c$. For the upper bound, bound $a_{n-k}$ by $a_n$ and use the fact that the sum of inverse factorials is bounded by $e$.

Local minima should be near $n = 2^k - 2$, and local maxima near $n = \lfloor 2^k/3 \rfloor$.

Answer 4

I get a slightly different answer every time I look at it, so I hope the following is ok. I won't dot every last "i" in the error analysis.

Let $F(t)=\sum_{i=0}^\infty a_i(t)$, where $a_i(t)=t^{2^i}2^i$. We want to find the solution to $F(t)=n$ as $n\to\infty$. As Ofir says, that is needed in Hayman's method, or in a hand-crafted application of the saddle-point method if Hayman's conditions are not precisely met.

For $0\lt t\lt 1$, the maximum term occurs near $i=i_0=\log_2\log_2(1/t)$, and we find that $a_{i_0+x}(t) = 2^{-2^x+x}/\log_2(1/t)$. The function $2^{-2^x+x}$ decays very rapidly in both directions, and $\int_{-\infty}^{\infty} 2^{-2^x+x}\,dx=1/(\ln 2)^2$. So let $Q(t) = \sum 2^{-2^x+x}$ where the sum is over all $x$ (positive and negative) such that $i_0+x$ is an integer. This clearly depends only on the fractional part of $i_0$, so it is periodic with period 1 as a function of $i_0$. Experimentally it oscillates between $0.9999901/(\ln 2)^2$ and $1.0000098/(\ln 2)^2$. The error in including negative values of $i_0+x$ is very tiny for large $n$; I will be lazy and ignore it.

Now we have that $F(t)\approx Q(t)/\log_2(1/t)$, which equals $n$ when $t=2^{-Q(t)/n}$. This is a strongly-contracting mapping. Write $Q(t)=R(n)$; then $R(n)$ oscillates between $0.9999901/(\ln 2)^2$ and $1.0000098/(\ln 2)^2$ depending on the fractional part of $\log_2 n$.

Answer 5

Here is a sketch of the standard approach to a problem of this type; its expansion will probably of Lucia's solution.

If in Jeff Shallit's response you introduce the related monotone increasing sequence $A_n=\sum_{k=0}^na_n$ then the difference relations can be used to show that $$C^kA_{\max\{0,[n/2^k]-5\}}\le A_n\le C^kA_{[n/2^k]+1}$$ for any $k$ with the choice $C=1+1/2+1/24+1+1/6+1/120=163/60$. An inductive argument then shows that $C_1n^\xi\le A_n\le C_2n^\xi$ with $\xi=1/\log(2)$ and some positive $C_1,C_2$ and the final passage from $A_n$ to $a_n$ can be performed with the help of the Stolz–Cesàro theorem.