1
$\begingroup$

Let $h$ and $k$ be two odd intergers and $(h,k)=1$. If $a=\frac{k-1}2$ and $b=\frac{h-1}2$, I want to prove algebraically

$$\sum_{r=1}^a\left\lfloor\frac{hr}k\right\rfloor+\sum_{r=1}^b\left\lfloor\frac{kr}h\right\rfloor=ab.$$

Of course, we can prove this by a geometric explanation. But I'm interested to know if there is an algebraic proof.

Here is my work. We can put $x=\frac hk=\lfloor x\rfloor+y$ where $0\le y<1$ and $h>k$. Then we can write

$$\sum_{r=1}^a\left\lfloor\frac{hr}k\right\rfloor=\sum_{r=1}^a\sum_{\ell =0}^{r-1}\left\lfloor\lfloor x\rfloor+y+\frac \ell r\right\rfloor =\sum_{r=1}^a\left(\sum_{\ell=0}^{m_r-1}\left\lfloor\lfloor x\rfloor+y+\frac \ell r\right\rfloor+\sum_{\ell=m_r}^{r-1}\left\lfloor\lfloor x\rfloor+y+\frac \ell r\right\rfloor\right)\\ =\sum_{r=1}^a(m_r\lfloor x\rfloor+(r-m_r)(\lfloor x\rfloor +1))=...=\frac{a(a+1)}2(\lfloor x\rfloor+1)-\sum_{r=1}^a\lceil r(1-y)\rceil$$

where $m_r$ is the first integer such that $y+\frac{m_r}r\ge1$, so in fact, $m_r=\lceil r(1-y)\rceil$.

Similarly,

$$\sum_{r=1}^b\left\lfloor\frac{kr}h\right\rfloor=\frac{b(b+1)}2-\sum_{r=1}^b\lceil r(1-y)\rceil.$$

But I think this can't be very helpful.

$\endgroup$
  • $\begingroup$ I'd suggest this book, page 68 "Floor Function and Integer Points", contains a proof of a more general result. But it's not available in the preview mode. $\endgroup$ – rtybase Jun 13 '18 at 21:44
  • $\begingroup$ @rtybase OK, but that doesn't seem to be algebraic! $\endgroup$ – user547800 Jun 14 '18 at 9:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.