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}$$
$$ \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.
