Change of variables on a double summation to yield a single sum

Question

I'm going through a proof in Monson's Statistical Digital Signal Processing and Modelling on page 98. They used the substitution $k=n-m$ in order to change the double summation into a single summation. I was hoping someone could show the steps in going from one step to the next.

$$\sum_{n=-N}^N\sum_{m=-N}^N r_x(n-m)e^{-j\omega (n-m)}=\sum_{k=-2N}^{2N} (2N+1-|k|)r_x(k)e^{-j\omega (k)}$$

I already asked my professor who said to look at the values of $n$ in $(-N,N)$ that makes $m=n-k$ fall outside the interval $(-N,N)$ for different values of $k=-2N,...2N$. Although that might be helpful for him to rationalize the step, it is not rigorous and lacks anyway of doing it again without reverse engineering it. I would really be grateful for any guidance here.

Answer 1

But it is rigorous, just tedious. Unfortunately, the standard notation that makes this explicit gives square brackets two different meanings. With $[a]b$ denoting the coefficienf of $a$ in $b$ and $[p]$ denoting the truth-value as an integer of a proposition $p$, each $k$ from $-2N$ to $2N$ inclusive satisfies$$\begin{align}\left[r_x(k)e^{-j\omega(k)}\right]\left[\sum_{mn}r_x(n-m)e^{-j\omega(n-m)}\right]&=\sum_{mn}[n-m=k]\\&=\sum_m[-N-k\le m\le N-k]\\&=\min\{N-k,\,N\}-\max\{-N-k,\,-N\}+1\\&=2N+1-|k|.\end{align}$$In particular, the last $=$ is trivial for $k=0$, and switching to any nonzero $k$ will reduce the $\min$ by $|k|$ if $k>0$ or increase the $\max$ by $|k|$ if $k<0$.

Answer 2

There is a fairly straightforward way to think about the answer to this question. The motivation for thinking you should be able to collapse the double sum into a single sum is the observation that the summand (call it $f(n-m)=f(k)$) depends only on the difference $k=n-m$, so shouldn't we able to write it as a single sum over the possible values of $k$?

The answer is yes, but we have to be a little bit careful how we do that. With $n\in\{-N,\ldots,N\}$ and similarly for $m$, $k\in\{-2N,\ldots,2N\}$. However, the key observation is that there are more possible pairs $(n,m)$ than there are individual values of $k$ (viz. $(2N+1)^2$ vs. $4N+1$), or in other words, different pairings of $n$ and $m$ yield the same $k=n-m$. Therefore, each term $f(k)$ in the sum over $k$ comes with a multiplicity $m(k)$ that counts how many ways we can make each $k$ out of different pairs $(n,m)$ in the original sum. The value of $m(k)$ depends on the limits of the original sums over $n$ and $m$, but in this case (both limits from $-N$ to $N$), $m(k)=2N+1-|k|$. Therefore, $$ \sum_{n=-N}^N\sum_{m=-N}^N f(n-m) = \sum_{k=-2N}^{2N} m(k)\cdot f(k) = \sum_{k=-2N}^{2N} (2N+1-|k|)\,f(k) ~.$$

So why is $m(k)=2N+1-|k|$? There are fancier ways to derive this, but the most straightforward is to make a table of values of $k$ for pairs $(n,m)$. From the table it's quite clear that there are $2N+1$ ways to make $k=0$: $N$ ways for $n=m=1,\ldots,N$, then $N$ more ways for $n=m=-1,\ldots,-N$, and one more way with $n=m=0$. Then observe that since $n=k+m$ there's one fewer way to make $k=1$ because $n$ has to be 1 bigger than $m$, so you lose any pairing with the smallest $n$ (here $n=-N$) or the largest $m$ (here $m=N$). Similarly, there are two fewer ways to make $k=2$, three fewer ways to make $k=3$, and so on (and similarly for $k<0$). And that's it.

Another way to visualize the counting is to picture the possible values of $n$ as dots on a number line, and similarly for $m$. If you "stack" the row of $n$ dots above the row of $m$ dots, the value of $k$ is then just the difference of the two rows. The vertical pairings that give you $k=0$ are the ones where the two rows are aligned, from which it is clear that there are as many such pairings as there are individual values of $n$ or $m$. The pairings that give you $k=1$ are those for which the $m$ row is shifted one unit to the right so each value of $m$ is paired with $n=m+1$ directly above it, and thus there's one fewer pairing between $n$ and $m$ that gives $k=1$ ... and so on.

Once you see why it works, it's fine to get fancy, but sometimes it's good to take it down to basics. We're counting stuff.