6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$$ $\endgroup$ – robjohn Nov 7 '13 at 13:27
  • $\begingroup$ Hello,what is $x,y?$ Thank you $\endgroup$ – china math Nov 7 '13 at 13:37
  • $\begingroup$ non-negative integers $\endgroup$ – robjohn Nov 7 '13 at 14:10
  • $\begingroup$ can you post you solution? Thank you $\endgroup$ – china math Nov 7 '13 at 14:28
  • $\begingroup$ I haven't shown that this is even yet, just that it is the number of non-negative, integer solutions to that inequality. $\endgroup$ – robjohn Nov 7 '13 at 15:53
4
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – robjohn Nov 8 '13 at 18:03
  • $\begingroup$ With the latest edit, I think your proof is good :-) (+1) $\endgroup$ – robjohn Nov 8 '13 at 18:53
5
$\begingroup$

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

$\endgroup$

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.