# 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.

## 1 Answer

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.