solve inductive inequality $a_m>a_{m-1}+0.5 a_{m-1}^2$

Question

Let $a_0, a_1,...$ be sequence of positive numbers satisfying $a_0<1$ and $$ a_m>a_{m-1}+0.5 a_{m-1}^2. $$ We aim to show that when $a_m>1$ first time, $m$ is at most of the size $O(a_0^{-1})$. So far I can get $a_0^{-2}$ using very crude estimate. But I would like to know how to get the better bound. The number $0.5$ in the above inequality is not important.

Answer 1

The differential equation $y' = \frac 12 y^2$ has solution $y(t) = -2/t$, so your sequence should behave at worst qualitatively like $-2/t$ does for negative $t$, so $a_m^{-1}$ should slowly decrease, by at least about $-1/2$ at every step.

Let us formalize this :

If $0 < a_{m-1} < 1$, then
$\frac 1 {a_m} - \frac 1 {a_{m-1}} < \frac 1 {a_{m-1}}(\frac 1 {1 + \frac 12 a_{m-1}} - 1) = \frac 1 {a_{m-1}}\frac {-\frac 12 a_{m-1}} {1 + \frac 12 a_{m-1}} = - \frac 1 {2+a_{m-1}} < - \frac 13$

Hence $\frac 1{a_m} < - \frac 13 + \frac 1 {a_{m-1}}$.

So if $m$ is the first integer where $a_m \ge 1$ then this inequality is true up to this $m$, and $1 < \frac 1 {a_{m-1}} \le -\frac {m-1} 3 + \frac 1 {a_0}$.

Then rearranging this, you get $m < \frac 3{a_0}-2$

This factor $3$ is not the best, in fact, for any $\epsilon >0$ there is a $c_\epsilon$ such that $m < (2+\epsilon)a_0^{-1} + c_\epsilon$

Answer 2

I am able to get $m=O(a_0\log (1/a_0))$.

Let $f(x)=x+c\,x^2$ (where $c>0$ takes the place of $0.5$), and $0<a_0<1$. If $g(x)=f(a_0)+f'(a_0)(x-a_0)$, then $g(x)\le f(x)$, $g(x_0)=f(x_0)$ and $g'(x_0)=f'(x_0)$. Define $b_0=a_0$ and $b_{n+1}=b_n$, $n\ge1$. It is clear the the sequence $a_n$ reaches $1$ before $b_n$. It is easy to see that $$ g^n(x)=(1+2\,c\,a_0)^nx-\frac{a_0}{2}\bigl((1+2\,c\,a_0)^{n-1}-1\bigr). $$ If $N$ is the largest index such that $b_N<1$, we have $$ (1+2\,c\,a_0)^Na_0-\frac{a_0}{2}\bigl((1+2\,c\,a_0)^{N-1}-1\bigr)<1. $$ From here we deduce $$ a_0(1+2\,c\,a_0)^N<2\implies N<\frac{\log(2/a_0)}{\log(1+2\,c\,a_0)}\sim\frac{\log(2/a_0)}{2\,c\,a_0}. $$

Answer 3

I found another solution. The idea is to look at "doubling time": each $a_m$ will become $2a_m$ after at most $Ca_m^{-1}$ steps. We let $a_0$ keep doubling and sum over the numbers of steps needed: $a_0^{-1}+(2a_0)^{-1}+(4a_0)^{-1}+...$, which is at most $Ca_0^{-1}$.