# Proving $\lfloor 2x \rfloor = \lfloor x \rfloor + \lfloor x+0.5\rfloor$

I can intuitively see that this is true, but I'm having a very hard time proving it. I'm actually not even quite sure where to begin. I tried using the inequalities that define the floor function, and I'm pretty sure this is the way to go, but I'm failing to make any kind of progress.

I appreciate any help.

## 4 Answers

Hint: split it in to cases $x\in[n,n+\frac{1}{2})$ and $x\in[n+\frac{1}{2},n+1)$ for some integer $n$.

Case 1: The fractional part of $x$ is less than $1/2$, i.e. $x=n+a$ where $n$ is an integer and $0\le a<1/2$. Then $\lfloor 2x\rfloor = \lfloor 2n+2a \rfloor = 2n$. But also $\lfloor x\rfloor=n$ and $\lfloor x +0.5 \rfloor = n$. Since $2n=n+n$, the equality holds.

Case 2: The fractional part of $x$ is more than $1/2$, i.e. $x=n+a$ where $n$ is an integer and $1/2\le a<1$. I leave the remainder as an exercise; let me know if you need more help.

You can "draw" an integer in and out of the floor function ($\lfloor x+n\rfloor=\lfloor x\rfloor+n$). Then it suffices to establish the property for $x\in[0,\frac12)$ and $x\in[\frac12,1)$, because the three floors remain constant in these intervals.

• $x\in[0,\frac12)\implies0=0+0$,

• $x\in[\frac12,1)\implies1=0+1$.

Simple as that.


We are asked to prove $$\tag{0} \floor{2x} = \floor{x} + \floor{x + \tfrac 1 2}$$ for all real $\;x\;$. Looking at the graph of either side, we see that there is a kind of 'period' of length $\;\tfrac 1 2\;$ involved, specifically the intervals $[0,\tfrac 1 2)$, $[\tfrac 1 2, 1)$, etc. Abbreviating $\ref 0$ by $\;P(x)\;$, this suggests we investigate $\;P(x+\tfrac 1 2)\;$:

$$\calc P(x + \tfrac 1 2) \op=\hint{expand abbreviation \;P\;; simplify} \floor{2x + 1} = \floor{x + \tfrac 1 2} + \floor{x + 1} \op=\hint{move integer 1 out of floor, twice; subtract 1 from both sides} \floor{2x} = \floor{x + \tfrac 1 2} + \floor{x} \op=\hint{reorder RHS; abbreviation \;P\;} P(x) \endcalc$$

So we've proven $$\tag 1 \langle \forall x :: P(x) \;\equiv\; P(x + \tfrac 1 2) \rangle$$ which is a kind of 'induction step'. If we can additionally prove the 'base case' $$\tag 2 \langle \forall x : 0 \le x \lt \tfrac 1 2 : P(x) \rangle$$ then by induction our goal $\;\langle \forall x :: P(x) \rangle\;$ follows. Fortunately $\ref 2$ is easy to prove: assuming $\;0 \le x \lt \tfrac 1 2\;$, we have

$$\calc P(x) \op=\hint{abbreviation \;P\;} \floor{2x} = \floor{x} + \floor{x + \tfrac 1 2} \op=\hints{by the assumption, all three parts are in the [0,1) interval:} \hints{LHS: \;0 \le 2x \lt 1\;, first part of RHS: \;0 \le x \lt \tfrac 1 2 \lt 1\;,} \hints{second part of RHS: \;0 \lt \tfrac 1 2 \le x + \tfrac 1 2 \lt 1\;;} \hint{definition of floor} 0 = 0 + 0 \op=\hint{arithmetic} \true \endcalc$$

This completes the proof.