Solving quadratic recurrence inequality

Question

Let $(n_k)$ be a sequence of natural numbers starting at $n_1=2$ and growing as follows $$n_k\leq n_{k+1}\leq n_k^2+2$$ As far as I know this sort of dynamical system may have no closed-form solution, but even if it has one, the $=$ replaced in it by $\leq$ would include more sequences than the above recurrence allows.

Can we obtain some upper bound for $n_k$ (depending on $k$ only) that holds if and only if $n_k$ satisfies the above recurrence? In other words, how do I solve (such) quadratic recurrence inequalities?

Answer 1

"Obviously", $n_j$ is maximal if $n_{k+1}=n_k^2+2$ for $k=1,\ldots,j-1$. In this case the sequence goes $2,6,38,1446,\ldots$ and grows roughly $\sim c^{2^k}$ for suitable $c$. For example, $n_k\le\sqrt3^{2^k}-2$ follws quickly by induction, and $\sqrt 3$ can be lowered to $\approx 1.576$ except for small indices.

Answer 2

For the sequence $u_k$ such that $u_1=n_1$ and $u_{k+1}=u_k^2+2$, we can write $$\frac{\log u_{k+1}}{2^{k+1}}=\frac{\log u_{k}}{2^{k}}+\frac{1}{2^{k+1}}\log(1+\frac{2}{u_k^2})$$ hence we get $$\frac{\log u_{n}}{2^{n}}=\frac{\log n_1}{2}+\sum_{k=1}^{n-1}\frac{1}{2^{k+1}}\log(1+\frac{2}{u_k^2})$$

As the series is clearly convergent, $\displaystyle \frac{\log u_{n}}{2^{n}}\to C$, with $\displaystyle C=\frac{\log n_1}{2}+\sum_{k=1}^{\infty}\frac{1}{2^{k+1}}\log(1+\frac{2}{u_k^2})$

and $C$ can be well approximated.