2
$\begingroup$

I've been asked to find an equivalent of the following recurrent sequence with $u_0=2$ : $u_{n+1}=u_n+\log u_n$.

It is clear that this is going to infinity with n, and I tried two things :

Solving the ODE $y'=\log y$, but I don't know what is the solution...

Finding a function $f$ such that $f(n+1,u_{n+1})-f(n,u_n)$ has a finite limit (non zero) in order to apply Cesaro.

But I'm stuck with only zeros limits, and numerically I observe that it's not growing much faster than $n^\alpha$...

Any clue about the sequence I have to consider ?

EDIT : You can also show that $u_{n+1}\sim u_n$

$\endgroup$

1 Answer 1

3
$\begingroup$

First, you notice that $u_n \ge 2$.

This means that $u_n \ge n \log 2$.

Plug it in again and get $u_n \succ \sum_{k=1}^n \log k \sim n\log n$.

Now for the other direction start out with $u_{n+1} < 2u_n$, therefore $u_n < 2^n$, therefore $u_{n+1} < u_n + O(n)$, therefore $u_n = O(n^2)$.

So we have $u_{n+1} = u_n + O(\log n)$, so $u_n \prec n\log n$.

So the asymptotic behaviour is $n\log n$. If you want the constant, you have to do the same argument with more care for detail.

$\endgroup$
1
  • $\begingroup$ You are right about $\sum_1^n \log k \sim n\log n$, that's the point I was missing. Your proof that $u_n$ has a lower bound equivalent to $n\log n$ is fine. But for the upper bound, the constant is larger than the real one that seems to be 1. But the asymptotic behaviour is indeed $cn\log n$. It works with convexity $\endgroup$
    – Bertrand R
    May 31, 2014 at 13:09

You must log in to answer this question.

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