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.

enter image description here


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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.