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