$\{a_n\}_{n\in \mathbb{N}}$ is a sequence satisfying $a_0=1$ and $$a_n=\sum_{j=0}^{\lfloor n/2\rfloor}\frac{a_j}{(n-2j)!}\qquad n\ge 1$$ Show that $$\liminf_{n\to \infty}\frac{\ln a_n}{\ln n}\le \frac{1}{\ln 2}-1\le \limsup_{n\to \infty} \frac{\ln a_n}{\ln n}$$
This problem was given to me by a friend. I have no idea on it so far. And I don't know if this is true or not. Can someone give some idea on how to do it? Thanks a lot.
Hint: If we put: $$ f(z) = \sum_{m\geq 0}a_m z^{2m},\qquad g(z) = \sum_{m\geq 0}\frac{z^m}{m!}=e^z,\tag{1}$$ the recurrence gives: $$ f(z)e^z = \sum_{m\geq 0}a_m z^m = f(\sqrt{z}) \tag{2}$$ hence: $$ f(z) = \exp\left(z^2+z^4+z^8+z^{16}+\ldots\right).\tag{3}$$
Now the problem boils down to estimating the coefficients of the Taylor series of $g(z)=\exp\left(z+z^2+z^4+z^8+z^{16}+\ldots\right)$ in a neighbourhood of zero. Since $g(z)=e^z\cdot e^{z^2}\cdot\ldots$ is an infinite product of entire functions with non-negative Taylor coefficients, the Taylor coefficients of $g(z)$ are lower-bounded by the Taylor coefficients of: $$ h(z) = (1+z)(1+z^2)(1+z^4)\cdot\ldots = \frac{1}{1-z} = 1+z+z^2+\ldots,$$ i.e. by $1$. You just have to push further this idea to provide improved upper and lower bounds.
Also notice that this problem is heavily related with the problem of counting the elements of $S_n$ (the permutation group over $n$ objects) with order $2$ and similar problems.