Asymptotic behavior of the sequence $u_n = u_{n-1}^2-n$

Question

I am currently interested in the following sequence: $$\begin{cases}u_0 & = & \alpha\\u_n & = & u_{n-1}^2-n\end{cases}$$ where $\alpha > C \approx 1.75793275... $ with $C$ being the Nested Radical Constant.

I'm interested to get the behaviour of this sequence as $n$ grows to infinity.

Furthermore, even though I would love to have an answer for any $\alpha$, you can for the sake of simplicity simply consider the case where $\alpha = 2$. In what follows, I consider only this case.

The OEIS know little about this sequence (http://oeis.org/A198959), and is not really helpful.

Now, I know (meaning I proved) very few about this sequence. It is obviously non-negative, and non-decreasing. Plus it goes to infinity.

Then, I feel like we should have $u_n \sim \lambda^{2^n}$ for some $1 < \lambda \leqslant \alpha$. The good news is that, when I compute the first hundred of terms, this equivalent seems pretty correct, with (in the case $\alpha=2$) $\lambda \approx 1.613590596957970...$.

Unfortunately, I am stuck here. I have been unable to prove this equivalent, or to find the following terms in the expansion of this sequence. And Plouffe's inverter (now Inverse Symbolic Calculator) does not recognize this number.

Do any of you have any ideas, clues, proofs, or links to papers related to this sequence? As it is just a matter of mathematical curiosity, I would take any relevant advance (a proof of the equivalent, a way to get the following terms, a close value for $\lambda$ (or an implicit formula, or involving $C$ itself, or an algorithm, etc.), a solution for the general problem with $\alpha \neq 2$, etc.).

Of course, as I did not proved the equivalent, it may be just false, in that case a counterargument would be welcomed too :-).

Thanks all.

Answer 1

Let us just consider the case $\alpha=2$ where there is an elegant answer: There exists a constant $\lambda$ such that for all $n$ we have $u_n = \lceil \lambda^{2^n}\rceil$. First note that by induction it is easy to see that $u_n \ge (n+2)$ for all $n\ge 0$. Define $$ \lambda= 2 \prod_{n=1}^{\infty} \Big(1-\frac{n}{u_{n-1}^2}\Big)^{\frac{1}{2^n}}. $$ Using $u_n\ge n+2$ it is simple to see that the product above converges, and to a value at least $3/2$. Now we show that $u_n = \lceil \lambda^{2^n}\rceil$ as claimed above.

Put $v_n=u_n^{\frac{1}{2^n}}$. Then the recurrence is, for $n\ge 1$, $$ v_n=v_{n−1}\Big(1−\frac{n}{u_{n−1}^2}\Big)^{\frac{1}{2^n}}, $$ and so $$ v_n = 2 \prod_{j=1}^{n} \Big(1- \frac{j}{u_{j-1}^2}\Big)^{\frac{1}{2^j}}. $$ It follows that $v_n >\lambda$, or $u_n > \lambda^{2^n}$. Also using that $n/u_{n-1}^2$ is decreasing for $n\ge 1$, $$ v_n = \lambda \prod_{j=n+1}^{\infty} \Big(1-\frac{j}{u_{j-1}^2}\Big)^{-\frac{1}{2^j}} < \lambda \Big(1-\frac{n+1}{u_n^2}\Big)^{-\frac{1}{2^n}}. $$ Therefore $$ \lambda^{2^n} > u_n \Big(1- \frac{n+1}{u_n^2}\Big) > u_n - 1, $$ completing our proof.

For general $\alpha >1$, a similar argument would show very good asymptotics for large $n$.

Answer 2

Rather than defining a sequence in which the recursion depends on the number of iterations, it might be advantageous to simply consider this as iteration of the $2$-dimensional polynomial recursion $$ (x,y)\longrightarrow (x^2-y,y+1)$$ and look at the orbit of the point $(a,0)$ or $(a,1)$. There is a large literature on the dynamics of polynomial maps, although offhand I'm not sure how to search for this particular one. It sort of looks like a generalized Henon map, which are maps of the form $$ (x,y)\longrightarrow (a_0 x^2 + a_1 y + a_2,b_0 x + b_1 y+b_2),$$ but the fact that your $b_0$ is $0$ makes it more of a degeneration of a Henon map. Alternatively, it is an example of what is sometimes called a triangular map, which is a polynomial map of the form $$ (x,y) \longrightarrow \bigl(F(x,y),G(y)\bigr). $$ Again, there's lots in the literature on the dynamics of such maps.