How do I find the general solution of this recurrence relation?
$$a_n=(a_{n-1})^2+(a_{n-2})^2,a_1=1, a_2=2$$
I didn't find any general solution for this recurrence relation.
How do you find the general solution of the recurrence relation: $a_n=(a_{n-1})^2+(a_{n-2})^2,a_1=1, a_2=2$
recurrence-relations
Best Answer
Hint: The following is rather a hint than an answer. Given is \begin{align*} \color{blue}{a_n}&\color{blue}{=a_{n-1}^2+a_{n-2}^2\qquad\qquad n\geq 3}\tag{1}\\ \color{blue}{a_1}&\color{blue}{=1, a_2=2} \end{align*}
The recurrence relation (1) belongs to a group of doubly exponential sequences which are analysed in the 1973 paper Some doubly exponential sequences by A. V. Aho and N. J. A. Sloane.
Some of the sequences analysed in the paper are \begin{align*} x_{n+1}&=x_n^2+1 &n\geq 0;\qquad x_0=1\qquad\quad\ \\ y_{n+1}&=y_n^2-y_n+1&n\geq 1;\qquad y_1=2\qquad\quad\ \\ y_{n+1}&=y_n^2-y_{n-1}^2& n\geq 1;\qquad y_0=1, y_1=2 \end{align*}
It is shown, that recurrence relations of the form \begin{align*} x_{n+1}&=x_n^2+\color{blue}{g_n}\qquad n\geq 0\tag{2} \end{align*} with boundary conditions, and such that the following three conditions \begin{align*} x_n&>0\tag{i}\\ \left|g_n\right|&<\frac{1}{4}x_n\qquad\quad n\geq n_0\tag{ii}\\ \left|\alpha_n\right|&\geq \left|\alpha_{n+1}\right|\qquad n\geq n_0\tag{iii} \end{align*} are satisfied all have a specific type of solution. For the definition of $\alpha_n$, see below.
Here we write (2) as \begin{align*} x_{n+1}&=x_n^2+g_n\\ &=x_n^2\left(1+\frac{g_n}{x_n^2}\right) \end{align*} take logarithms and obtain after setting \begin{align*} y_n=\ln \left(x_n\right),\qquad \alpha_n=\ln\left(1+\frac{g_n}{x_n^2}\right) \end{align*} the recurrence relation \begin{align*} \color{blue}{y_{n+1}=2y_n+\alpha_n\quad n\geq 0}\tag{3} \end{align*}
Solving (3) leads to a solution of (2) which is of the form \begin{align*} \color{blue}{x_n=\left\lfloor K^{2^n}\right\rfloor\qquad n\geq 0}\tag{4} \end{align*} with $\color{blue}{K}$ a constant which needs to be determined.
Note: The first time I read about this type of recurrence relation was many years ago in section 2.2.3 Doubly Exponential Sequences in Mathematics for the Analysis of Algorithms by D. E. Knuth and D. H. Greene. There I found the reference to the 1973 paper.