4

When, for arbitrary positive integers $m$ and $n$, is the following sum equal to $0$?

$$ \sum_{i=0}^{mn-1} (-1)^{\lfloor i/m \rfloor +\lfloor i/n\rfloor} $$

John Gowers
  • 24,959
arshajii
  • 782
  • Each term is either $-1$ or $1$. So if $mn$ were odd you are adding either an even number of copies of $1$ with an odd number of copies of $-1$ or vice versa. That would preclude a sum of $0$. – 2'5 9'2 May 19 '13 at 07:16
  • Here's a thought. Take $m=1$, find the first few $n$ that give zero, see whether there is a pattern (or whether the sequence of $n$-values is in the Online Encyclopedia of Integer Sequences). If not, that suggests you've got a hard problem here. If you can do the $m=1$ case, you may see how to do other cases. – Gerry Myerson May 19 '13 at 07:56
  • @alex.jordan Thanks. Further evidence that availability of computers makes some people unable to count to 2 (namely, me). – 75064 May 19 '13 at 19:33

1 Answers1

7

The sum is $0$ if and only if $m$ and $n$ contain different numbers of factors of $2$.

If neither contains a factor of $2$, the number of summands is odd, so the sum can't be $0$.

If both contain a factor of $2$, let $m=2k$ and $n=2l$, and $i=2kla+2b+c$ with $a,c\in\{0,1\}$ and $0\le b\lt kl$. Then

$$ \left\lfloor\frac im\right\rfloor=\left\lfloor\frac{2kla+2b+c}{2k}\right\rfloor=2la+\left\lfloor\frac bk\right\rfloor $$

and likewise

$$ \left\lfloor\frac in\right\rfloor=\left\lfloor\frac{2kla+2b+c}{2l}\right\rfloor=2ka+\left\lfloor\frac bl\right\rfloor\;, $$

so we just get $4$ times the contributions for the case $k,l$ for the $4$ different pairs of values of $a$ and $c$.

Thus, by induction we can divide out common factors of $2$. That leaves the case where one of $m$ and $n$ is even and the other is odd. In this case $i\to mn-1-i$ flips the parity of the exponent, and thus the sign of the summand, so the sum is $0$.

joriki
  • 238,052