Asymptotics of a recurrence relation

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.

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$.

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$.