# Proof Verification: Show that $[mx] = \sum_{k=0}^{m-1} \, \bigg[x+\frac{k}{m} \bigg]$

I was wondering if this proof is valid.

I use $[x]$ to denote the floor of $x$.

Problem

Prove that

$$[mx] = \sum_{k=0}^{m-1} \, \bigg[x+\frac{k}{m} \bigg]$$

where $m \in \mathbb{N}$ and $x \in \mathbb{R}$.

Proof

Let $m \in \mathbb{N}$ and let $x \in \mathbb{R}$ such that $\epsilon = x - [x]$ where $0 \leq \epsilon < 1$.

Partition the interval $[0,1)$ as

$$[0,1) = \bigcup_{k=0}^{m-1} \, \bigg[\frac{k}{m}, \frac{k+1}{m} \bigg)$$

Let $p \in \{1, \dotsc, m\}$ and consider the interval

$$\frac{p-1}{m} \leq \epsilon < \frac{p}{m}$$

Expanding and simplifying the sum $\sum_{k=0}^{m-1} \, \big[x+\frac{k}{m} \big]$ renders

\begin{align} \sum_{k=0}^{m-1} \, \bigg[x+\frac{k}{m} \bigg] &= [x] + \bigg([x] + \bigg[\epsilon + \frac{1}{m}\bigg]\bigg) + \cdots + \bigg([x] + \bigg[\epsilon + \frac{m-1}{m} \bigg]\bigg) \\ &= m[x] + \sum_{k=1}^{m-1} \, \bigg[\epsilon + \frac{k}{m} \bigg] \end{align}

Since each term in the sum $\sum_{k=1}^{m-1} \, \big[\epsilon + \frac{k}{m} \big]$ either equals 0 or 1 depending on $p$, we observe that there are at most $(m-p)$ zeros and $(p-1)$ ones amongst the $(m-1)$ terms of the given series. Hence,

\begin{align} \sum_{k=0}^{m-1} \, \bigg[x+\frac{k}{m} \bigg] &= m[x] + \sum_{k=1}^{m-1} \, \bigg[\epsilon + \frac{k}{m} \bigg] \\\\ &= m[x] + (m-p)\cdot 0 + (p-1) \cdot 1 \\\\ &= m[x] + (p-1) \end{align}

Furthermore, $\frac{p-1}{m} \leq \epsilon < \frac{p}{m}$ implies $p-1 \leq m \cdot \epsilon < p$. Thus we can write

\begin{align} [mx] &= \big[m([x]+\epsilon)\big] \\\\ &= m[x] + [m \cdot \epsilon] \\\\ &= m[x] + (p-1). \end{align}

Since for all intervals $p = 1, \dotsc, m$ we have

\begin{align} \sum_{k=0}^{m-1} \, \bigg[x+\frac{k}{m} \bigg] &= [mx] \\ &= m[x] + (p-1) \end{align}

we conclude that $[mx] = \sum_{k=0}^{m-1} \, \bigg[x+\frac{k}{m} \bigg]$

• What does $[mx]$ mean? Is this like a floor/ceiling function where we just round off to the nearest integer, whether it is greater or lower than the value we are rounding off from? – Mr Pie Jan 17 '18 at 4:10
• @user477343 it’s the floor function. – Benedict Voltaire Jan 19 '18 at 13:44
• I thought the floor function of a value $x$ is expressed as $\lfloor x \rfloor$ instead of $[x]$ but I guess there is more than one way. With a bit of research, nonetheless, it seems that $[x]$ denotes the set of congruence classes of $x$ ?? – Mr Pie Jan 23 '18 at 14:48
• @user477343 Yes, you’re correct on both points. However, some texts use $[x]$, so it just depends on the author. For example, Rosen’s number theory text uses the brackets. – Benedict Voltaire Jan 23 '18 at 17:27
• @user477343 no problem! – Benedict Voltaire Jan 26 '18 at 15:04

There are a couple of small bugs, but the argument is basically correct. When you partition $[0,1)$, you want either $\bigcup_{k=0}^{m-1}\left[\frac{k}m,\frac{k+1}m\right)$ or $\bigcup_{k=1}^m\left[\frac{k-1}m,\frac{k}m\right)$. In the next sentence you should not be considering all $m$ values of $p$: you already have $\epsilon=x-\lfloor x\rfloor$, and you’re defining $p$ to be the unique member of $\{1,\ldots,m\}$ such that

$$\frac{p-1}m\le\epsilon<\frac{p}m\;.$$

A bit later you say that $\sum_{k=1}^{m-1}\left\lfloor\epsilon+\frac{k}m\right\rfloor$ is $0$ or $1$ depending on $p$; what you mean, I think, is that each term of that sum is $0$ or $1$.

The same basic idea can be carried out a bit more compactly.

Let $\ell\in\{0,\ldots,m-1\}$ be maximal such that $x+\frac{\ell}m<\lfloor x\rfloor+1$. Then $\left\lfloor x+\frac{k}m\right\rfloor=\lfloor x\rfloor$ for $k=0,\ldots,\ell$, and $\left\lfloor x+\frac{k}m\right\rfloor=\lfloor x\rfloor+1$ for $k=\ell+1,\ldots,m-1$. Thus,

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

This also implies that

$$1-\frac{\ell+1}m\le x-\lfloor x\rfloor<1-\frac{\ell}m$$

and hence that

$$m-\ell-1\le mx-m\lfloor x\rfloor<m-\ell\;,$$

or

$$m\lfloor x\rfloor+m-\ell-1\le mx<m\lfloor x\rfloor+m-\ell\;.\tag{2}$$

But $(2)$ implies that $\lfloor mx\rfloor=m\lfloor x\rfloor+m-\ell-1$, which, when combined with $(1)$, yields the desired result:

$$\lfloor mx\rfloor=\sum_{k=0}^{m-1}\left\lfloor x+\frac{k}m\right\rfloor\;.$$

• I corrected the bugs in the proof, and I appreciate your solution to the problem that is in the spirit of what I attempted to do. If I fixed those issues you mentioned, do you think my answer would be sufficient to turn in for homework? I was wondering if you wouldn't mind acknowledging some small things I can change in the presentation of my answer as to make ti clearer to follow. I appreciate your help! – Benedict Voltaire Feb 27 '16 at 0:16
• @Benedict: I would make a couple more changes. First, it would be clearer if you wrote ‘Let $m\in\Bbb N$ and $x\in\Bbb R$, and define $\epsilon=x-\lfloor x\rfloor$. The other I already mentioned: instead of ‘Let $p=1,2,\ldots,m$ ...’, I would specifically define $p$ as the unique member of $\{1,\ldots,m\}$ such that $\frac{p-1}m\le\epsilon<\frac{p}m$. (Note that you need to allow for the possibility that $p=m$, but not for $p=0$.) – Brian M. Scott Feb 27 '16 at 0:25
• When I say, "Let $p \in \{1, \cdots, m\}$", doesn't it imply that $p$ is unique or do I have to explicitly state that it is unique? If I do have to make it explicit, what is the reason for doing that? – Benedict Voltaire Feb 27 '16 at 0:30
• @Benedict: ‘Let $p\in\{1,\ldots,m\}$ and consider thing-involving-p’ is the language used when you want to consider an arbitrary $p\in\{1,\ldots,m\}$. You don’t want to do that: you want very specifically to consider the integer $p$ defined by the inequalities that follow. You could say ‘There is a $p\in\{1,\ldots,m\} such that$\frac{p-1}m\le\epsilon<\frac{p}m$’ and go on with ‘Expanding ...’; that would be fine. – Brian M. Scott Feb 27 '16 at 0:34 I think it's a good effort but your proof is difficult to follow due to some issues with presentation and definition. For example, the partition of$[0,1) = \bigcup_{k=1}^m [k/m, (k+1)/m)$is problematic because it obviously fails to contain$0$. Also, if you say "let$p = 1, 2, \ldots, m$and consider the$p^{\rm th}$subinterval..." this is not clear, nor is it clear that if$p$is to take on a sequence of values, that in fact the following inequality is true for at most one particular$p$. At that point, I stopped reading carefully. A more elegant proof of the stated identity exploits periodicity: consider the function defined for all nonnegative integers$m$and reals$x: $$f_m(x) = -\lfloor mx \rfloor + \sum_{k=0}^{m-1} \left\lfloor x + \frac{k}{m} \right\rfloor.$$ Then note that \begin{align*} f_m(x+1/m) &= -\lfloor m(x+1/m) \rfloor + \sum_{k=0}^{m-1} \left\lfloor x + \frac{k+1}{m} \right\rfloor \\ &= -\lfloor mx \rfloor - 1+ \sum_{k=1}^m \left\lfloor x + \frac{k}{m} \right\rfloor \\ &= f_m(x) - 1 + \lfloor x+m/m\rfloor - \lfloor x \rfloor \\ &= f_m(x).\end{align*} That is to say,f_m$is a periodic function for which$1/m$is an integer multiple of its period. So it suffices to consider the behavior of$f_m(x)$on the interval$x \in [0, 1/m)$. But on this interval,$\lfloor mx \rfloor = 0$, and because$0 \le x + k/m < 1$for all$0 \le k \le m-1$and$0 \le x < 1/m$, all the terms in the sum are also zero; thus$f_m(x)$is identically zero on$[0,1/m)$, and by extension, is zero for all$x \in \mathbb R\$. This completes the proof.

• I haven't learned about periodic functions yet, but such an approach does provide an elegant and simple proof! Thank you for your help. – Benedict Voltaire Feb 27 '16 at 0:19