# Inequality with $\limsup$ and $\liminf$ of a sequence

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

• This is a very nice problem. – Jack D'Aurizio Sep 10 '15 at 21:30

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.
• Thanks a lot for your reply. I have tried to go on the path of your hint, and I have found that $\exp\left(\sum_{k\ge 0}x^{2^k}\right)=\sum_{n\ge 0}a_n x^n$ but I don't get any bounds for $a_n$ from this. Can you help me out? Thanks @Jack D'Aurizio – shadow10 Sep 11 '15 at 13:41