3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.