Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I wasn't going to spoil the fun for you, but this is known as Hermite's Identity. –  JavaMan Feb 7 '12 at 21:12
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
I'm still not seeing it. I'll have to think about it in the morning. Thanks for your reply though. –  AvatarOfChronos Feb 7 '12 at 5:18
    
@Avatar: Feel free to ask for more detail if it still doesn’t make sense in the morning. –  Brian M. Scott Feb 7 '12 at 6:34
    
Thanks for your answer. It helped a lot. –  AvatarOfChronos Feb 8 '12 at 16:11
add comment

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.

share|improve this answer
    
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. –  robjohn Feb 12 '12 at 17:13
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.