# About the proof of an equality related to the DFT [sampling the DTFT to obtain the DFT]

This wiki page about the DTFT says that the DFT can be obtained from the DTFT by sampling the latter in one cycle at $$N$$ points:

When the DTFT is continuous, a common practice is to compute an arbitrary number of samples ($${{N}}$$) of one cycle of the periodic function ($${X_{1/T}}$$):\begin{align} \underbrace{X_{1/T}\left(\frac{k}{NT}\right)}_{X_k} &= \sum_{n=-\infty}^\infty x[n]\cdot e^{-i 2\pi \frac{kn}{N}} \quad \quad k = 0, \dots, N-1 \\ &= \underbrace{\sum_{N} x_{_N}[n]\cdot e^{-i 2\pi \frac{kn}{N}},}_{DFT}\quad \scriptstyle{\text{(sum over any }n\text{-sequence of length }N)} \end{align} where $$x_{_N}$$ is a periodic summation: $$x_{_N}[n]\ \triangleq\ \sum_{m=-\infty}^{\infty} x[n-mN]$$

So we essentially have the following equality $$\sum_{n=-\infty}^\infty x[n]\cdot e^{-i 2\pi \frac{kn}{N}}= \sum_{n=0}^{N-1} \sum_{m=-\infty}^{\infty} x[n-mN] e^{-i 2\pi \frac{kn}{N}}.$$

I didn't manage to prove it, is this a known identity?

• Be very suspicious of that wiki material. If you go back to the definition of what is a periodic sequence and what is the definition of the DFT, you will realize that is impossible to perform the DFT on a periodic sequence. – Richard Lyons Feb 8 at 11:51
• I think you're right, the article shouldn't have labeled the quantity over the bracket as a DFT, the DFT is a sum over $x(n)$, not $x_{N}(n)$. – Hilbert Feb 8 at 12:13
• No, actually the article is correct. It is a DFT because as jomegA showed below, $x(n)$ is exactly $x_{N}(n)$ over ${0,1,..., N-1}$. – Hilbert Feb 8 at 12:19

The right hand side is the periodic repetition of the left, tells the last equation.

Starting from Fourier transform $$X(\omega)=\sum_{n=-\infty}^{\infty}x(n)e^{-j\omega n}$$ and $$X(\omega)$$ is periodic with period $$2\pi$$. So only the samples in the fundamental frequency range are sufficient.

Now we take $$N$$ equi-distance samples in the iterval $$0\leq\omega\leq 2\pi$$, so the spacing will be $$\dfrac{2\pi}{N}$$

Let $$k$$ be the sample index and $$k=0,1,\dots,N-1$$ and we evaluate $$\omega$$ at $$\left(\dfrac{2\pi k}{N}\right)$$

$$X\left(\dfrac{2\pi}{N}k\right)=\sum_{n=-\infty}^{\infty}x(n)e^{-j2\pi kn/N}$$

which can be written as

$$X\left(\dfrac{2\pi}{N}k\right)=\sum_{l=-\infty}^{\infty}\sum_{n=lN}^{lN+N-1}x(n)e^{-j2\pi kn/N}$$

Now change the index $$n$$ to $$n-lN$$ which results in

$$X\left(\dfrac{2\pi}{N}k\right)=\sum_{n=0}^{N-1}\left[\sum_{l=-\infty}^{\infty}x(n-lN)\right]e^{-j2\pi kn/N}$$

The sequence inside the square brackets is the periodic repetition of $$x(n)$$ of period $$N$$

$$x_p(n)=\sum_{l=-\infty}^{\infty}x(n-Nl)$$

Thus $$x_p(n)=\begin{cases} x(n),\;\;\;\;0\leq n \leq N-1\\ \\ 0,\;\;\;\;\;\;\;\;\;\;\; \mathrm{elsewhere}\\ \end{cases}$$

• Sorry but the question wasn't about the periodization equation, rather about why this equation is true:$$\sum_{n=-\infty}^\infty x[n]\cdot e^{-i 2\pi \frac{kn}{N}}= \sum_{n=0}^{N-1} \sum_{m=-\infty}^{\infty} x[n-mN] e^{-i 2\pi \frac{kn}{N}}.$$ – Hilbert Feb 8 at 10:13
• The equations on the left and right are the same, one is periodic extension of the other. – jomegaA Feb 8 at 11:48
• @jomegaA. Is the "sequence inside the brackets" an infinite-length sequence? – Richard Lyons Feb 9 at 16:31
• @RichardLyons The sequence $x(n)$ is finite and $x_p(n)$ is periodic extension of it. The index $0\leq n \leq N-1$ is definitely finite. – jomegaA Feb 9 at 19:17
• @jomegaA. Hi. I wasn't asking about $x(n)$ or $x_p(n)$. I asked if the "sequence inside the brackets", the summation of $x(n-lN)$, was an infinite-length sequence? Thanks. – Richard Lyons Feb 10 at 14:13