3
$\begingroup$

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

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?

  • 0
    I wasn't going to spoil the fun for you, but this is known as [Hermite's Identity](http://en.wikipedia.org/wiki/Hermite's_identity).2012-02-07

3 Answers 3

2

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 and $\frac{n}m\le\{x\}<\frac{n+1}m$. Now consider $x+\frac{k}m$, where $0\le k:

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

  • 0
    @Avatar: Feel free to ask for more detail if it still doesn’t make sense in the morning.2019-04-24
1

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.

1

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.

  • 0
    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.2012-02-12