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

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.

• 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. – rtybase Jun 13 '18 at 21:44
• @rtybase OK, but that doesn't seem to be algebraic! – user547800 Jun 14 '18 at 9:33