# Prove of the Parseval's theorem for Discrete Fourier Transform (DFT)

If $x[k]$ and $X[r]$ are the pair of discrete time Fourier sequences, where $x[k]$ is the discrete time sequence and $X[r]$ is its corresponding DFT. Prove that the energy of the aperiodic sequence $x[k]$ of length $N$ can be expressed in terms of its $N$-point DFT as follows:

$$E_x=\sum_{k=0}^{N-1}|x[k]|^2=\frac{1}{N}\sum_{r}^{N-1}|X[r]|^2.$$

Could anyone one help me with this prove? Thanks.

-
Note that the DFT is an unitary transformation. – chaohuang Mar 31 '13 at 0:56
In the middle expression, replace one of the $x[k]$ by the weighted sum of $X[r]$'s as specified in the inverse DFT formula. Then, interchange order of summation. For details of this idea for Fourier transforms (where integrals instead of sums are involved), see this answer. – Dilip Sarwate Mar 31 '13 at 3:09

The proof is straightforward. Assume that $X$ and $x$ are related as follows:

$$X[r] = \sum_{k=0}^{N-1} x[k]\, e^{i 2 \pi k r /N}$$

Then

$$|X[r]|^2 = \sum_{k=0}^{N-1} x[k]\, \sum_{k'=0}^{N-1} x^*[k']\, e^{i 2 \pi (k-k') r /N}$$

and

\begin{align}\sum_{r=0}^{N-1}|X[r]|^2 &= \sum_{r=0}^{N-1} \sum_{k=0}^{N-1} x[k]\, \sum_{k'=0}^{N-1} x^*[k']\, e^{i 2 \pi (k-k') r /N} \\ &= \sum_{k=0}^{N-1} x[k]\, \sum_{k'=0}^{N-1} x^*[k']\, \sum_{r=0}^{N-1} e^{i 2 \pi (k-k') r /N} \end{align}

The inner sum is a geometric series and has the value

$$\sum_{r=0}^{N-1} e^{i 2 \pi (k-k') r /N} = \frac{e^{i 2 \pi (k-k')}-1}{e^{i 2 \pi (k-k')/N}-1}$$

Note that the RHS is zero unless $k=k'$; in that case, you should be able to see that the sum is simply $N$. We then write

$$\sum_{r=0}^{N-1} e^{i 2 \pi (k-k') r /N} = N \delta_{kk'}$$

where $\delta_{kk'}$ is $0$ when $k \ne k'$ and $1$ when $k=k'$. Therefore

$$\sum_{r=0}^{N-1}|X[r]|^2 = N \sum_{k=0}^{N-1} |x[k]|^2$$

and Parseval's theorem follows.

-
why $$|X[r]|^2 = \sum_{k=0}^{N-1} x[k]\, \sum_{k'=0}^{N-1} x^*[k']\, e^{i 2 \pi (k-k') r /(N-1)}$$, but not $$|X[r]|^2 = \sum_{k=0}^{N-1} x[k]\, \sum_{k'=0}^{N-1} x^*[k']\, e^{i 2 \pi (k+k') r /(N-1)}$$? Thanks. – Cheung Apr 2 '13 at 0:00
Because of the complex conjugation. – Ron Gordon Apr 2 '13 at 0:06
Thank you Ron. You help me a lot. – Cheung Apr 2 '13 at 0:53
Isn't the relationship $X[r]=\sum\limits_{k=0}^{N-1}x[k]e^{-i2\pi kr/N}$? – Alejandro May 10 at 6:31
@Alejandro: it doesn't matter. – Ron Gordon May 10 at 7:05