# Proof that $\forall k\in\mathbb Z^+$, $\lfloor\log_2(2k+1)\rfloor=\lfloor\log_2(2k)\rfloor$

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

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

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*}$$