# Prove that $\sum_{i=1}^{\frac{n-1}{2}}\left\lfloor\frac{mi}{n}+\frac{1}{2}\right\rfloor$ is an even number

Let $m$, $n$ be positive odd numbers such that $\gcd(m,n)=1$. Show that

$$\sum_{i=1}^{\frac{n-1}{2}}\left\lfloor\dfrac{mi}{n}+\dfrac{1}{2}\right\rfloor$$

is an even number, where $\lfloor{x}\rfloor$ is the largest integer not greater than $x$.

My try: $$\sum_{i=1}^{\frac{n-1}{2}}\left\lfloor\dfrac{mi}{n}+\dfrac{1}{2}\right\rfloor=\left\lfloor\dfrac{m}{n}+\dfrac{1}{2}\right\rfloor+\left\lfloor\dfrac{2m}{n}+\dfrac{1}{2}\right\rfloor+\cdots+\left\lfloor\dfrac{m(n-1)}{2n}+\dfrac{1}{2}\right\rfloor$$

Then I can't it. Thank you for your help.

-
I've been able to show that the sum is the number of non-negative, integer solutions to $$mx+ny\lt\frac{(m-1)(n-1)}{2}$$ –  robjohn Nov 7 '13 at 13:27
Hello,what is $x,y?$ Thank you –  china math Nov 7 '13 at 13:37
non-negative integers –  robjohn Nov 7 '13 at 14:10
can you post you solution? Thank you –  china math Nov 7 '13 at 14:28
I haven't shown that this is even yet, just that it is the number of non-negative, integer solutions to that inequality. –  robjohn Nov 7 '13 at 15:53

Note $[x+\frac{1}{2}]=[2x]-[x]$

$$\sum_{i=1}^{\frac{n-1}{2}}\left\lfloor\dfrac{mi}{n}+\dfrac{1}{2}\right\rfloor=\sum_{i=1}^{\frac{n-1}{2}}(\left\lfloor2x\right\rfloor-\lfloor x\rfloor)\\=\sum_{i\ge \frac{n-1}{2},i\equiv0\pmod{2}}\left\lfloor x \right\rfloor-\sum_{i\le \frac{n-1}{2},i\equiv1\pmod{2}}\left\lfloor x \right\rfloor\\=\sum_{i\ge \frac{n-1}{2},i\equiv0\pmod{2}}\left\lfloor x \right\rfloor+\sum_{i\le \frac{n-1}{2},i\equiv1\pmod{2}}\left\lfloor -x+1 \right\rfloor \\ \equiv 2\sum_{i\ge \frac{n-1}{2},i\equiv0\pmod{2}}\left\lfloor x \right\rfloor \pmod{2}\\ \equiv0\pmod{2}$$

I hope you don't mind me trying to clarify what you have above: \begin{align} \sum_{i=1}^{\frac{n-1}{2}}\left\lfloor\frac{mi}{n}+\frac12\right\rfloor &=\sum_{i=1}^{\frac{n-1}{2}}\left\lfloor\frac{2mi}{n}\right\rfloor -\sum_{i=1}^{\frac{n-1}{2}}\left\lfloor\frac{mi}{n}\right\rfloor\\ &=\sum_{\substack{i=2\\i\text{ even}}}^{n-1}\left\lfloor\frac{mi}{n}\right\rfloor -\sum_{i=1}^{\frac{n-1}{2}}\left\lfloor\frac{mi}{n}\right\rfloor\\ &=\sum_{\substack{i\gt n/2\\i\text{ even}}}\left\lfloor\frac{mi}{n}\right\rfloor -\sum_{\substack{i\lt n/2\\i\text{ odd}}}\left\lfloor\frac{mi}{n}\right\rfloor\\ &=\sum_{\substack{i\gt n/2\\i\text{ even}}}\left\lfloor\frac{mi}{n}\right\rfloor -\sum_{\substack{i\gt n/2\\i\text{ even}}}\left\lfloor\frac{m(n-i)}{n}\right\rfloor\\ &=\sum_{\substack{i\gt n/2\\i\text{ even}}}\left\lfloor\frac{mi}{n}\right\rfloor -\sum_{\substack{i\gt n/2\\i\text{ even}}}\left\lfloor m-\frac{mi}{n}\right\rfloor\\ &=\sum_{\substack{i\gt n/2\\i\text{ even}}}\left\lfloor\frac{mi}{n}\right\rfloor -\sum_{\substack{i\gt n/2\\i\text{ even}}}\left(m-1-\left\lfloor\frac{mi}{n}\right\rfloor\right)\tag{\ast}\\ &=2\sum_{\substack{i\gt n/2\\i\text{ even}}}\left(\left\lfloor\frac{mi}{n}\right\rfloor-\frac{m-1}{2}\right) \end{align} $(\ast)$ is true as long as $\frac{mi}{n}\not\in\mathbb{Z}$.

-
In your fourth line, You seem to be using that $-\lfloor x\rfloor=\lfloor1-x\rfloor$ (but only when $x\not\in\mathbb{Z}$). However, that is only true when you have the same $x$ on both sides. Here, you don't. At least it is not clearly so since $x=mi/n$ and the $i$'s don't seem to match. Perhaps if you made the association more explicit (i.e. don't use $x$), things might be better. –  robjohn Nov 8 '13 at 18:03
With the latest edit, I think your proof is good :-) (+1) –  robjohn Nov 8 '13 at 18:53

This is not a full answer to the question, but a proof of a claim I made in a comment.

In Fig 1, hypotenuse of the half-sized triangle is the line $\frac mni+\frac12$.

$\hspace{2cm}$

The number of dots inside that triangle is the sum in question: $$\sum_{i=1}^{(n-1)/2}\left\lfloor\frac mni+\frac12\right\rfloor\tag{1}$$ If we scale that triangle to the full-sized triangle, we see that the dots inside the half-sized triangle correspond to the red dots in the full-sized triangle. Flipping the full-sized triangle from Fig 1 to Fig 2, we see that the red dots are the points with odd coordinates. Thus, the red dots represent the solutions in non-negative integers of $$m(2x+1)+n(2y+1)\lt mn\tag{2}$$ Since the left side of $(2)$ is even and the right side is odd, it is equivalent to $$m(2x+1)+n(2y+1)\lt mn+1\tag{3}$$ which is equivalent to $$mx+ny\lt\frac{(m-1)(n-1)}{2}\tag{4}$$ Therefore, the sum in $(1)$ counts the number of non-negative solutions of $(4)$.

-