4
$\begingroup$

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 ?

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

This is an answer to part C.

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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