Changing the order of summation and using a change of variables I'm looking at the below, and I don't understand how to get the second equality using the change of variables $m=k-l$. I've tried changing the order of summation to get $$\sum_{k=2^j+1}^{2^{j+1}}\sum_{l=2^j+1}^{k-1}=\sum_{l=2^j+1}^{2^{j+1}-1}\sum_{k=l+1}^{2^{j+1}}=\sum_{l=2^j+1}^{2^{j+1}-1}\sum_{m=1}^{2^{j+1}}$$which isn't the form given below. How can I get the summation given below? I would greatly appreciate some help.

 A: The double sum with a rectangle as index range is split into the diagonal part and (due to symmetry) twice a lower triangle part. We obtain a representation which has the form
\begin{align*}
\sum_{k=2^j+1}^{2^{j+1}}\sum_{l=2^j+1}^{2^{j+1}}a_kb_l
&=\sum_{k=2^j+1}^{2^{j+1}}a_kb_k+2\sum_{\color{blue}{k=2^j+2}}^{2^{j+1}}\sum_{l=2^j+1}^{k-1}a_kb_l\\
\end{align*}
Note we start the double sum with $k=2^j+2$, since the diagonal entries are no longer part of it. This implies that
\begin{align*}
\sum_{k=2^j+1}^{2^{j+1}}\sum_{l=2^j+1}^{k-1}\frac{e^{ik\pi t} e^{-i l\pi t}}{kl}G_kG_l
=\sum_{\color{blue}{k=2^j+2}}^{2^{j+1}}\sum_{l=2^j+1}^{k-1}\frac{e^{ik\pi t} e^{-i l\pi t}}{kl}G_kG_l
\end{align*}
since the summand with $k=2^j+1$ has an empty inner sum which is zero.

We  obtain
  \begin{align*}
\color{blue}{\sum_{k=2^j+1}^{2^{j+1}}\sum_{l=2^j+1}^{k-1}a_kb_l}&=\sum_{k=2^j+2}^{2^{j+1}}\sum_{l=2^j+1}^{k-1}a_kb_l\\
&=\sum_{l=2^j+1}^{2^{j+1}-1}\sum_{k=l+1}^{2^{j+1}}a_kb_l\tag{1}\\
&=\sum_{l=2^j+1}^{2^{j+1}-1}\sum_{m=1}^{2^{j+1}-l}a_{m+l}b_l\tag{2}\\
&\color{blue}{=\sum_{m=1}^{2^j-1}\sum_{l=2^j+1}^{2^{j+1}-m}a_{m+l}b_l}\tag{3}\\
\end{align*}
  in accordance with the calculation in OPs post.

Comment:


*

*In (1) we exchange the sums respecting $2^j+1\leq l < k\leq 2^{j+1}$.

*In (2) we substitute $m=k-l$, which means the lower limit as well as the upper limit of the inner sum is reduced by $l$.

*In (3) we exchange the sums again. We also change the order of summation of the inner sum, since the lower limit has to be less or equal the upper limit.
