Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$



share|cite|improve this question

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)$.

share|cite|improve this answer
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$.

enter image description here

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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