What is the solution to $a_n =a_{n-1}^2+a_{n-2}^2, a_0, a_1>1 $? I saw this on Quora
and have made
very little progress.
What is the solution
(exact or asymptotic) to
$a_n
=a_{n-1}^2+a_{n-2}^2,
a_0, a_1>1
$?
I would be satisfied
with a good asymptotic analysis.
Heck,
I would be happy with an
asymptotic form
of the log of the solution.
A lower bound is easy.
Assuming $a_1 > a_0 > 1$,
$a_n>a_{n-1}^2
\gt a_{n-2}^4
... > a_{n-k}^{2^k}
...
\gt a_1^{2^{n-1}}
\gt a_0^{2^{n}}
$.
A reasonable upper bound seems harder.
$a_{n-1} > a_{n-2}^2
$
so
$a_n
=a_{n-1}^2+a_{n-2}^2
\lt a_{n-1}^2+a_{n-1}
$
so
$a_n+\frac14
\lt a_{n-1}^2+a_{n-1}+\frac14
=(a_{n-1}+\frac12)^2
$
or
$a_n+\frac12
\lt (a_{n-1}+\frac12)^2+\frac14
$.
If
$b_n
= a_n+\frac12
$,
$\begin{array}\\
b_n
&\lt b_{n-1}^2+\frac14\\
&\lt (b_{n-2}^2+\frac14)^2+\frac14\\
&= b_{n-2}^4+\frac12 b_{n-2}^2+\frac1{16}+\frac14\\
\end{array}
$
Not sure where to go
from this.
Another possibility
is to notice that
once $a_n$ gets large,
for any $c > 0$
there is an
$n(c)$ such that
for $n \ge n(c)$,
$a_n > 1/c$ so
$\begin{array}\\
a_n
&=a_{n-1}^2+a_{n-2}^2\\
&\lt a_{n-1}^2+a_{n-1}\\
&= a_{n-1}^2(1+1/a_{n-1})\\
&\lt (1+c)a_{n-1}^2\\
&\lt (1+c)((1+c)a_{n-2}^2)^2\\
&=(1+c)^3a_{n-2}^4\\
&<(1+c)^3((1+c)a_{n-3}^2)^4\\
&=(1+c)^7a_{n-3}^8\\
& ...\\
&<(1+c)^{2^k-1}a_{n-k}^{2^k}\\
& ... \text{up to } n-k = n(c), k=n-n(c)\\
&<(1+c)^{2^{n-n(c)}-1}a_{n(c)}^{2^{n-n(c)}}\\
\end{array}
$
Don't see how to do better.
 A: For any $n \ge 1$, we have:
\begin{align*}
a_{n+1} &= a_n^2+a_{n-1}^2
\\
a_{n+1} &= a_n^2\left(1+\dfrac{a_{n-1}^2}{a_n^2}\right)
\\
\log a_{n+1} &= 2\log a_n + \log\left(1+\dfrac{a_{n-1}^2}{a_n^2}\right)
\\
\dfrac{1}{2^{n+1}}\log a_{n+1} &= \dfrac{1}{2^n}\log a_n + \dfrac{1}{2^n}\log\left(1+\dfrac{a_{n-1}^2}{a_n^2}\right)
\end{align*}
This is enough to show that $\dfrac{1}{2^n}\log a_n$ is non-decreasing, and thus, either converges to some limit or is unbounded.
Summing the previous equation from $n = 2$ to $n = N-1$ yields, $$\dfrac{1}{2^N}\log a_N = \dfrac{1}{4}\log a_2 + \sum_{n = 2}^{N-1}\dfrac{1}{2^n}\log\left(1+\dfrac{a_{n-1}^2}{a_n^2}\right).$$
It is easy to check that for all $n \ge 2$, we have $a_{n-1} > 1$, and thus, $a_n = a_{n-1}^2+a_{n-2}^2 > a_{n-1}^2 > a_{n-1}$. Hence, we can bound $$0 \le \sum_{n = 2}^{N-1}\dfrac{1}{2^n}\log\left(1+\dfrac{a_{n-1}^2}{a_n^2}\right) \le \sum_{n = 2}^{N-1}\dfrac{1}{2^n}\log 2 = \dfrac{1}{2}\log 2,$$ and thus, $$\dfrac{1}{4}\log a_2 \le \dfrac{1}{2^N}\log a_N \le \dfrac{1}{4}\log a_2 + \dfrac{1}{2}\log 2.$$
Since $\dfrac{1}{2^n}\log a_n$ is bounded (and previously shown to be non-decreasing), $\dfrac{1}{2^n}\log a_n$ converges to some number between $\dfrac{1}{4}\log a_2$ and $\dfrac{1}{4}\log a_2 + \dfrac{1}{2}\log 2$.
We can probably get tighter bounds if we are more careful about bounding the sum.
