I am reading the "Algorithm Design" (Kleinberg et al). Inside this book, at the chapter 11.6 there is an inequality I have failed to resolve.
Considering $\beta=m^{(1/3)}$ and $|I|>=1$ (it is a set) divide the follower inequality by $\beta^2$:
$ \beta^2|I^*|<=2(\beta^3|I|+m)+\beta|I|) $
The book say that this division results:
$ |I^*|<=(4m^{1/3}+1)|I| $
I try several time to resolve this inequality but I have never succeeded in referring to the above formula.
For more details on this inequality you can see the Kleinberg book at p. 630.
Thanks, Marco
We have of course $\beta^3 = m$, so we can rewrite the original expression as
$\beta^2 |I^*| \leq 2(\beta^3|I| + \beta^3) + \beta |I|$.
Then dividing by $\beta^2$,
$|I^*| \leq 2 \beta |I| + 2 \beta + \frac{|I|}{\beta} = 2m^{1/3} |I| + 2m^{1/3} + \frac{|I|}{m^{1/3}}$.
The two short steps that are glossed over in the proof are to notice that since $|I| \geq 1$, $2m^{1/3} \leq 2m^{1/3}|I|$, and (since presumably $m \geq 1$) that $\frac{|I|}{m^{1/3}} \leq |I|$. Then we have
$2m^{1/3} |I| + 2m^{1/3} + \frac{|I|}{m^{1/3}} \leq 2m^{1/3} |I| + 2m^{1/3} |I| + |I| = (4m^{1/3} + 1)|I|$, as desired.