# Solving recursion by analogy with a differential equation

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 !

• 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. Aug 15, 2020 at 15:49

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.
• 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)$ Aug 15, 2020 at 16:56