# Does there exist a constant $C$ such that $2^n\le a_n \le C^n$ for any $n$?

I'm interested in making original sequences and in finding a special property. I've been thinking a sequence $\{a_n\}$.

$\{a_n\}\ (n=0,1,2,\cdots)$ is defined as the following:

$$a_0=1, a_{n+1}=\sum_{j=0}^{n}a_j+\sum_{j=0}^na_ja_{n-j}.$$

By using computer, I expect the following would be proven true:

My expectation: There exists a constant $C\gt2$ such that $2^n\le a_n \le C^n$ for any $n$.

I can't prove this, but it seems true, indeed. Here is my question.

Question: Is this property is true? In other words, can this property be a theorem? If it can be a theorem, please show me how to prove it. If not, again please show me how to prove it.

-
My computations show the following. If we compute $d_n = a_{n+1}/a_n$, we get (approximating to two decimals) $$\begin{bmatrix} d_5 & = & 4.631 \\ d_{10} & = & 5.316 \\ d_{50} & = & 5.975 \\ d_{100} & = & 6.064 \\ d_{500} & = & 6.137 \\ d_{1000} & = & 6.147 \\ d_{2000} & = & 6.151 \\ d_{4000} & = & 6.154 \\ d_{8000} & = & 6.155 \\ \end{bmatrix}$$ So I don't understand how you believe it will converge or stay bounded. Yes the values are small, but $\log(\log(n))$ goes to infinity too, and yet it grows very slow. – Patrick Da Silva Aug 29 '13 at 9:25
The sequence $d_n$ is apparently increasing, but that is not very hard to believe. (The first hundred values show this.) What's harder to believe is if the sequence is bounded or not, i.e. if your value of $C$ would exist. Note that $2^n \le a_n \le C^n$ for $C > 2$ implies that $2 \cdot (2/C)^n \le d_n \le C \cdot (C/2)^n$. So $d_n$ does not need to be bounded (it would be a stronger statement), but still. The constraint $a_n \le C^n$ looks quite weak and shouldn't be too hard to prove (in the sense that you seem to have a "lot of space" between $a_n$ and $C^n$). – Patrick Da Silva Aug 29 '13 at 9:35
A generating function is known : $$\frac{2\,x-1+\sqrt{1-8\,x+12\,x^2-4\,x^3}}{2\,x\,(x-1)}$$ see OEIS entry A215973 with the $1000$ first terms. – Raymond Manzoni Aug 29 '13 at 9:36

Let $$f(z) = \sum_{n\ge 0}^{}a_n z^n.$$ It's straightforward to verify (P.S.: See end of this post.) that $$z(1-z)f(z)^2+(2z-1)f(z)+1-z=0,$$ and therefore $$f(z) = \frac{2z-1+\sqrt{1-8z+12z^2-4z^3}}{2z(z-1)}.$$ In this form, there appears to be a singularity at $z=0$, but by rationalizing the numerator we see that there really isn't one: $$f(z)=\frac{2(1-z)}{1-2z+\sqrt{1-8z+12z^2-4z^3}}.$$ So $f$ is analytic for $|z|<|r|$, where $r$ is the root of $1-8z+12z^2-4z^3=0$ with smallest absolute value. Numerically, we find that $r=0.16243...$ . Therefore the series defining $f(z)$ converges whenever $|z|\le 0.16243$, which implies that $$\lim_{n\rightarrow\infty}a_n 0.16243^n=0.$$ So, at least for sufficiently large values of $n$, $$a_n 0.16243^n\le1$$ and $$a_n\le\frac{1}{0.16243^n}<6.15650^n.$$ Numerically, this appears to be true for all $n$, but I haven't proved that. In any case, $C$ does exist; in fact we can take $C$ to be the maximum of $6.15650$ and the finitely many values (if any) of $a_n^{1/n}$ for which $a_n 0.16243^n>1.$
P.S.: Proof of functional equation for $f(z)$:
$$f(z)^2=\sum_{n\ge0}\sum_{j=0}^na_j a_{n-j} z^n =\sum_{n\ge0}\Big(a_{n+1}-\sum_{j=0}^na_j\Big)z^n$$ so \begin{align} (1-z)f(z)^2&=\sum_{n\ge0}\Big(a_{n+1}-\sum_{j=0}^na_j\Big)z^n - \sum_{n\ge1}\Big(a_n-\sum_{j=0}^{n-1}a_j\Big)z^n\\ &=a_1-a_0+\sum_{n\ge1}(a_{n+1}-2a_n)z^n\\ &=1+\sum_{n\ge2}a_nz^{n-1}-2\sum_{n\ge1}a_nz^n\\ &=1+z^{-1}(f(z)-a_0-a_1z)-2(f(z)-a_0)\\ &=1-z^{-1}+(z^{-1}-2)f(z). \end{align} Multiplying by $z$ and rearranging gives the stated equation.
Thank you. I have a question. Could you tell me how to get the equation about $f(z)$? – mathlove Aug 30 '13 at 14:36