1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mr Pie Jan 17 '18 at 4:10
  • $\begingroup$ @user477343 it’s the floor function. $\endgroup$ – Benedict Voltaire Jan 19 '18 at 13:44
  • $\begingroup$ 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$ ?? $\endgroup$ – Mr Pie Jan 23 '18 at 14:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Benedict Voltaire Jan 23 '18 at 17:27
  • 1
    $\begingroup$ @user477343 no problem! $\endgroup$ – Benedict Voltaire Jan 26 '18 at 15:04
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Benedict Voltaire Feb 27 '16 at 0:16
  • 1
    $\begingroup$ @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$.) $\endgroup$ – Brian M. Scott Feb 27 '16 at 0:25
  • $\begingroup$ 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? $\endgroup$ – Benedict Voltaire Feb 27 '16 at 0:30
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Feb 27 '16 at 0:34
1
$\begingroup$

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.

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

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.