MathOverflow is a question and answer site for professional mathematicians. 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

Given two natural numbers $p$ and $i$, such that $0 < i \leqslant 2^p$, let $$ \Phi(p,i) := \frac{1}{2^p+1} + \frac{1}{(i+1)^2} - \frac{1}{2^p}\lg\left(\frac{2^p}{i}+1\right), $$ where $\lg x$ is the binary logarithm. With the help of a Computer Algebra System, it seems that

  • If $0 \leqslant p \leqslant 3$, then $\Phi(p,i) < 0$.

  • If $4 \leqslant p$, there exists $i_p$ such that $\Phi(p,i_p) = 0$ and $\Phi(p,i) > 0$ for $1 \leqslant i < i_p$, and $\Phi(p,i) < 0$ for $i_p < i \leqslant 2^p$.

How can I prove this?

Just in case, the partial derivative with respect to $i$ is: $$ \frac{\partial\Phi}{\partial i}(p,i) = \frac{1}{i(2^p+i)\ln 2} - \frac{2}{(i+1)^3}, $$ where $\ln x$ is the natural logarithm.

[Note: I asked this question over at but received no answer nor comments.]

share|cite|improve this question
I doubt that this is research level. To start with, I would analyse the cubic polynomial in $i$ which arises from $\frac{\partial\Phi}{\partial i}(p,i)=0$. – Peter Mueller Oct 5 '12 at 9:33
The context in which this question arises is noble enough (analysis of algorithms), but giving too many details here would further discourage knowledgeable people to try and help, I think. $\partial\Phi/\partial i = 0 \Leftrightarrow i^3 + (3-2\ln 2)i^2 + (3 - 2^{p+1}\ln 2)i + 1 = 0$. Solving another cubic equation, we find that if $p=0,1,2$, then there is only one real root and, if $p \geqslant 3$, there are three real roots. The exact expression of these roots is so unwieldy it is unhelpful. How can I show that $\partial\Phi/\partial i < 0$ if $0 < i \leqslant 2^p$ and $p \geqslant 4$? – Christian Oct 5 '12 at 11:54
up vote 0 down vote accepted

Suppose $p\ge3$, so the cubic $q(i)$ has $3$ real roots. As the product of the roots is $-1$, at most two of them are positive. From $q(0)=1>0$, $q(1)<0$, $q(+\infty)>0$ we see that there are exactly two positive roots, one in $]0,1[$, the other one in $]1,\infty[$. Now $\Phi(0+)=-\infty$, $\Phi(1)>0$, $\Phi(2^p)<0$, and the result follows from the intermediate theorem.

share|cite|improve this answer
Peter, thank you for bearing with me and nailing this last bit. – Christian Oct 5 '12 at 18:34

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.