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

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$.

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.