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.

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.

share|improve this question
    
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

2 Answers 2

up vote 3 down vote accepted
+50

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

share|improve this answer
    
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}$enter image description here

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

share|improve this answer

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.