Understanding solution to: $\sum_{k=0}^{N-1}\sum_{m=0}^{N-1}x[m]e^{-\rm j\frac{2\pi}{N}mk}e^{-\rm j\frac{2\pi}{N}nk}$

Question

I cannot understand the solution that is presented below: \begin{eqnarray} X[k]&=&\sum_{m=0}^{N-1}x[m]e^{-\rm j\frac{2\pi}{N}mk}.\nonumber\\ y[n]&=&\sum_{k=0}^{N-1}X[k]e^{-\rm j\frac{2\pi}{N}nk}\nonumber\\ &=&\sum_{k=0}^{N-1}\sum_{m=0}^{N-1}x[m]e^{-\rm j\frac{2\pi}{N}mk}e^{-\rm j\frac{2\pi}{N}nk}\nonumber\\ &=&\sum_{m=0}^{N-1}x[m]\underbrace{\sum_{k=0}^{N-1}e^{-\rm j\frac{2\pi}{N}(m+n)k}}_{=\left\{\begin{array}{cc} N&m=-n,\\ 0&\text{ otherwise.}\end{array}\right.}\nonumber\\ &=&\left\{\begin{array}{cc} Nx[0]&n=0,\\ Nx[N-n]&\text{ otherwise.}\end{array}\right.\nonumber \end{eqnarray}

More specifically I know that:

$\sum_{k=0}^{N-1}e^{-j\frac{2\pi}{N}(m+n)k}$

is equal to:

$\frac{1- e^{-\rm j2\pi(m+n)}}{1 - e^{-\rm j\frac{2\pi}{N}(m+n)}}$

Now here it seems I have to know how $n$ and $m$ are related to $N$ to know the result. More specifically. If $n+m$ are multiples of $N$ then the sum above is $N$. For all other combinations of $m$ and $n$ the value is $0$. However even with this information I cannot understand the derivation above. In particular how can $m = -n$ when the $k, n, m$ are integers $>0$.

Appreciate any help.

Answer 1

When $m=-n$ the summation becomes $\sum _{k=1}^{k=N-1} (1) $, which is sum of N 1's. When $m\ne n$, and $m$ and $n$ are integers, the numerator of the result, $1-e^{-j2\pi(m+n)}$ becomes zero as $e^{-j2\pi(m+n)} = cos(2\pi(m+n))-j sin(2\pi(m+n)) = 1-j0$

[Edit] As per comments

the summation is a geometric progression, with ratio, $r=e^{-j\frac{2\pi}{N}(m+n)}$. The final result is the summation of this series

1. for $r \ne 1$, $sum = \frac{1-r^N}{1-r}$, which becomes zero as mentioned above
2. for $r = 1$, each term become 1, and so sum = N

for $n=0$, $Nx[0]$ is very obvious (m =-n = 0)

for $n \ne 0$, $r=1$, if $e^{-j\frac{2\pi}{N}(m+n)} = 1-j0$. This is possible is (m+n) mod N = 0, by which we get m = -n = N-n (since it is modulo computation). Alternately, we can say $0\le m,n \le N-1$, so $(m+n) mod N =0 \implies m=N-n$