# Recurrence relation/inequality, $S(i) \leq d \cdot \log^c (S(i-1))$

During my reaserch I came across the folowwing recursion ineqaulity, I wonder if someone can help me to give a bound about this

$S(i) \leq d \cdot \log^c (S(i-1))$

where $s(1) = c_0$

Thanks!

Daniel

-

The sequence $(S(i))$ is bounded above and its limsup is at most the largest root, if any, of the equation $x=d\cdot\log^c(x)$.

-
Which I suppose can be solved using LambertW. – Aryabhata Jul 20 '11 at 19:16

I will assume that $d>0$, $c>0$ , $c_0>1$ and that $\log^c x=(\log x)^c$. Let $f(x)=d\,\log^cx$, and define the sequence $x_1=c_0$, $x_i=f(x_{i-1})$ for $i\ge2$ (the sequence terminates if for some $i$, $x_i<1$.) Since $f$ is increasing, it is easy to see that $S(i)\le x_i$. There are two different cases to consider:

1. $f(x)<x$ for all $x\ge 1$ (blue line)
2. The graph of $f$ cuts the diagonal of the first quadrant in two different points (red line). Let's call $a<b$ the two solutions of $f(x)=x$.

In the first case, the sequence $\{x_i\}$ will terminate in a finite number of steps. In the second case, if $c_0>a$, then the sequence $\{x_i\}$ converges to $b$; if $c_0<a$, then the sequence terminates in a finite number of steps; finally, if $c_0=a$, then $x_i=a$ for all $i$.

-