# Asymptotics of a recurrence relation

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?

• Do you just want the bounds for the lim sup and lim inf (which is fairly easy), or are you looking for precise asymptotics? – Lucia Nov 1 '15 at 21:56
• @Lucia Showing the bounds will help a lot! :) Thanks! – r9m Nov 1 '15 at 21:57
• It is a problem in AMM from Georges Stoica. AMM-11849 to be exact, but worry not it's not a recent problem. :-) – user88969 Mar 15 '16 at 6:41

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.

• Wow! That's incredible! Thanks!! :) Could you explain the last identity a bit .. $\sum_{n=0}^{\infty} e^{-2^n/N} = \frac{\log N}{\log 2} + O(1)$? – r9m Nov 1 '15 at 22:55
• To get the lower bound, note that it is $\ge \sum_{n\le \log_2 N} (1-2^n/N)$ which is $\ge \log_2 N- C$ for some constant. For the upper bound, use $e^{-2^n/N} \le \min (1, N/2^n)$ and so the sum is $\le \log_2 N + \sum_{2^n>N} N/2^n \le \log_2 N+ C$ for some constant $C$. – Lucia Nov 1 '15 at 23:01
• I am unable to get the passage from $\max_{n\le N} a_n \ge A_2 N^{\alpha-1}$ to $\limsup\limits_{n \to \infty} \frac{\log a_n}{\log n} \ge \alpha - 1$ – r9m Nov 2 '15 at 6:17
• Since $\alpha >1$, as $N$ gets larger and larger the max of $a_n$ over $n\le N$ is attained at larger and larger values; and also $n^{\alpha-1}$ is at most $N^{\alpha-1}$. – Lucia Nov 2 '15 at 7:49
• Not sure what you're confused by. The argument shows that for all large $N$, there exists $n\le N$ with $a_n \ge A_2 N^{\alpha-1} (\ge A_2 n^{\alpha-1})$. Note that for any given $n$, the inequality $a_n \ge A_2 N^{\alpha-1}$ will fail once $N$ is large enough. So there are arbitrarily large $n$ with $a_n \ge A_2 n^{\alpha-1}$, and hence the lim sup is at least as large as $\alpha-1$. Does that help? – Lucia Nov 2 '15 at 14:18

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

• Indeed I tried Hayman's method but couldn't have an exact asymptotics for $a_n$, (+1) Thanks! :) – r9m Jul 31 '15 at 12:39
• The solution of $\sum t^{2^i} 2^i=n$ is $t=2^{-R(n)/n}$, where $R(n)$ is a quasi-periodic function that oscillates around $1/\ln(2)^2$ without converging. If I didn't get it wrong. There will be a quasi-periodic component to the asymptotics. – Brendan McKay Jul 31 '15 at 13:11
• @BrendanMcKay could you explain how we get to the quasi-periodic component, it'd be nice if you elaborate over an answer! Thanks!! :) – r9m Aug 11 '15 at 10:19

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

• $c$ should be close to $\frac{1}{\log 2} - 1$, but I was looking for stronger asymptotics. Thanks! (+1) :) – r9m Jul 31 '15 at 12:40

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

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.