Why does this method for solving recurrence relations work in some cases and not in others?

Question

I have been reading on recurrence relations and I have seen that some of them are really easy to solve, for example: $$a_{n+1}=a_n^2$$ Starting from $n=0$ and substituting yields a pattern that is simple enough to take advantage of, after a proof by induction we get $a_n=a_0^{2^n}$. I have some problems with this method because, even though it provides an answer, this answer springs from pattern recognition and nothing else, we know nothing more about the relation or whether other solutions exist, but at least we know one solution.
The problem comes when, three strokes later, we get this: $$a_{n+1}=a_n^2+1$$ A single one makes the problem much harder. However, I still tried to solve it and after fruitlessly attacking it with matrices, integrals, derivatives, polynomial expansions and more pattern recognition, I tried a new method:
We set $a_n=f(n)$ such that $f(n)^2+1=f(n+1)$. To find an expression for $f(n)$ we note that $a_{n+1}-a_n^2=1$.
Assume we have a solution $(a_1,a_0)$, then $$(\sqrt{a_1}+a_0)^{g(n)}(\sqrt{a_1}-a_0)^{g(n)}=1^{g(n)}=(\sqrt{a_{n+1}}+a_n)(\sqrt{a_{n+1}}-a_n)$$

Equating coefficients and solving the system of two equations in two unknowns yields $$a_{n+1}=\frac 14 ((\sqrt{a_{1}}+a_0)^N+(\sqrt{a_{1}}-a_0)^N)^2$$ $$a_{n}=\frac 12 ((\sqrt{a_{1}}+a_0)^N-(\sqrt{a_{1}}-a_0)^N)$$ Where $N=g(n)$. We can check that these expressions satisfy the original equation but I do not know how to proceed from here. I noticed, however, that if we define $h(N)$ to be equal to the square root of the expression for $a_{n+1}$ we have $h(N)^2=\frac {h(2N)+1}{2}$. If we use the ansatz $g(n)=2^n$ then $2h(n)^2-1=h(n+1)$ which is extremely close to the function I was searching for. Furthermore, we can set $$f(n)=A(\sqrt{a_{1}}+a_0)^{2^n}+A(\sqrt{a_{1}}-a_0)^{2^n}$$ Which gives $f(n)^2-2A^2=Af(n+1)$. In some way, the above approach solved an equation similar to the one I wanted to solve. My question is twofold: "Why did I end up solving a different yet similar equation?" And "Although this approach has many holes here and there (e.g. Justifying the replacement of $1/2$ with $A$, finding $g(n)$ without using an ansatz, adjusting the values of $a_1, a_0$ for different recurrence relations, etc.) is it still a promising approach?"

Answer 1

Nonlinear recurrence relations are hard. There are very few cases where you can have a closed-form solution. In particular, quadratic recurrences have closed-form solutions only in a few cases.

This deserves to be put in a somewhat wider context. There are, up to conjugacy by linear functions, two sequences $P_n$ of polynomials of degree $n$ forming semigroups under composition (i.e. $P_{mn}(x) = P_m(P_n(x))$): the monomials $M_n(x) = x^n$ and the Chebyshev polynomials $T_n(x) = \cos(n \arccos(x))$. See e.g. this sci.math posting from 2001 for a proof. Each of these correspond to recurrences with closed-form solutions: $a_n = P_{k^n}(x)$ satisfies $a_{n+1} = P_k(a_n)$. In particular, for $k=2$ we get $a_n = x^{2^n}$ with $a_{n+1} = a_n^2$ corresponding to the monomials and $a_n = T_{2^n}(x)$ with $a_{n+1} = T_2(a_n) = 2 a_n^2 - 1$ corresponding to the Chebyshev polynomials. Conjugating this one with multiplication by a constant gives you $a_n = c T_{2^n}(x/c)$ for $a_{n+1} = 2 a_n^2/c - c$, which is the equation you ended up solving for $c = 2A$.

Answer 2

The only other one of type $x^2 + C$ that has a closed form solution is $$ x_{n+1} = x_n^2 - 2 $$ where $x_0 > 2.$ Take real constants so $A+B = x_0$ and $AB=1,$ then $$ x_n = A^{\left( 2^n \right)} + B^{\left( 2^n \right)} $$ Worth checking yourself. Not sure what happens if $0 < x_0 < 2$

For other $x_{n+1} = x_n^2 + C$ you can still prove an approximation $x_n \approx H^{\left( 2^n \right)},$ however, I recall that you cannot get an explicit value for the constant $H,$ only estimates from calculating large $x_n.$ Meaning, of course, the you are just estimating $$ \frac{\log x_n}{2^n}$$ and calling that $\log H.$

Answer 3

According to this paper (which I haven't read), for any recurrence relation of a general form including yours, there is some constant $k$ such that for all sufficiently large $n,$ $a_n$ is the nearest integer to $k^{2^n}.$

A. V. Aho and N. J. A. Sloane, "Some Doubly Exponential Sequences", http://www.fq.math.ca/Scanned/11-4/aho-a.pdf