# How can I find the closed form of this recursive relationship: $a_{n}=(a_{n-1})^2+a_{n-1},a_{0}=1$

This comes up in OEIS as A007018. However the recursive form is useless to me, I need the closed form. I've been trying for several hours and I simply come up empty. Any advice?

Thanks.

• What exactly do you mean with the explicit form? The recursive form looks pretty explicit. Do you mean the closed form to evaluate $a_n$ for any $n$? – Newb Apr 1 '15 at 4:58
• The fact that the only closed form given in the OEIS entry is $a(n) = \left\lfloor c^{2^n}\right\rfloor$, where $c=1.597910218031873178338070118157\ldots$, suggests that you won’t do any better than this. – Brian M. Scott Apr 1 '15 at 4:59
• @BrianM.Scott Note that $c$ was probably computed by evaluating the sequence recursively up to some $n$. (Similar to the "closed form" for the Fibonacci sequence that requires finding the Golden Ratio to arbitrary precision...) – Newb Apr 1 '15 at 5:00
• @Newb: Yes, after showing that there is a closed expression of that form. – Brian M. Scott Apr 1 '15 at 5:01
• @Newb, Yes, my bad, thank you! I'm looking for something like Brian M. Scott posted, but I don't know how I would ever arrive at that solution on my own without a computer. – TechnoSam Apr 1 '15 at 12:08

There are just two (diagonalized monic) versions that give nice closed forms: $$x_n = x_{n-1}^2$$ gives $$x_n = x_0^{\left( 2^n \right) }.$$ The other, used by Lucas, is $$x_n = x_{n-1}^2 - 2; \; \; \; \; x_0 > 2.$$ This time we find $A > 1,$ with $AB = 1$ and $A + B = x_0.$ Then $$x_n = A^{\left( 2^n \right) } + B^{\left( 2^n \right) }.$$

That is all the nice ones. For the others, taking logarithm of both sides shows that there is a limit which is the number $c$ from OEIS, but we can only estimate $c$ by calculating many terms of the sequence itself.

With your sequence, taking $$a_n = b_n - \frac{1}{2}$$ gives $$b_n = b_{n-1}^2 + \frac{1}{4}$$ so you are out of luck as far as closed form answers. With this much, not difficult to prove that $$\frac{\log b_n}{2^n}$$ has a limit as $n \rightarrow \infty,$ call it $w,$ then the number $c = e^w.$