# 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.

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.

Here is an alternative approach, which does not require a case split, and instead uses a form of induction. I found this approach (through Wikipedia) in Matsuoka, Yoshio (1964), "Classroom Notes: On a Proof of Hermite's Identity", The American Mathematical Monthly 71 (10): 1115 (doi: 10.2307/2311413).\newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\floor}[1]{\lfloor#1\rfloor} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}}

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.