0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – Peter Mueller
    Commented Oct 5, 2012 at 9:33
  • $\begingroup$ 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$? $\endgroup$
    – Christian Rinderknecht
    Commented Oct 5, 2012 at 11:54

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Peter, thank you for bearing with me and nailing this last bit. $\endgroup$
    – Christian Rinderknecht
    Commented Oct 5, 2012 at 18:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .