I wrote a proof for this but am not completely sure if this is valid. Specifically, can I go from $m\leq k+0.5$ to $m\leq k$ because $m,k\in\mathbb Z^+$ with no further explanation? Any feedback would be greatly appreciated!

Proof. Let $n=\lfloor\log_2(2k+1)\rfloor$. Then, $$\begin{align*} n&\leq\log_2(2k+1)\lt n+1&&\text{(since $\forall x\in\mathbb R$, $\lfloor x\rfloor\leq x\lt x+1$),}\\ \implies2^n&\leq2k+1\lt2^{n+1}&&\text{(by algebra).}\\ \end{align*}$$ Observe that $2^n\in2\mathbb Z^+$ so $2^n=2m$ for some $m\in\mathbb Z^+$. Thus, $$\begin{align*} 2m&\leq2k+1&&\text{(since $2m=2^n\leq2k+1$),}\\ \implies m&\leq k+0.5&&\text{(by algebra),}\\ \implies m&\leq k&&\text{(since $m,k\in\mathbb Z^+$),}\\ \implies 2m&\leq2k&&\text{(by algebra),}\\ \implies 2^n&\leq2k&&\text{(since $2^n=2m$),}\\ \implies 2^n&\leq2k\lt2^{n+1}&&\text{(since $2k+1\lt2^{n+1}\rightarrow2k\lt2^{n+1}$),}\\ \implies n&\leq\log_2(2k)\lt n+1&&\text{(by algebra),}\\ \therefore n&=\lfloor\log_2(2k)\rfloor&&\text{(since $\forall x\in\mathbb R$, $\lfloor x\rfloor\leq x\lt x+1$).} \end{align*}$$ $$\tag*{$\blacksquare$}$$

  • $\begingroup$ In your latter paragraph it seems you can just go from line $1$ to lines $4/5$ $\endgroup$
    – David P
    Dec 3, 2019 at 21:29
  • $\begingroup$ Your proof looks good to me! $\endgroup$
    – Bram28
    Dec 3, 2019 at 21:37

1 Answer 1


Note that for all $n \in \mathbb{N_{>0}} $ there exist $m \in \mathbb{N}$ such that \begin{eqnarray*} 2^m \leq n < 2^{m+1}. \end{eqnarray*} This value $m$ is $\lfloor\log_2(n)\rfloor$ And $n$ increases passed a power of $2$ the value $m$ will increase by $1$.

If $n$ increases (by $1$) from an even value to an odd value the $m$ will not change (provided $n>1$). So \begin{eqnarray*} \lfloor\log_2(2k+1)\rfloor = \lfloor\log_2(2k)\rfloor. \end{eqnarray*}


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.