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

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.

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.

• First step: look the sequence up in the Online Encyclopedia of Integer Sequences. – Gerry Myerson Nov 7 '13 at 11:30
• Yes, I already did that before, but the sequence (A198959) seems mainly unknown excepted for its bare definition and few first terms. I should have mentioned that, I edited the post in consequence, thanks. – Olivier Nov 7 '13 at 11:35
• If the OEIS knows little, chances are little is known. Do you have Finch's book, Mathematical Constants? – Gerry Myerson Nov 7 '13 at 11:37
• Yes, I had a look sooner, and I found nothing (excepted on page 8, with the nested radical constant, but with no more informations than online). I know there is not so many chances, but as the sequence itself looks quite simple, and as I'm basically asking for anything, I thought that was worth the try. Plus the fact that the OEIS sequence as been created in 2011, and never edited since, made me think that the lack of informations was maybe because this sequence is uninteresting (meaning it does not arise naturally in any problem) but not necessarily difficult or out of reach for any advance. – Olivier Nov 7 '13 at 11:54
• @Lucia this is the answer, not a comment-> make it an answer.. – username Nov 7 '13 at 14:31

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

• It looks to me that this does not prove $u_n \sim \lambda^{2^n}$ but only $u_n = \lambda^{2^n+o(2^n)}$. – Aurel Nov 7 '13 at 16:40
• OK studying the convergence speed of the product gives the equivalent. – Aurel Nov 7 '13 at 16:52
• @Aurel: Right; in fact the growth of the sequence is so rapid, that $u_n$ will in fact be the nearest integer to $\lambda^{2^n}$. – Lucia Nov 7 '13 at 19:10
• Yes, thanks, that's nice. Actually, yout exact same proof should work for every $\alpha > C$. Just one detail though, your very last sentence is wrong, your argument works only for $\alpha > C$ (where $C$ is defined in the top of my question). Because for $1 < \alpha < C$, the sequence is no longer increasing, neither positive. – Olivier Nov 10 '13 at 11:53
• @Olivier: Even if $\alpha$ is small, then initially the sequence may be small, but after a few steps it'll start to grow, and then what I said will hold. – Lucia Nov 10 '13 at 12:47

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.