# Trying to understand a double summation formula

I am trying to understand a double summation mentioned in this paper: https://doi.org/10.1016/0024-3795(95)00696-6. How can we prove that this is true?

$$\sum_{l = 1}^n\;\; \sum_{k = l}^{n+l} = \sum_{k \,=\, 1}^n \;\; \sum_{l \,=\, 1}^{k} \,+\, \sum_{k \,=\, n+1}^{2n}\;\; \sum_{l \,=\, k-n}^{n}$$

• It helps to draw this: the summation on the left is over a parallelogram with corners at (1,1), (n+1, 1), (n, n), (2n, n). The first summation on the right is the right triangle with corners at (1,1), (n, 1), (n, n) and the second summation on the right is the other right triangle making up the parallelogram, vertices (n+1, 1), (n+1, n), (2n, n) Nov 16, 2020 at 19:48

$$\begin{array}{c} n=3 \\[8pt] \begin{array}{|c|c|ccccccc|c|} % {}_{\large\ell} \, \diagdown \, {}^{\large k} \hline & k & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \ell & (\ell,k)\\ \hline 1 & & (1,1) & (1,2) & (1,3) & (1,4) & & & & \sum_{k=1}^{n+1} \\ 2 & & & (2,2) & (2,3) & (2,4) & (2,5) & & & \sum_{k=2}^{n+2} \\ 3 & & & & (3,3) & (3,4) & (3,5) & (3,6) & & \sum_{k=3}^{n+3} \\ \hline & & \sum_{\ell=1}^1 & \sum_{\ell=1}^2 & \sum_{\ell=1}^3 & \sum_{\ell=4-3}^3 & \sum_{\ell=4-2}^3 & \sum_{\ell=4-1}^3 \\ \hline \end{array} \end{array}$$

One way to handle these changes of variables in a more formal way is to re-write the summation in terms of indicator variables on unrestricted sums, so that interchanging sums is as simple as switching the order. Then we need to manipulate the inequalities defining the indicators until we get the standard form of a sum.

Define $$1_P$$ to be $$1$$ when the proposition $$P$$ is true, otherwise $$0$$. If we're given variables $$a_{l,k}$$ with $$1 \leq l,k \leq 2n$$, we extend $$a_{l,k}$$ to be $$0$$ for $$l,k$$ outside of this range, and use $$\sum_l$$ to mean $$\sum_{l=-\infty}^\infty$$. Then we have

\begin{align*} \sum_{l = 1}^n\;\; \sum_{k = l}^{n+l} a_{l,k} &= \sum_l \sum_{k} 1_{1 \leq l \leq n, \, l \leq k \leq n+l} a_{l,k}\\ &= \sum_k \sum_{l} 1_{1 \leq l \leq n, \, l \leq k \leq n+l} a_{l,k}\\ &= \sum_{k=1}^{2n} \sum_{l} 1_{1 \leq l \leq n, \, l \leq k, k \leq n+l} a_{l,k}\\ &= \sum_{k=1}^{2n} \sum_{l} 1_{1 \leq l \leq n, \, l \leq k, k-n \leq l } a_{l,k}\\ &= \sum_{k=1}^{2n} \sum_{l} 1_{1 \leq l \leq n, \, k-n \leq l \leq k} a_{l,k}\\ &= \sum_{k=1}^{2n} \sum_{l=\max(k-n,1)}^{\min(k,n)} a_{l,k}\\ &= \sum_{k=1}^{n} \sum_{l=\max(k-n,1)}^{\min(k,n)} a_{l,k} + \sum_{k=n+1}^{2n} \sum_{l=\max(k-n,1)}^{\min(k,n)} a_{l,k} \\ &= \sum_{k=1}^{n} \sum_{l=1}^{k} a_{l,k} + \sum_{k=n+1}^{2n} \sum_{l=k-n}^{n} a_{l,k}. \\ \end{align*}

Here is another variation to show the identity for $$n\geq 1$$: \begin{align*} \sum_{l=1}^n\sum_{k=l}^{n+l}a_{k,l} =\sum_{k=1}^n\sum_{l=1}^ka_{k,l}+\sum_{k=n+1}^{2n}&\sum_{l=k-n}^na_{k,l}\tag{1} \end{align*}

We start with the right-hand side of (1) and consider at first the left sum.

We obtain \begin{align*} \sum_{k=1}^n\sum_{l=1}^ka_{k,l}=\sum_{\color{blue}{1\leq l\leq k\leq n}} a_{k,l}=\sum_{l=1}^n\sum_{k=l}^{n}a_{k,l}\tag{2} \end{align*}

In the middle of (2) we represent the index range of summation as inequality chain. This might help to better see the region of validity and how to exchange the sums.

Now the other sum. We obtain \begin{align*} \sum_{k=n+1}^{2n}&\sum_{l=k-n}^na_{k,l}\\ &=\sum_{k=1}^{n}\sum_{l=k}^na_{k+n,l} =\sum_{\color{blue}{1\leq k\leq l\leq n}} a_{k+n,l}=\sum_{l=1}^n\sum_{k=1}^la_{k+n,l}\tag{3}\\ &=\sum_{l=1}^n\sum_{k=n+1}^{n+l}a_{k,l}\tag{4} \end{align*}

Comment:

• In (3) we shift the index $$k$$ by $$n$$ to start with $$k=1$$. We are now in the same situation as in (2) and continue accordingly.

• In (4) we shift the index back.

Adding (2) and (4) gives \begin{align*} \sum_{l=1}^n\sum_{k=l}^{n}a_{k,l}+\sum_{l=1}^n\sum_{k=n+1}^{n+l}a_{k,l} \color{blue}{=\sum_{l=1}^n\sum_{k=l}^{n+l}a_{k,l}} \end{align*} and the claim (1) follows.