3
$\begingroup$

Let $M,N,c$ be positive integer. It was astonishing when trying to solve $\sum_{k=0}^N\sum_{l=0}^M\left\lfloor\frac{k+l}{c}\right\rfloor$ to obtain this rather complex looking result \begin{align*} \color{blue}{\sum_{k=0}^N}&\color{blue}{\sum_{l=0}^M\left\lfloor\frac{k+l}{c}\right\rfloor}\tag{1}\\ &=-\frac{1}{2}c(1-c)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{2c-2}{c}\right\rfloor\\ &\quad+\frac{1}{2}m(m+1)\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{c+m-1}{c}\right\rfloor +\frac{1}{2}n(n+1)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{c+n-1}{c}\right\rfloor\\ &\quad+\left(m+1-\frac{c}{2}\right)(n+1)\left\lfloor\frac{M}{c}\right\rfloor+\left(n+1-\frac{c}{2}\right)(m+1)\left\lfloor\frac{N}{c}\right\rfloor\\ &\quad+\frac{1}{2}(n+1)c\left\lfloor\frac{M}{c}\right\rfloor^2+\frac{1}{2}(m+1)c\left\lfloor\frac{N}{c}\right\rfloor^2\\ &\quad+c(m+n+2-c)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{N}{c}\right\rfloor\\ &\quad+\frac{1}{2}c^2\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{M}{c}\right\rfloor \left(\left\lfloor\frac{M}{c}\right\rfloor+\left\lfloor\frac{N}{c}\right\rfloor\right)\\ &\quad+\left(\frac{1}{2}((m+n)^2+3(m+n)+2)-\left(m+n+\frac{3}{2}\right)c+\frac{1}{2}c^2\right)\left\lfloor\frac{m+n}{c}\right\rfloor \end{align*}

Moreover what really baffled me was the long and cumbersome road to find this identity. In fact I needed to derive closed formulas for the three sums ($n,a,c$ integer $n\geq 0, c>0, 0\leq a <c$):

\begin{align*} &\sum_{k=0}^n\left\lfloor\frac{k+a}{c}\right\rfloor,\qquad\sum_{k=0}^n k\left\lfloor \frac{k+a}{c}\right\rfloor,\qquad\sum_{k=0}^n\left\lfloor\frac{k+a}{c}\right\rfloor^2\\ \end{align*}

and used these intermediate results to calculate (1) with tedious, lengthy calculations. You might have a look at this answer to see some steps.

Question: Do we have some other, maybe more advanced techniques to tackle (1) more efficiently than I did in the referred answer?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.