Precise asymptotic estimate of a recurrence sequence involving a square root

Question

Consider a recurrence sequence defined like this:

$$ \begin{cases} x_0 = \varepsilon \\ x_{n+1} = x_n + \varepsilon \sqrt{x_n}. \end{cases}$$

I am interested in estimating the value of $x_{\varepsilon^{-1}}$. I'm not very used to recurrence sequences, moreover here we have a square root (which I remember to be quite troublesome) and I am not interested in the asymptotic behavior, but in the behavior of a specific $x_{n}$. I tried running a little MATLAB code and apparently no matter the value of $\varepsilon$ (provided it's small enough), for some reason $x_{\varepsilon^{-1}} \approx 1/4$. How should one try to prove it rigorously?

Answer 1

Your difference equation can be viewed as the Euler method for the initial value problem $y'(t)=\sqrt{y}$, $y(0)=\epsilon$, on the interval $0\le t\le 1$, with step size $h=\epsilon$.

This we can of course solve explicitly: $y(t)=(t/2+\sqrt{\epsilon})^2$; in particular, $y(1)\to 1/4$, as desired. We still need to show that $x_{1/\epsilon}-y(1)\to 0$ also, which is essentially the convergence of the Euler method, but for varying initial value. As a consequence, this runs into the annoying technical problem that we don't have a uniform Lipschitz constant on the RHS $f(y)=\sqrt{y}$ of our ODE, so the usual error bounds for the Euler method are useless here.

However, we can do these estimates by hand, and we don't have to be particularly careful for what we need here. Sketch: Write $y_n=y(n\epsilon)$; we want to control $|y_n-x_n|$. We have $$ y_{n+1}=y_n+\epsilon\sqrt{y_n}+\epsilon^2/4 . $$ So clearly $y_n\ge x_n$. On the other hand, we can prove by induction that $y_n\le x_n +n^{3/2}\epsilon^2$, say, which is good enough.