# Finite double sum $\sum_{k=0}^N\sum_{l=0}^M\left\lfloor\frac{k+l}{c}\right\rfloor$; any advanced summation technique?

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 ):

\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?

• Hello! Can you help me with this question? Commented Oct 7, 2019 at 10:22

Let $$S_n=\sum_{k=0}^{n-1}\left\lfloor \frac kc\right\rfloor$$ and $$T_n=\sum_{k=0}^{n-1}S_k.$$ Then we are looking for \begin{align}\sum_{k=0}^N\sum_{l=0}^M\left\lfloor\frac{k+l}{c}\right\rfloor &=\sum_{k=0}^N(S_{M+k+1}-S_k)\\ &=T_{N+M+2}-T_{M+1}-T_{N+1}\end{align} Note that for $$n=qc+r$$ with $$0\le r, we have $$S_n=c\sum_{k=0}^{q-1}k+rq=\frac c2{q(q-1)}+rq.$$ By the same trick, \begin{align}T_n&=\sum_{k=0}^{q-1}\left(\frac c2{k(k-1)}+\frac{k(k-1)}2k\right)+r\cdot\frac c2{q(q-1)} +\frac{r(r-1)}2q\\ &=\frac {cq(q-1)(q-2)}6+\frac{q(q-1)(q-2)(3q-1)}{12}+\frac{rq(cq-c+r-1)}2\end{align}