Double sum over $\left\lfloor{ac+bd\over k}\right\rfloor$

Question

We have $$\left\lfloor{ac+bd\over k}\right\rfloor-\left\lfloor{ac+bd-1\over k}\right\rfloor=1-\left\lceil{ (ac+bd)\mod{k}\over k}\right\rceil$$ for $a,b,c,d,k$ - integers, $a\geqslant0$, $b\geqslant0$, $c>0$, $d>0$, $k>0$. Next we want to calculate $$\sum\limits_{a=0}^{n}\sum\limits_{b=0}^{m}\left\lfloor{ac+bd\over k}\right\rfloor$$ or $$\sum\limits_{a=0}^{n}\sum\limits_{b=0}^{m}\left\lceil{(ac+bd)\mod{k}\over k}\right\rceil$$ Is there a nice closed form for it?

Answer 1

Here we give a closed form expression for a special case of the double sum indicating that there is no nice formula in the general case.

Let $N, M, c$ be positive integer with \begin{align*} N=&c\left\lfloor\frac{N}{c}\right\rfloor+n\qquad 0\leq n<c\\ M=&c\left\lfloor\frac{M}{c}\right\rfloor+m\qquad 0\leq m<c \end{align*} then the following is valid \begin{align*} \sum_{k=0}^N&\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}{2}\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\tag{2} \end{align*}

We observe the special case $\left\lfloor\frac{ak+bl}{c}\right\rfloor$ in (1) with $a=b=1$ results in a rather complex formula (2) indicating the general case is also rather complex.

In order to prove (2) we need some preliminary results, namely three types of single sums with floor functions given below.

Let $n,a,c$ be integer $n\geq 0, c>0, 0\leq a <c$.

The following is valid

\begin{align*} \sum_{k=0}^n\left\lfloor\frac{k+a}{c}\right\rfloor &=\left(n+1+a-\frac{c}{2}\right)\left\lfloor\frac{n+a}{c}\right\rfloor-\frac{c}{2}\left\lfloor\frac{n+a}{c}\right\rfloor^2\tag{3}\\ \sum_{k=0}^n k\left\lfloor \frac{k+a}{c}\right\rfloor &=\frac{1}{12}\left(6n(n+1)-6a^2+6a(c-1)-c^2+3c\right)\left\lfloor\frac{n+a}{c}\right\rfloor\\ &\qquad+\frac{c}{4}(2a-c+1)\left\lfloor\frac{n+a}{c}\right\rfloor^2-\frac{c^2}{6}\left\lfloor\frac{n+a}{c}\right\rfloor^3\tag{4}\\ \sum_{k=0}^n\left\lfloor\frac{k+a}{c}\right\rfloor^2 &=\frac{c}{6}\left\lfloor\frac{n+a}{c}\right\rfloor+\left(n+1+a-\frac{c}{2}\right)\left\lfloor\frac{n+a}{c}\right\rfloor^2-\frac{2c}{3}\left\lfloor\frac{n+a}{c}\right\rfloor^3\tag{5} \end{align*}

Ad (3):

Let $n,a,c$ integer $n\geq 0, c>0, 0\leq a <c$. We obtain

\begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{\left\lfloor\frac{k+a}{c}\right\rfloor}\\ &=\sum_{k=0}^n\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[j=\left\lfloor\frac{k+a}{c}\right\rfloor\right]\tag{6}\\ &=\sum_{k=0}^n\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[ j\leq \frac{k+a}{c} < j+1\right]\\ &=\sum_{k=0}^n\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[ cj-a\leq k < c(j+1)-a\right]\\ &=\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j\sum_{k=cj-a}^{c(j+1)-a-1}1 +\left\lfloor\frac{n+a}{c}\right\rfloor\sum_{k=c\left\lfloor\frac{n+a}{c}\right\rfloor-a}^n 1\\ &=c\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j+\left\lfloor\frac{n+a}{c}\right\rfloor\left(n-c\left\lfloor\frac{n+a}{c}\right\rfloor+a+1\right)\\ &=\frac{c}{2}\left(\left\lfloor\frac{n+a}{c}\right\rfloor-1\right)\left\lfloor\frac{n+a}{c}\right\rfloor+\left\lfloor\frac{n+a}{c}\right\rfloor\left(n-c\left\lfloor\frac{n+a}{c}\right\rfloor+a+1\right)\\ &\,\,\color{blue}{=\left(n+a+1-\frac{c}{2}\right)\left\lfloor\frac{n+a}{c}\right\rfloor-\frac{c}{2}\left\lfloor\frac{n+a}{c}\right\rfloor^2} \end{align*}

and (3) follows.

Comment:

• In (6) we use Iverson brackets to get rid of the floor function.

Ad (4):

Let $n,a,c$ integer $n\geq 0, c>0, 0\leq a <c$. We obtain

\begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{k\left\lfloor\frac{k+a}{c}\right\rfloor}\\ &=\sum_{k=0}^nk\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[j=\left\lfloor\frac{k+a}{c}\right\rfloor\right]\\ &=\sum_{k=0}^nk\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[ j\leq \frac{k+a}{c} < j+1\right]\\ &=\sum_{k=0}^nk\sum_{j=1}^{\left\lfloor\frac{k+a}{c}\right\rfloor} j\left[ cj-a\leq k < c(j+1)-a\right]\\ &=\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j\sum_{k=cj-a}^{c(j+1)-a-1}k +\left\lfloor\frac{n+a}{c}\right\rfloor\sum_{k=c\left\lfloor\frac{n+a}{c}\right\rfloor-a}^n k\\ &=\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j\left(\frac{1}{2}\left(c(j+1)-a-1\right)(c(j+1)-a)-\frac{1}{2}\left(cj-a-1\right)(cj-a)\right)\\ &\qquad+\left\lfloor\frac{n+a}{c}\right\rfloor\left(\binom{n+1}{2}-\binom{c\left\lfloor\frac{n+a}{c}\right\rfloor-a}{2}\right)\\ &=\frac{1}{2}\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j(-2ac+2c^2j+c^2-c) +\left\lfloor\frac{n+a}{c}\right\rfloor\left(\binom{n+1}{2}-\binom{c\left\lfloor\frac{n+a}{c}\right\rfloor-a}{2}\right)\\ &=c^2\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j^2+\left(\frac{c^2-c}{2}-ac\right)\sum_{j=1}^{\left\lfloor\frac{n+a}{c}\right\rfloor-1}j +\left\lfloor\frac{n+a}{c}\right\rfloor\left(\binom{n+1}{2}-\binom{c\left\lfloor\frac{n+a}{c}\right\rfloor-a}{2}\right)\\ &=\frac{c^2}{6}\left(\left\lfloor\frac{n+a}{c}\right\rfloor-1\right)\left\lfloor\frac{n+a}{c}\right\rfloor\left(2\left\lfloor\frac{n+a}{c}\right\rfloor-1\right)\\ &\qquad+\frac{c}{4}(c-1-2a)\left(\left\lfloor\frac{n+a}{c}\right\rfloor-1\right)\left\lfloor\frac{n+a}{c}\right\rfloor\\ &\qquad+\frac{1}{2}\left(n(n+1)-\left(c\left\lfloor\frac{n+a}{c}\right\rfloor-a\right)\left(c\left\lfloor\frac{n+a}{c}\right\rfloor-a-1\right)\right)\left\lfloor\frac{n+a}{c}\right\rfloor\\ &\,\,\color{blue}{=\frac{1}{12}\left(6n(n+1)-6a^2+6a(c-1)-c^2+3c\right)\left\lfloor\frac{n+a}{c}\right\rfloor}\\ &\qquad\color{blue}{+\frac{c}{4}(2a-c+1)\left\lfloor\frac{n+a}{c}\right\rfloor^2-\frac{c^2}{6}\left\lfloor\frac{n+a}{c}\right\rfloor^3} \end{align*}

and (4) follows.

Ad (5):

The proof of this case is similar to (3) and is omitted.

The main formula (2):

The proof of formula (2) is really cumbersome and somewhat lengthy. Here I will show the first steps and everything else follows by consequently applying (3) to (5).

We obtain \begin{align*} \color{blue}{\sum_{k=0}^N}&\color{blue}{\sum_{l=0}^M\left\lfloor\frac{k+l}{c}\right\rfloor}\\ &=\sum_{k=0}^{c\left\lfloor\frac{N}{c}\right\rfloor+n}\ \sum_{l=0}^{c\left\lfloor\frac{M}{c}\right\rfloor+m}\left\lfloor\frac{k+l}{c}\right\rfloor\\ &=\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}\ \sum_{k_2=0}^{c-1}\ \sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}\ \sum_{l_2=0}^{c-1} \left\lfloor\frac{ck_1+k_2+cl_1+l_2}{c}\right\rfloor\\ &\qquad+\sum_{k_2=0}^n\ \sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}\ \sum_{l_2=0}^{c-1} \left\lfloor\frac{c\left\lfloor\frac{N}{c}\right\rfloor+k_2+cl_1+l_2}{c}\right\rfloor\\ &\qquad+\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}\ \sum_{k_2=0}^{c-1}\ \sum_{l_2=0}^{m} \left\lfloor\frac{ck_1+k_2+c\left\lfloor\frac{M}{c}\right\rfloor+l_2}{c}\right\rfloor\\ &\qquad+\sum_{k_2=0}^n\sum_{l2=0}^n\left\lfloor\frac{c\left\lfloor\frac{N}{c}\right\rfloor+k_2+c\left\lfloor\frac{M}{c}\right\rfloor+l_2}{c}\right\rfloor\\ &=\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}\ \sum_{k_2=0}^{c-1}\ \sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}\ \sum_{l_2=0}^{c-1} \left(\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+k_1+l_1\right)\\ &\qquad+\sum_{k_2=0}^n\ \sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}\ \sum_{l_2=0}^{c-1} \left(\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+\left\lfloor\frac{N}{c}\right\rfloor+l_1\right)\\ &\qquad+\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}\ \sum_{k_2=0}^{c-1}\ \sum_{l_2=0}^{m} \left(\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+k_1+\left\lfloor\frac{M}{c}\right\rfloor\right)\\ &\qquad+\sum_{k_2=0}^n\sum_{l2=0}^n\left(\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+\left\lfloor\frac{N}{c}\right\rfloor+\left\lfloor\frac{M}{c}\right\rfloor\right)\\ &=\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{M}{c}\right\rfloor\sum_{k_2=0}^{c-1}\sum_{l_2=0}^{c-1}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor +c^2\left\lfloor\frac{M}{c}\right\rfloor\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}k_1 +c^2\left\lfloor\frac{N}{c}\right\rfloor\sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}l_1\\ &\qquad+\left\lfloor\frac{M}{c}\right\rfloor\sum_{k_2=0}^n\sum_{l_2=0}^{c-1}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor +(n+1)\left\lfloor\frac{M}{c}\right\rfloor c\left\lfloor\frac{N}{c}\right\rfloor +(n+1)c\sum_{l_1=0}^{\left\lfloor\frac{M}{c}\right\rfloor-1}l_1\\ &\qquad+\left\lfloor\frac{N}{c}\right\rfloor\sum_{k_2=0}^{c-1}\sum_{l_2=0}^{m}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor +\left\lfloor\frac{N}{c}\right\rfloor c (m+1)\left\lfloor\frac{M}{c}\right\rfloor +c(m+1)\sum_{k_1=0}^{\left\lfloor\frac{N}{c}\right\rfloor-1}k_1\\ &\qquad+\sum_{k_2=0}^{n}\sum_{l_2=0}^m\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+(n+1)(m+1)\left(\left\lfloor\frac{N}{c}\right\rfloor+\left\lfloor\frac{M}{c}\right\rfloor\right)\\ \end{align*} \begin{align*} &=\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{M}{c}\right\rfloor\sum_{k_2=0}^{c-1}\sum_{l_2=0}^{c-1}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor\\ &\qquad\qquad+c^2\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{N}{c}\right\rfloor\left(\left\lfloor\frac{N}{c}\right\rfloor-1\right) +c^2\left\lfloor\frac{N}{c}\right\rfloor\left\lfloor\frac{M}{c}\right\rfloor\left(\left\lfloor\frac{M}{c}\right\rfloor-1\right)\\ &\qquad+\left\lfloor\frac{M}{c}\right\rfloor\sum_{k_2=0}^n\sum_{l_2=0}^{c-1}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor\\ &\qquad\qquad+(n+1)\left\lfloor\frac{M}{c}\right\rfloor c\left\lfloor\frac{N}{c}\right\rfloor+(n+1)c\left\lfloor\frac{M}{c}\right\rfloor\left(\left\lfloor\frac{M}{c}\right\rfloor-1\right)\\ &\qquad+\left\lfloor\frac{N}{c}\right\rfloor\sum_{k_2=0}^{c-1}\sum_{l_2=0}^{m}\left\lfloor\frac{k_2+l_2}{c}\right\rfloor\\ &\qquad\qquad+\left\lfloor\frac{N}{c}\right\rfloor c (m+1)\left\lfloor\frac{M}{c}\right\rfloor +c(m+1)\left\lfloor\frac{N}{c}\right\rfloor\left(\left\lfloor\frac{N}{c}\right\rfloor-1\right)\\ &\qquad+\sum_{k_2=0}^{n}\sum_{l_2=0}^m\left\lfloor\frac{k_2+l_2}{c}\right\rfloor+(n+1)(m+1)\left(\left\lfloor\frac{N}{c}\right\rfloor+\left\lfloor\frac{M}{c}\right\rfloor\right)\tag{7}\\ \\ &=\cdots\tag{8}\\ \\ &\,\,\color{blue}{=-\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}{2}\right\rfloor}\\ &\quad\color{blue}{+\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\color{blue}{+\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\color{blue}{+\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\color{blue}{+c(m+n+2-c)\left\lfloor\frac{M}{c}\right\rfloor\left\lfloor\frac{N}{c}\right\rfloor}\\ &\quad\color{blue}{+\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\color{blue}{+\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*}

Note: I've checked the formula programmatically for small values of $M,N$ and $c$.

There are in fact some steps which are needed to fill in (8), since we have double sums in (7) which have to be substituted iteratively by (3) to (5). So, the steps up to (7) are rather the beginning of the main calculation.