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?"