Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.$

share|improve this answer
    
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. –  Christian Sep 2 '12 at 4:55
    
@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. –  Ross Millikan Sep 2 '12 at 5:37
    
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? –  Christian Sep 2 '12 at 8:06
    
@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. –  Ross Millikan Sep 2 '12 at 14:35

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.