Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 http://math.stackexchange.com/ but received no answer nor comments.]

share|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
add comment

1 Answer

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|improve this answer
    
Peter, thank you for bearing with me and nailing this last bit. –  Christian Oct 5 '12 at 18:34
add comment

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.