Closed Formula for Double Summation

Question

Problem

Fill in the missing parts:

$$\sum_{k=1}^b \sum_{i=1}^a i - k = \sum_{i=?}^? \sum_{j=?}^? ?$$

where j = i - k and the integers a > 1 and b > 1.

Solution

I came up with the following solution:

$$\sum_{i=1}^b \sum_{j=1-i}^{a-i} j$$

based on the following argument:

$$\sum_{k=1}^b \sum_{i=1}^a i - k = (1-1) + (2-1) + ... + (a - 1)$$ $$ + (1-2) + (2-2) + ... + (a-2)$$ $$ + ... +$$ $$ + (1-b) + (2-b) + ... + (a-b)$$

Letting each row be its own sum, we find:

$$ = \sum_{j=1-1}^{a-1} j + \sum_{j=1-2}^{a-2} j + ... + \sum_{j=1-b}^{a-b} j$$ $$ = \sum_{i=1}^b \sum_{j=1-i}^{a-i} j$$

However, the professor summed up the columns instead of the rows and found this solution:

$$\sum_{i=1}^a \sum_{j=i-b}^{i-1} j$$

I have been given the opportunity to prove my result is also correct, but I need to provide the closed formula for both results and show they are equivalent. However, I am stuck. In particular, I do not know how to find the closed formula for the following summation:

$$\sum_{j=i-b}^{i-1} j$$

My intuition is telling me the formula changes depending on the relation between i and b. If i > b, then I find the following formula:

$$\sum_{j=1}^{i-1} j - \sum_{j=1}^{i-b-1} j = \frac{(i-1)i}{2} - \sum_{j=1}^{i-b-1} j$$

However, if i < b, then the subtracted sum changes to:

$$\sum_{j=1}^{b-i} j$$

Is my intuition correct? Am I heading in the right direction? My gut is telling me that solving the double summation closed formula will be very tricky if the inner summation has multiple cases.

Thanks for the help.

Answer 1

We show the following is valid for integers $a>1$, $b>1$: \begin{align*} \color{blue}{\sum_{i=1}^a\sum_{j=i-b}^{i-1}j=\sum_{i=1}^b\sum_{j=1-i}^{a-i}j} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{i=1}^a\sum_{j=i-b}^{i-1}j}&=\sum_{i=1}^a\sum_{j=-b}^{-1}(j+i)\tag{1}\\ &=\sum_{i=1}^{a}\sum_{j=1}^b(i-j)\tag{2}\\ &=\sum_{j=1}^b\sum_{i=1}^a(i-j)\tag{3}\\ &=\sum_{i=1}^b\sum_{j=1}^a(j-i)\tag{4}\\ &\,\,\color{blue}{=\sum_{i=1}^b\sum_{j=1-i}^{a-i}j}\tag{5} \end{align*} and the claim follows.

Comment:

• In (1) we decrease the index $j$ by $i$ and compensate this by adding $i$ to the summand.

• In (2) we change the index region of the inner sum from $-b\leq j\leq -1$ to $1\leq j\leq b$ and compensate this by substituting $j$ by $-j$ in the summand.

• In (3) we exchange the sums.

• In (4) we change the notation of the indices: $j\to i$ and $i\to j$.

• In (5) we subtract $i$ from the index $j$ and compensate this by adding $i$ to the summand.

Answer 2

The $(k,i)$ sum is over a rectangle and the resummation replaces one of the variables by a value $j=i-k$ that is constant along the diagonal. Assuming $a\ge 1$ and $b\ge 1$: $$ \sum_{i=1}^a\sum_{k=1}^b j = \sum_{i=1}^a \sum_{i-j=1}^{i-j=b} j = \sum_{i=1}^a \sum_{j=i-1}^{j=i-b} j = \sum_{i=1}^a \sum_{j=i-b}^{j=i-1} j = \sum_{i=1}^a \frac{b(2i-1-b)}{2} = \frac{ab(a-b)}{2}. $$ Sums of the type $\sum_{j=...}^{...}j$ are evaluated with https://en.wikipedia.org/wiki/Faulhaber%27s_formula