# Closed form solution for Quadratic Recurrence Relations

I was trying to solve the following recurrence relation using method of generating function but I couldn't.

$$a_n=a_{n-1}^2-a_{n-1} +1$$ for $a_0=2$ and $n>0$.

After googling I found it is the recurrence for Sylvester's sequence (A000058 OEIS).

In wikipedia the $n^{th}$ term of sequence is given by $$a_n=\lfloor E^{2^{n+1}}+\frac{1}{2}\rfloor$$ where $E=1.264084735305302$ approximately.

So my questions are

a) Whether the above has a perfect closed form solution or not ?

b) If yes, is $E$ rational or irrational ?

c) Is there a way to tell if the given recurrence relation having quadratic form($a_n=pa_{n-1}^2+qa_{n-1} +r$) has closed form solution just by looking at the coefficients ?

• Those quadratic terms are quite tricky; among other things, such recurrences are unlikely to exist in a closed form – Alex Dec 31 '16 at 12:29
• Here hal.archives-ouvertes.fr/hal-00651136v1 you can find a proof for the irrationality of $E$. – Fabio Lucchini Jan 1 '17 at 8:33
• Note also that every quadratic recurrence is linearly conjugate to a recurrence of the form $x_{n+1}=x_n^2+c$. – Fabio Lucchini Jan 1 '17 at 8:42

Currently, we know how to iterate two types of quadratic sequences. They are for quadratics in one of these two forms: $$q_1(x)=ax^2+bx+\frac{b^2-2b}{4a}$$ $$q_2(x)=ax^2+bx+\frac{b^2-2b-8}{4a}$$ See the wikipedia page on iterated functions or this blog post for a more in-depth explanation of how to iterate these two types.