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.

Solution 1:

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.