Quadratic Recurrence Relations

Question

Does anyone know combinatoric methods to get solutions to quadratic recurrences? An example of what I'm looking for:

$$F_{n+1} = 3F_n^2-2F_n$$

under the initial condition $F_0 =2, F_1 = 8$.

Much more tricky than a linear recurrence.

Answer 1

A linear substitution can get rid of the linear term on the right, leaving only the quadratic term and a constant term. Here, if we let $G_n = 3F_n - 1$, then the recurrence relation turns into $$ \frac{G_{n+1}+1}{3} = 3 \left(\frac{G_n + 1}{3}\right)^2 - 2 \left(\frac{G_n+1}{3}\right) $$ which simplifies to $G_{n+1} = G_n^2 - 2$. We might hope that this is easier to deal with...

---

...but I don't actually know how to solve a general recurrence of this type. In this case, we are lucky that the constant is a $2$, because a general solution to this recurrence relation is $G_n = \alpha^{2^n} + \alpha^{-2^n}$; this recurrence comes up in applications such as the Lucas-Lehmer test for primality. We can check that $$ \left(\alpha^{2^n} + \alpha^{-2^n}\right)^2 - 2 = (\alpha^{2^{n+1}} + 2 + \alpha^{-2^{n+1}}) - 2 = \alpha^{2^{n+1}} + \alpha^{-2^{n+1}}. $$ How do we choose $\alpha$? To satisfy the initial condition $\alpha + \frac1\alpha = G_0$.

Here, we have $G_0 = 3F_0 - 1 = 5$. This means $\alpha + \frac1\alpha = 5$, so $\alpha = \frac{5 \pm \sqrt{21}}{2}$. We can choose either root, because the other root is the reciprocal, getting $$G_n = \left(\frac{5+\sqrt{21}}{2}\right)^{2^n} + \left(\frac{5-\sqrt{21}}{2}\right)^{2^n}$$ with $F_n = \frac{G_n + 1}{3}$. The first few values of $G_n$ we get from this formula are $5, 23, 527, 277727, \dots$, giving us $2, 8, 176, 92576, \dots$ for $F_n$.

Answer 2

This alternative solution is too long for a comment, so I'm posting it as an answer.

In my (admittedly, limited) experience, the only known closed form solution to a quadratic recurrence is for $a_n=a_{n-1}^2-2$. And therefore, given a quadratic recurrence to solve, the first thing to do is to try to get it into that form. As was masterfully done by Misha Lavrov. The solution to this recurrence is based on the identity $\cos 2\alpha=2\cos^2\alpha-1$, or similarly for $\cosh2\alpha$.

However, I came across another solution that you might find interesting. This method linearizes the recurrence as follows:

$$ a_n=a_{n-1}^2-2\\ a_n=b_n+\frac{1}{b_n}\\ b_n+\frac{1}{b_n}=\bigg(b_{n-1}+\frac{1}{b_{n-1}} \bigg)^2-2=b_{n-1}^2+\frac{1}{b_{n-1}^2}\\ b_n-b_{n-1}^2=\frac{1}{b_{n-1}^2}-\frac{1}{b_n}=\frac{b_n-b_{n-1}^2}{b_nb_{n-1}^2}\\ b_nb_{n-1}^2=1\\ \ln(b_nb_{n-1}^2)=0\\ g_n=\ln(b_n)\\ g_n=-2g_{n-1}\\ g_n=(-2)^ng_0\\ b_n=b_0e^{(-2)^n}\\ a_n=b_n+\frac{1}{b_n}\\ a_0=b_0+\frac{1}{b_0}\\ b_0=\frac{a_0\pm\sqrt{a_0^2-4}}{2} $$

And so on. The results are the same as the $\cos,\cosh$ solutions, albeit in exponential form.