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$
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$
  • $\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 '14 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.