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 !

  • $\begingroup$ Considering this from the opposite perspective is interesting. If we have the differential equation $\frac{dy}{dx} = f(y)$ with initial condition $y(0) = y_0$, then applying Euler's method with step size $1$ gives us the approximation $y(n) \approx u_n$, where $u_n$ satisfies the recurrence $u_{n+1} = u_n + f(u_n)$ and $u_0 = y_0$. I suspect that your approach having the correct asymptotics is equivalent to the convergence some approximations from Euler's method to this differential equation's solution. $\endgroup$ Aug 15, 2020 at 15:49

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

  • $\begingroup$ Hi, thank you for your answer but I think the inequality $y(k)+f(w_k) \geq y(k)+f(y(k))$ is wrong since f is decreasing and $w_k \geq y(k)$ $\endgroup$
    – 25laps
    Aug 15, 2020 at 16:56
  • $\begingroup$ @25laps Of course, good catch. I do suspect that this argument can be fixed, but I'll have to think about it $\endgroup$ Aug 15, 2020 at 17:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .