Summation of the minimum of two options

Question

I am trying to figure out how to sum a minimum functions, i.e.

$$\sum_{i=0}^{\lfloor\frac{m}{2}\rfloor} \sum_{j=0}^{\lfloor\frac{n}{2}\rfloor} \min \Bigl( m - 2i, \lfloor\frac{n-2j}{2}\rfloor\Bigr)$$

and

$$\sum_{i=0}^{\lfloor\frac{m-1}{2}\rfloor} \sum_{j=0}^{\lfloor\frac{n-1}{2}\rfloor} \min \Bigl( m - 2i - 1, \lfloor\frac{n-2j-1}{2}\rfloor\Bigr)$$

And I have no idea how to do this sum without specifying $m$ and $n$. Are there any resources that offer a tutorial on doing this type of sum?

Thank you

Answer 1

We calculate the first sum with even $m$ and $n$. The other cases can be treated similarly.

The following is valid for non-negative even integers $m=2M, n=2N$. \begin{align*} &\sum_{i=0}^{\left\lfloor\frac{m}{2}\right\rfloor}\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\min\left\{m-2i,\left\lfloor\frac{n-2j}{2}\right\rfloor\right\}\\ &=\left\{ \begin{array}{lr} \frac{1}{6}M(M+1)(6N-4M+1)\qquad&\quad M\leq \left\lfloor\frac{N-1}{2}\right\rfloor\\\\ \frac{1}{6}M(M+1)(4M+5)\\ \quad+\frac{1}{3}\left\lfloor\frac{N-1}{2}\right\rfloor\left(\left\lfloor\frac{N-1}{2}\right\rfloor+1\right)\left(3N-4\left\lfloor\frac{N-1}{2}\right\rfloor-2\right)\qquad&\quad \left\lfloor\frac{N-1}{2}\right\rfloor<M\leq \left\lfloor\frac{N}{2}\right\rfloor\\\\ \frac{1}{6}\left\lfloor\frac{N}{2}\right\rfloor(\left\lfloor\frac{N}{2}\right\rfloor+1)(4\left\lfloor\frac{N}{2}\right\rfloor+5)\\ \quad+\left(M-\left\lfloor\frac{N}{2}\right\rfloor\right)\frac{1}{2}N(N+1)\\ \quad+\frac{1}{3}\left\lfloor\frac{N-1}{2}\right\rfloor\left(\left\lfloor\frac{N-1}{2}\right\rfloor+1\right)\left(3N-4\left\lfloor\frac{N-1}{2}\right\rfloor-2\right)\qquad&\quad M>\left\lfloor\frac{N}{2}\right\rfloor \end{array} \right. \end{align*}

We obtain

\begin{align*} \color{blue}{\sum_{i=0}^{\left\lfloor\frac{m}{2}\right\rfloor}}&\color{blue}{\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\min\left\{m-2i,\left\lfloor\frac{n-2j}{2}\right\rfloor\right\}}\\ &=\sum_{i=0}^M\sum_{j=0}^N\min\left\{2(M-i),N-j\right\}\tag{1}\\ &=\sum_{i=1}^M\sum_{j=1}^N\min\left\{2i,j\right\}\tag{2}\\ &=\sum_{i=1}^M\sum_{j=1}^{2i}j[[j\leq N]]+\sum_{i=1}^M\sum_{j=2i+1}^{N}2i\tag{3} \end{align*}

Comment:

• In (1) we substitute $m=2M$ and $n=2N$ and get rid of the floor symbols.

• In (2) we exchange the order of summation $i\to M-i, j\to N-j$ and we also let the indices start with $1$ since $i=0$ and $j=0$ does not contribute anything.

• In (3) we sum up the inner sum dependent on the index $i$ of the outer sum and use Iverson brackets $[[P]]$ to prevent overcounting.

We continue summing the left sum of (3) by splitting it into two cases and using power summation formulas.

• $M\leq \left\lfloor\frac{N}{2}\right\rfloor$

\begin{align*} \sum_{i=1}^M\sum_{j=1}^{2i}j[[j\leq N]]&=\sum_{i=1}^M\frac{1}{2}(2i)(2i+1)=\sum_{i=1}^M(2i^2+i)\\ &=2\cdot\frac{1}{6}M(M+1)(2M+1)+\frac{1}{2}M(M+1)\\ &=\frac{1}{6}M(M+1)(4M+5)\tag{4} \end{align*}

• $M> \left\lfloor\frac{N}{2}\right\rfloor$

  We split the left sum of (3) into two sums, use the result (4) and obtain

\begin{align*} \sum_{i=1}^M&\sum_{j=1}^{2i}j[[j\leq N]]\\ &=\sum_{i=1}^{\left\lfloor\frac{N}{2}\right\rfloor}\sum_{j=1}^{2i}j +\sum_{i={\left\lfloor\frac{N}{2}\right\rfloor}+1}^M\sum_{j=1}^Nj\\ &=\frac{1}{6}\left\lfloor\frac{N}{2}\right\rfloor\left(\left\lfloor\frac{N}{2}\right\rfloor+1\right)\left(4\left\lfloor\frac{N}{2}\right\rfloor+5\right) +\left(M-\left\lfloor\frac{N}{2}\right\rfloor\right)\frac{1}{2}N(N+1)\tag{5} \end{align*}

Next we calculate the right sum of (3) again by splitting it into two cases and using power summation formulas.

• $M\leq \left\lfloor\frac{N-1}{2}\right\rfloor$

\begin{align*} \sum_{i=1}^M\sum_{j=2i+1}^{N}2i&=\sum_{i=1}^M2i(N-2i)=2N\sum_{i=1}^Mi-4\sum_{i=1}^Mi^2\\ &=NM(M+1)-\frac{2}{3}M(M+1)(2M+1)\\ &=\frac{1}{3}M(M+1)(3N-4M-2)\tag{6} \end{align*}

• $M> \left\lfloor\frac{N-1}{2}\right\rfloor$

  We use the result (6) and obtain \begin{align*} \sum_{i=1}^M\sum_{j=2i+1}^{N}2i&=\sum_{i=1}^{\left\lfloor\frac{N-1}{2}\right\rfloor}\sum_{i=2i+1}^N2i\\ &=\frac{1}{3}\left\lfloor\frac{N-1}{2}\right\rfloor\left(\left\lfloor\frac{N-1}{2}\right\rfloor+1\right)\left(3N-4\left\lfloor\frac{N-1}{2}\right\rfloor-2\right)\tag{7} \end{align*}

Now it's time to harvest. We collect the results (4) to (7) and put them into the intermediate result (3).

• $M\leq \left\lfloor\frac{N-1}{2}\right\rfloor$

  We obtain from (4) and (6)

\begin{align*} \sum_{i=1}^M&\sum_{j=1}^{2i}j[[j\leq N]]+\sum_{i=1}^M\sum_{j=2i+1}^{N}2i\\ &=\frac{1}{6}M(M+1)(4M+5)+\frac{1}{3}M(M+1)(3N-4M-2)\\ &\,\,\color{blue}{=\frac{1}{6}M(M+1)(6N-4M+1)} \end{align*}

• $ \left\lfloor\frac{N-1}{2}\right\rfloor<M\leq \left\lfloor\frac{N}{2}\right\rfloor$

  We obtain from (4) and (7)

\begin{align*} \sum_{i=1}^M&\sum_{j=1}^{2i}j[[j\leq N]]+\sum_{i=1}^M\sum_{j=2i+1}^{N}2i\\ &\,\,\color{blue}{=\frac{1}{6}M(M+1)(4M+5)}\\ &\,\,\qquad\color{blue}{+\frac{1}{3}\left\lfloor\frac{N-1}{2}\right\rfloor\left(\left\lfloor\frac{N-1}{2}\right\rfloor+1\right)\left(3N-4\left\lfloor\frac{N-1}{2}\right\rfloor-2\right)} \end{align*}

• $M> \left\lfloor\frac{N}{2}\right\rfloor$

  We obtain from (5) and (7)

\begin{align*} \sum_{i=1}^M&\sum_{j=1}^{2i}j[[j\leq N]]+\sum_{i=1}^M\sum_{j=2i+1}^{N}2i\\ &\color{blue}{=\frac{1}{6}\left\lfloor\frac{N}{2}\right\rfloor\left(\left\lfloor\frac{N}{2}\right\rfloor+1\right)\left(4\left\lfloor\frac{N}{2}\right\rfloor+5\right) +\left(M-\left\lfloor\frac{N}{2}\right\rfloor\right)\frac{1}{2}N(N+1)}\\ &\qquad\,\,\color{blue}{+\frac{1}{3}\left\lfloor\frac{N-1}{2}\right\rfloor\left(\left\lfloor\frac{N-1}{2}\right\rfloor+1\right)\left(3N-4\left\lfloor\frac{N-1}{2}\right\rfloor-2\right)} \end{align*} and the claim follows.

Note: The results might be simplified by using \begin{align*} \left\lfloor\frac{N-1}{2}\right\rfloor=\left\lfloor\frac{N-1}{2}\right\rfloor\quad\Longleftrightarrow\quad N\equiv 1(2)\quad\Longleftrightarrow\quad n\equiv 2(4)\\ \left\lfloor\frac{N-1}{2}\right\rfloor+1=\left\lfloor\frac{N}{2}\right\rfloor\quad\Longleftrightarrow\quad N\equiv 0(2)\quad\Longleftrightarrow\quad n\equiv 0(4)\\ \end{align*}

Hint: Chapter 3 in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik contains a thorough introduction of floor and ceiling functions.