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?
Best Answer
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.