How can one simplify iterated sums $\sum\sum\dots$?

Question

Question. I am interested in whether there are methods to simplify a term with iterated $\sum$s in it where the range of one $\sum$-symbol may depend on a variables of the preceding $\sum$-symbols.

Example. In particular I am interested in this example: $$f(n)=\sum_{i=0}^{ \lfloor\frac{n}{3} \rfloor}\sum_{j=0}^{\lfloor \frac{n-3i}{2} \rfloor} 1.$$ How can one express $f(n)$ with a simpler formula, without the $\sum$-symbols and without the variables $i$ and $j$ occuring in it?

Answer 1

Note that $$f(n)=\sum_{i=0}^{ \lfloor\frac{n}{3} \rfloor}\sum_{j=0}^{\lfloor \frac{n-3i}{2} \rfloor} 1=\sum_{i=0}^{ \lfloor\frac{n}{3}\rfloor}\left(\lfloor \frac{n-3i}{2} \rfloor+1\right).$$ Now consider $n=6q+r$ with $r=0,1,2,3,4,5$. For example if $r=0$ then \begin{align*} f(n)&=\sum_{i=0}^{ 2q}\left(\lfloor \frac{6q-3i}{2} \rfloor+1\right)=\sum_{j=0}^{q}\left(\lfloor \frac{6q-3(2j)}{2} \rfloor+1\right)+\sum_{j=1}^{q}\left(\lfloor \frac{6q-3(2j-1)}{2} \rfloor+1\right)\\ &=\sum_{j=0}^{q}\left(3(q-j)+1\right)+\sum_{j=1}^{q}\left(3(q-j)+1) +1\right)=6\sum_{j=0}^{q}j+q+1-3q +2q\\ &=3q^2+3q+1. \end{align*}

Finally, you should verify that $$f(n)=\mbox{round}\left(\frac{(n+3)^2}{12}\right)\tag{1}$$ see the OEIS sequence A001399.

P.S. Note that for $n=6q$, formula (1) holds $$f(n)=\mbox{round}\left(\frac{(6q+3)^2}{12}\right)=\mbox{round}\left(3q^2+3q+3/4\right)=3q^2+3q+1.$$

Answer 2

I'll use your example, with $n=8$. (But I'll ignore your summand "1" because that makes an explicit sum trivial.)

The first sum has $i$ running $0$ to $2$. When $i=0$, $j$ runs $0$ to $4$. When $i=1$, $j$ runs $0$ to $2$. When $i=2$, $j$ runs $0$ to $1$. So visuzalise your $(i,j)$ plane:

4 |* 3 |* 2 |* * 1 |* * * 0 |* * * - + - - - | 0 1 2

So in the end here you have $10$ terms to sum. Their positioning in the $(i,j)$ plane is a little erratic, and this means you are in general unlikely to be able to simplify expressions like this if the summand is complicated. (Of course you can simplify it with a fixed $n$. But what I mean is for an unknown $n$, the positioning of the terms that contribute is not typically "regular" enough to give you a simplified formula in $n$.)

Sometimes you can make progress by reversing the order of summation. To do that, you still need the visualization above. Now $j$ would run first from $0$ to $4$. And you need $i$ to run from $0$ to some function $f$ of $j$ where $f(0)=2$, $f(1)=2$, $f(2)=1$, $f(3)=0$, and $f(4)=0$. It's not immediately clear how to write a formula for such a function here. But sometimes, with other double sums, it is clear how to do that.