Solving recursion by analogy with a differential equation

Question

I came across this problem:

---

Let sequence $u_n$ be defined by its first term $u_0 > 0$ and $$\forall n \in \mathbb{N}, \quad u_{n+1} = u_n + \frac{1}{u_n}$$ Find an asymptotic formula for $u_n$.

---

I thought that we could solve it by analogy with the equation $$f' = \frac{1}{f}$$ which gives the asymptotic formula $u_n \sim \sqrt{2 n}$, and this is indeed the right answer.

More generally, is we take $u_0 > 0, \forall n \in \mathbb{N}, u_{n+1} = u_n + f(u_n)$, what would be the conditions on a continuous, positive, decreasing function $f$ such that the method of analogy with a differential equation gives the right asymptotic formula ?

Thanks a lot !

Answer 1

As is noted in the comment below, this answer is incorrect

---

Suppose that $y$ is a solution to the differential equation $y' = f(y)$, and $u_n$ solves the recurrence $u_{n+1} = u_n + f(u_n)$ with $u_0 = y(0)$. By the mean value theorem, we find that for all $n$, there exists a $c \in [n,n+1]$ for which $y(n+1) - y(n) = y'(c).$ Because $f$ is decreasing, we have $$ f(y(n)) = y'(n) \geq y(n+1) - y(n) \geq y'(n+1) = f(y(n+1)). $$ Now, suppose that $w_n$ satisfies $w_{n+1} = w_n + f(w_n)$, and $w_0 = y(1)$. We find inductively that $u_n \leq y(n) \leq w_n$. In particular, we we that if the inequality holds for $n = k$, then $$ \begin{align} w_{k+1} &= w_k + f(w_k) \geq y(k) + f(w_k) \geq y(k) + f(y(k)) \\ & \geq y(k) + [y(k+1) - y(k)] = y(k+1), \end{align} $$ and the inequality $y(k+1) \geq u_{k+1}$ can be seen similarly.

With that, we can conclude the following: if $f$ is such that the recurrence $u_{n+1} = f(u_n) + u_n$ has the same asymptotics for all $u_0 > 0$, then it follows that the asymptotics of the sequence $(y(n))_{n \in \Bbb N}$ generated from a solution to $y' = f(y)$ with $y(0) > 0$ are the same.