Determine if this statement about Big O notation is true or not. $f(n) = n^2 + n^{0.5}$
$g(n) = [g(n-1)]^2 + [g(n-2)]^2$ for $n \geq 3$, where $g(1) = 1$ and $g(2) = 2$
The statement: $2^{2^{f(n)} }= Ω(g(n))$
The $\lim_{n \rightarrow \infty} \frac{2^{2^{f(n)} }}{g(n)}$ can't be computed easily since $g(n)$ has a recurrence relation. 
How do I approach it?
 A: For $n\ge 3$ we have $0<g(n-2)^2<g(n-1)^2$ so $0<g(n-1)^2<g(n)<2g(n)^2,$ so $$2\log g(n-1)<\log g(n)<\log 2+2\log g(n-1),$$ so $$2^{n-2}\log g(2)<\log g(n)<(n-2)\log 2+2^{n-2}\log g(2)$$ by induction on $n\ge 3,$ and $g(2)=2 $  so $$2^{2^{n-2}}<g(n)<2^{n-2+2^{n-2}}.$$ 
A: First prove $g(n) \le 2^{2^{n-1}-1}$ by induction on $n$ as follows. It is true for the base cases (equality holds). It is clear that $g$ is increasing, so $g(n) = g(n-1)^2 + g(n-2)^2 \le 2g(n-1)^2 \le 2\cdot (2^{2^{n-2}-1})^2 = 2^{2^{n-1} - 1}$, as required.
Once we have this fact, your limit is easy to compute (or at least bound in the way we need), as
$\frac{2^{2^{f(n)}}}{g(n)} \ge 2^{2^{f(n)} - 2^{n-1} + 1} \ge 2^{2^{n^2} - 2^{n-1} + 1} \to \infty$, as needed.
A: The $g_n$ are given in sequence $A000283$ in $OEIS$ (have look here). I you look at the formula, in year 2003, Benoit Cloitre  proposed
$$g_n=\left\lfloor A^{2^{n}}\right\rfloor$$ where 
$$A=1.23539273778543688962233101322844082434745718691367945473360\cdots$$ is "almost" $[\log(5) ]^{e^\gamma}-\log(3)=1.235392625$
Now it is quite obvious from the formulae that
$$r_n=\frac{2^{2^{f(n)} }}{g(n)}\to \infty$$
Considering $\log [\log (r_n)]$ and computing a few values before overflows
$$\left(
\begin{array}{cc}
n & \log [\log (r_n)] \\
 1 & 1.01978 \\
 2 & 3.36260 \\
 3 & 7.07101 \\
 4 & 12.1101 \\
 5 & 18.5121 \\
 6 & 26.2846 \\
 7 & 35.4316 \\
 8 & 45.9554 \\
\end{array}
\right)$$
If you plot these last results, you will see that they perfectly align along a quadratic in $n$.
