1
$\begingroup$

Given two natural numbers $i$ and $p$ such that $0 < i < 2^p$, a real constant $b$ must satisfy the inequality $$ (2^p+i)\lg(2^p+i) - p2^p - i\lg i - (2^p+i) + \frac{2^p}{i+1} + \frac{i}{2^p+1} \leqslant b, $$ where $\lg n$ is the binary logarithm of $n$. (This problem comes from the analysis of an algorithm which relies on the binary notation of $n$ when it is strictly between two consecutive powers of $2$, i.e., $n = 2^p + i$.)

I would like to show that, for all $p$ and $i$, the left-hand side has a smallest upper bound, and use it to minimize $b$. (I would hope $b_{\min} = 2$.)

How would you tackle this?

1 Answers 1

1

I made a spreadsheet and the local maxima occur at $i=2^p-1$. At $n=63, p=5, i=31$ the expression is $1.927943$ and at $n= 4194303, p=21, n= 2097151$ it is just under $2.$ We can see that for these cases the expression is almost $2^{p+1}(p+1) - p2^p -p2^p-2^{p+1}+1+1=2.$ If we take the derivative at $i=2^{p-}$ we get $1-\frac{2^p(2^p+2)}{(2^p+1)^2} \gt 0$ so the value at $i=2^p-1$ will be less than $2.$

  • 0
    Thank you for your interest in my question. This is good news, but is there a way to be absolutely certain that the local maxima occurs at $i=2^p-1$? Global maxima are probably more difficult to make out, right? I have never taken multivariate calculus in college. I tried to proceed by making two cases: $i=2^q$ and $i=2^q+j$, with $0 < j < 2^q$, hoping to handle the logarithms, but nothing conclusive.2012-09-02
  • 0
    @Christian: yes, you can regard it as a function of real $i$ instead of integer, then take the derivative. It will be positive except for the breakpoints at $2^p$, so is increasing.2012-09-02
  • 0
    Ah, so your approach is to fix $p$ and let $i$ range as $0 < i \leqslant 2^p$. Then you derive the left-hand side with respect to $i$, and you show that the derivative is positive everywhere except when $i=2^p$. Therefore, you conclude that the (implicit) function increases and its smaller upper bound is the limit when $i=2^{p-}$. Finally, you come back to the integers and settle for $i=2^p-1$. Did I understand you correctly?2012-09-02
  • 0
    @Christian: exactly. As things are discontinuous at $i=2p$ there is no derivative there, but you can approach it from below (which is the case of interest). I got Alpha to do the derivative for me.2012-09-02