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
    @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