Derive the discrete-time Fourier series

A discrete-time signal $x[n]$ is periodic with period $N$ if $x[n+N] = x[n]$; its fundamental frequency is $\omega_0 = 2\pi/N$. The DTFS writes it as a sum of harmonically related complex exponentials $\phi_k[n] = e^{jk\omega_0 n}$.

Only $N$ distinct exponentials

$$\phi_{k+N}[n] = e^{j(k+N)(2\pi/N)n} = e^{jk(2\pi/N)n}\, e^{j2\pi n} = \phi_k[n]$$

since $e^{j2\pi n} = 1$ for integer $n$. So only $N$ different exponentials exist, e.g. $k = 0, 1, \dots, N-1$. The sum therefore runs over any $N$ consecutive values of $k$, written $k = \langle N\rangle$.

Synthesis equation

$$x[n] = \sum_{k=\langle N\rangle} a_k\, e^{jk\omega_0 n} = \sum_{k=\langle N\rangle} a_k\, e^{jk(2\pi/N)n}$$

Orthogonality result

For integer $r$, using the finite geometric series:

$$\sum_{n=0}^{N-1} e^{jr(2\pi/N)n} = \begin{cases} N, & r = 0, \pm N, \pm 2N, \dots \\ \dfrac{1 - e^{j2\pi r}}{1 - e^{j2\pi r/N}} = 0, & \text{otherwise} \end{cases}$$

Analysis equation

Multiply the synthesis equation by $e^{-jr(2\pi/N)n}$ and sum over one period:

$$\begin{aligned} \sum_{n=\langle N\rangle}x[n]e^{-jr(2\pi/N)n} &= \sum_{n=\langle N\rangle}\sum_{k=\langle N\rangle}a_k e^{j(k-r)(2\pi/N)n} \\ &= \sum_{k=\langle N\rangle}a_k \sum_{n=\langle N\rangle}e^{j(k-r)(2\pi/N)n} \end{aligned}$$

The inner sum is $N$ when $k = r$ (within one period of $k$) and 0 otherwise, so

$$\sum_{n=\langle N\rangle}x[n]e^{-jr(2\pi/N)n} = N a_r$$ $$a_k = \frac{1}{N}\sum_{n=\langle N\rangle}x[n]\,e^{-jk(2\pi/N)n}$$

The DTFS pair

Key points:

• Both sums are finite ($N$ terms), so there is no convergence problem, unlike the CT Fourier series.
• The coefficients are periodic: $a_{k+N} = a_k$.
• $a_0 = \frac{1}{N}\sum x[n]$ is the average (dc) value.

Example: $x[n] = \sin(2\pi n/5)$, $N = 5$: $x[n] = \frac{1}{2j}e^{j(2\pi/5)n} - \frac{1}{2j}e^{-j(2\pi/5)n}$, so $a_1 = \frac{1}{2j}$, $a_{-1} = -\frac{1}{2j}$, and these repeat every 5 values of $k$.