Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.