The question is to prove that if m is a positive integer then, $$[mx] = [x] + \left[x+\frac{1}{m}\right] +\left[x+\frac{2}{m}\right] + \cdots + \left[x+\frac{(m-1)}{m}\right] $$ for $x \in \mathbb{R}$. Where $[x] =n$ such that $ n \leq x <n+1$

I'm given that the solution should use the pigeonhole principle. So I need to look for $n$ boxes where I'm trying to stuff $n+1$ things (my understanding of the pigeonhole principle). If I look at the fractional part of x I see $\{x\} \in [0,1)$ where $\{x\}$ is the fraction part of x. So $m\{x\} \in [0,m)$. I can break this interval into $[0,1) [1,2) \ldots [m-1,m)$ or I can divide everything by m and get $[0,\frac{1}{m}) [\frac{1}{m},\frac{2}{m}) \ldots [\frac{m-1}{m},1)$ and get m intervals of length $\frac{1}{m}$ which is my "n" boxes.

I am however stuck with regards to the "$n+1$" objects to put in the box and how to relate this observation to the question. Can anybody provide a hint or point out a flaw in what I have so far?

  • $\begingroup$ I wasn't going to spoil the fun for you, but this is known as Hermite's Identity. $\endgroup$ – JavaMan Feb 7 '12 at 21:12

I wouldn’t use the pigeonhole principle: it’s not needed. You know that there is a unique integer $n$ such that $0\le n<m$ and $\frac{n}m\le\{x\}<\frac{n+1}m$. Now consider $x+\frac{k}m$, where $0\le k<m$:

$$x+\frac{k}m=\lfloor x\rfloor +\{x\}+\frac{k}m\;,$$ so

$$\lfloor x\rfloor+\frac{n+k}m\le x+\frac{k}m<\lfloor x\rfloor +\frac{n+1+k}m\;.\tag{1}$$

What does $(1)$ tell you about $\left\lfloor x+\frac{k}m\right\rfloor$? Specifically, for how many values of $k$ will it be $\lfloor x\rfloor$, and for how many will it be $\lfloor x\rfloor+1$? If you can answer that, you’ll have a good handle on the righthand side of your desired equation.

As for the lefthand side, start from the fact that $\lfloor mx\rfloor=\big\lfloor m(\lfloor x\rfloor+\{x\})\big\rfloor$.

Most of the Missing Detail: If $0\le k\le m-n-1$, $(1)$ tells us that

$$\lfloor x\rfloor\le\lfloor x\rfloor+\frac{n}m\le \lfloor x\rfloor+\frac{n+k}m\le x+\frac{k}m<\lfloor x\rfloor+\frac{n+k+1}m=\lfloor x\rfloor+1\;;$$

after getting rid of the excess baggage, we have $$\lfloor x\rfloor\le x+\frac{k}m<\lfloor x\rfloor+1\;,$$ and therefore $$\left\lfloor x+\frac{k}m\right\rfloor=\lfloor x\rfloor\;.\tag{2}$$

On the other hand, if $m-n\le k\le m-1$, $(1)$ implies that

$$\lfloor x\rfloor+1\le\lfloor x\rfloor+\frac{n+k}m\le x+\frac{k}m<\lfloor x\rfloor+\frac{n+1+k}m\le\lfloor x\rfloor+\frac{n+m}m<\lfloor x\rfloor+2$$

and hence that $$\left\lfloor x+\frac{k}m\right\rfloor=\lfloor x\rfloor +1\;.\tag{3}$$

Now $(2)$ holds for $m-n$ values of $k$, and $(3)$ holds for the other $n$ values of $k$, so

$$\begin{align*}\sum_{k=0}^{m-1}\left\lfloor x+\frac{k}m\right\rfloor&=(m-n)\lfloor x\rfloor+n(\lfloor x\rfloor+1)\\ &=m\lfloor x\rfloor+n\;. \end{align*}$$

But $$\begin{align*} \lfloor mx\rfloor&=\big\lfloor(m\lfloor x\rfloor+\{x\})\big\rfloor\\ &=\big\lfloor m\lfloor x\rfloor+m\{x\}\big\rfloor\\ &=m\lfloor x\rfloor+\lfloor m\{x\}\rfloor\;, \end{align*}$$

since $m\lfloor x\rfloor$ is an integer.

Now you need only show that $\lfloor m\{x\}\rfloor=n$ to finish the argument. Go back to the beginning to recall how $n$ was defined.

  • $\begingroup$ I'm still not seeing it. I'll have to think about it in the morning. Thanks for your reply though. $\endgroup$ – AvatarOfChronos Feb 7 '12 at 5:18
  • $\begingroup$ @Avatar: Feel free to ask for more detail if it still doesn’t make sense in the morning. $\endgroup$ – Brian M. Scott Feb 7 '12 at 6:34

For $m\in\mathbb{Z}$, define $$ f_m(x)=\lfloor mx\rfloor-m\lfloor x\rfloor\tag{1} $$ For $k\in\mathbb{Z}$, $\lfloor x\rfloor-k=\lfloor x-k\rfloor$; thus, because $m\lfloor x\rfloor\in\mathbb{Z}$, we have $$ \begin{align} f_m(x) &=\lfloor mx\rfloor-m\lfloor x\rfloor\\ &=\lfloor mx-m\lfloor x\rfloor\rfloor\\ &=\lfloor m(x-\lfloor x\rfloor)\rfloor\tag{2} \end{align} $$ Since $0\le x-\lfloor x\rfloor<1$, we get that $0\le\lfloor m(x-\lfloor x\rfloor)\rfloor\le m-1$; that is, $$ 0\le f_m(x)\le m-1\tag{3} $$ Furthermore, for $k\in\mathbb{Z}$, $$ \begin{align} f_m\left(x+\frac{k}{m}\right) &=\left\lfloor m\left(x+\frac{k}{m}\right)\right\rfloor-m\left\lfloor x+\frac{k}{m}\right\rfloor\\ &=\left\lfloor mx\vphantom{\frac{k}{m}}\right\rfloor+k-m\left\lfloor x+\frac{k}{m}\right\rfloor\\ &\equiv\lfloor mx\rfloor+k-m\lfloor x\rfloor\pmod{m}\\ &=f_m(x)+k\tag{4} \end{align} $$

Therefore, $(3)$ and $(4)$ show that for $k=0,1,\dots,m-1$, $f_m\left(x+\frac{k}{m}\right)$ takes on each value $0,1,\dots,m-1$. Thus, $$ \sum_{k=0}^{m-1}f_m\left(x+\frac{k}{m}\right)=\frac{m(m-1)}{2}\tag{5} $$ Relating $(5)$ and $(1)$ yields $$ \begin{align} \frac{m(m-1)}{2} &=\sum_{k=0}^{m-1}\left\lfloor m\left(x+\frac{k}{m}\right)\right\rfloor-m\left\lfloor x+\frac{k}{m}\right\rfloor\\ &=\sum_{k=0}^{m-1}\left\lfloor mx\vphantom{\frac{k}{m}}\right\rfloor+k-m\left\lfloor x+\frac{k}{m}\right\rfloor\\ &=m\lfloor mx\rfloor+\frac{m(m-1)}{2}-\sum_{k=0}^{m-1}m\left\lfloor x+\frac{k}{m}\right\rfloor\tag{6} \end{align} $$ Simplifying equation $(6)$ yields $$ \lfloor mx\rfloor=\sum_{k=0}^{m-1}\left\lfloor x+\frac{k}{m}\right\rfloor\tag{7} $$ As far as I see, step $(5)$, where we fill up all the equivalence classes $\!\!\!\pmod{m}$, is as close to a pigeonhole as we get.

  • $\begingroup$ I am undeleting my answer since it has been almost a week since the original question and I think it is different enough from @BrianScott's answer not to be a duplicate. $\endgroup$ – robjohn Feb 12 '12 at 17:13

Hint: it's clear upon writing $x$ in radix $m$, e.g. for $\:m = 10\:$ and $\:x = 12.34\:$ we have

$\qquad \lfloor 12.{\color{red}3}4\rfloor + \lfloor 12.44\rfloor + \lfloor 12.54\rfloor +\:\cdots\:+ \lfloor {\color{red}{13.04}}\rfloor + \lfloor {\color{red}{13.14}}\rfloor + \lfloor {\color{red}{13.24}} \rfloor $

$\quad =\ 10\cdot 12 + {\color{red}3}\ =\ \lfloor 10\cdot 12.34 \rfloor$

So the "boxes" for the box principle are the $m$ possible digits following the decimal point.

Notice how the choice of radix representation greatly clarifies the innate structure.


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.