Is there any way to show for $k \in \mathbb{N}$ $$\lfloor \log_2 k \rfloor + 1 = \lceil \log_2 (k + 1) \rceil$$

without casework, or of little of it as possible? I've tested it for some integers and I noticed that both sides seem to "transition" at the same point-- when $k$ is around powers of $2$ - but I don't know if I can explain it elegantly.

  • 3
    $\begingroup$ This is just due to the fact that there is no natural number between $\log_2(k)$ and $\log_2(k+1)$. Indeed, if the contrary was the case, then $\log_2(k) < n < \log_2(k+1)$, which yields $k < 2^n < k+1$, which is impossible. $\endgroup$ – amsmath Dec 11 '17 at 3:32
  • $\begingroup$ @amsmath 1) that is wrong. 2) comments are not the right place to post answers $\endgroup$ – miracle173 Dec 11 '17 at 3:58
  • $\begingroup$ @miracle173 Why is this wrong? And, of course, if something is very simple, you can well answer by comment. $\endgroup$ – amsmath Dec 11 '17 at 4:02
  • $\begingroup$ @amsmath I think your answer is correct. It's really nice because I can just include it as an elegant one-liner in my paper, and let the reader think for it about a moment themselves rather than interrupting the flow with a proof. $\endgroup$ – James Ko Dec 11 '17 at 4:12
  • $\begingroup$ I think with my argumentation you still need 3 cases. Therefore, I like Alexander's answer more. $\endgroup$ – amsmath Dec 11 '17 at 4:13

For $k\in\mathbb{N}$, $$\left\lfloor\log_2 k\right\rfloor=m \iff 2^m\le k<2^{m+1} \iff 2^m<k+1\le 2^{m+1} \iff \left\lceil\log_2(k+1)\right\rceil=m+1.$$

Note that this works "for any value of $2$", i.e. for any integer base $b>1$, not just $2$.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.