Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 5 down vote accepted

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.

share|cite|improve this answer
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
I've added the proof as a postscript in my original post. – Dean Hickerson Aug 30 '13 at 20:52
Thank you very much. – mathlove Aug 31 '13 at 2:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.