Discrete Parseval's theorem I am currently trying to verify whether my DFT algorithm produces the correct results through the discrete version of Parseval's theorem given by:
$$
\sum_{n=0}^{N-1} |x_n|^2 = \frac{1}{N}\sum_{k=0}^{N-1}|\hat x_k|^2
$$
where $x_n$ is a real space set of points, and $\hat x_k$ is the corresponding Fourier transform. However, I could not understand how the two are equal. The left hand side seems to be an arbitrarily large summation for some general function $x_n$. But the right hand side converge to a mean value due to the $1/N$ factor. Could anyone please explain why the two are equal?
 A: First note that
\begin{equation}
(1)\hspace{5em}\sum_{k=0}^{N-1}e^\frac{2\pi ijk}{N}=\cases{N&if $\ j=0$\\
0&otherwise}
\end{equation}
Presuming that your definition of $\ \hat{x}_k\ $ is
$$
\hat{x}_k=\sum_{n=0}^{N-1}e^{-\frac{2\pi ink}{N}}x_n\ ,
$$
then
\begin{align}
\sum_{k=0}^{N-1}\big|\hat{x}_k\big|^2&=\sum_{k=0}^{N-1}\hat{x}_k\overline{\hat{x}}_k\\
&=\sum_{k=0}^{N-1}\sum_{n=0}^{N-1}e^{-\frac{2\pi ink}{N}}x_n\sum_{r=0}^{N-1}e^\frac{2\pi irk}{N}\overline{x}_r\\
&=\sum_{k=0}^{N-1}\sum_{n=0}^{N-1}\sum_{r=0}^{N-1}e^\frac{2\pi i(r-n)k}{N}x_n\overline{x}_r\\
&=\sum_{k=0}^{N-1}\sum_{n=0}^{N-1}x_n\sum_{j=-n}^{N-1-n}e^\frac{2\pi ijk}{N}\overline{x}_{n+j}\\
&=\sum_{n=0}^{N-1}x_n\sum_{j=-n}^{N-1-n}\overline{x}_{n+j}\sum_{k=0}^{N-1}e^\frac{2\pi ijk}{N}\ .
\end{align}
Now applying equation $(1)$ to the two rightmost sums gives
$$
\sum_{j=-n}^{N-1-n}\overline{x}_{n+j}\sum_{k=0}^{N-1}e^\frac{2\pi ijk}{N}=N\overline{x}_n\ ,
$$
and substituting this back into the final expression gives
\begin{align}
\sum_{k=0}^{N-1}\big|\hat{x}_k\big|^2&=N\sum_{n=0}^{N-1}x_n\overline{x}_n\\
&=N\sum_{n=0}^{N-1}\big|x_n\big|^2\ ,
\end{align}
which is (equivalent to) the equation you're trying to prove.
