I have an assignment tomorrow and we should proof that $$\lfloor{\log n}\rfloor = \left\lfloor \log\left( \Big\lfloor \frac{n-1}2 \Big\rfloor \right) \right\rfloor + 1$$ But the floor drives me crazy since I cannot relate to it. I believe that let $m=\lfloor{\log n}\rfloor$ so that $m=\lfloor{\log n}\rfloor$ then $m\le \log n<m+1$ and $2^m\le n<2^{m+1}$ and because $n\in N$ we know that its an interger so $2^m<n+1\le2^{m+1}$ and therefore $m+1=\lfloor \log n \rfloor+1$ but again the $\log(\lfloor\frac{n-1}{2}\rfloor$) part kills me.

Would really appreciate some hints since I stuck and can't get forward on my own.

  • 1
    $\begingroup$ The equations in the title and the content differ by a pair of $\lfloor\ \rfloor$. $\endgroup$ – peterwhy Apr 24 at 21:28
  • $\begingroup$ Is the $\log$ binary, as implied by your work? $\endgroup$ – peterwhy Apr 24 at 21:29
  • $\begingroup$ What is $n$? What if $n=1$? $\endgroup$ – peterwhy Apr 24 at 21:32
  • $\begingroup$ Pretty sure the inside is the ceil function and not floor. Also math.stackexchange.com/questions/3196363/… $\endgroup$ – kingW3 Apr 24 at 21:39
  • $\begingroup$ Will it help if you incorporate the $+1$ term into floor and then get it into $\log$ at the RHS...? $\endgroup$ – CiaPan Apr 24 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.