\begin{claim}
For a signal written in terms of vectors that represent complex exponentials,
$$x(n) = \sum_{k=\langle p\rangle}X_k\Psi_k$$
the spanning set that makes up the set of vectors is an orthogonal set, in other words, 
$$ \Psi_k \perp \Psi_\ell \quad k \neq \ell$$
\end{claim}

\begin{proof}

For $\Psi_k(n) = e^{ik\omega_0}$, and $\Psi_\ell = e^{i\ell\omega_0n}$, we can write
$\Psi_k = 
\left[
\begin{array}{c}
\Psi_k(0) \\
\Psi_k(1) \\
\vdots \\
\Psi_k(p-1) \\
\end{array}
\right]
$, and 
$\Psi_\ell =
\left[
\begin{array}{c}
\Psi_\ell(0) \\
\Psi_\ell(1) \\
\vdots \\
\Psi_\ell(p-1) \\
\end{array}
\right]
$. 

Note that for an aperiodic signal, the inner product can be written as $\langle \Psi_k,\Psi_\ell\rangle  = \sum \limits_{n=-\infty}^{\infty}\Psi_k(n)\Psi_\ell^*(n) $ or $\int_{-\infty}^{\infty}\Psi_k(t)\Psi_\ell^*(t)dt$. For this proof, we will use the summation for a periodic signal. We can take the inner product
\begin{align*}
\langle \Psi_k,\Psi_\ell\rangle  &= \sum \limits_{n=0}^{p-1}\Psi_k(n)\Psi_\ell^*(n) \\
\langle \Psi_k,\Psi_\ell\rangle  &= \sum \limits_{n=0}^{p-1} e^{ik\omega_0n}e^{-i\ell\omega_0n} \\
\langle \Psi_k,\Psi_\ell\rangle  &= \sum \limits_{n=0}^{p-1} e^{i(k-\ell)\omega_0n} \\
\langle \Psi_k,\Psi_\ell\rangle  &= \sum \limits_{n=0}^{p-1} \lr{e^{i(k-\ell)\omega_0}}^n \\
\end{align*}
Before we arrive at our answer, lets take a slight mathematical detour. Recall that we can write a sum $S$ as 
\begin{align*}
S &= \sum \limits_{k=0}^{\infty}\alpha^k \\
S &= 1 + \alpha + \alpha^2 + \cdots  \\
\alpha S &= \alpha + \alpha^2 + \alpha^3 + \cdots  \\
(1-\alpha)S &= 1 \\
S &= \frac{1}{1-\alpha} \quad \mbox {if } \alpha \neq 1 
\end{align*}

or for a finite sum

\begin{align*}
S &= \sum \limits_{n=A}^{B}\alpha^n \\
S &= \alpha^A + \alpha^{A+1} + \cdots + \alpha^B \\
\alpha S &= \alpha^{A+1} + \alpha^{A+2} + \cdots + \alpha^{B+1} \\
(1-\alpha)S &= \alpha^{B+1} - \alpha^A \\
S &= \frac{\alpha^{B+1}-\alpha^{A}}{1-\alpha} \quad \mbox{if }\alpha \neq 1 \\
S &= \begin{cases}
\frac{\alpha^{B+1}-\alpha^{A}}{1-\alpha} & \alpha\neq1 \\
B-A+1 & \alpha=1 \\
\end{cases}
\end{align*}

Now back to our proof:

\begin{align*}
\langle \Psi_k,\Psi_\ell\rangle  &= \sum \limits_{n=0}^{p-1} \lr{e^{i(k-\ell)\omega_0}}^n \\
\langle \Psi_k,\Psi_\ell\rangle  &= \begin{cases} \frac{\lr{e^{i(k-\ell)\omega_0}}^p-\lr{e^{i(k-\ell)\omega_0}}^0}{1-e^{i(k-\ell)\omega_0}} & k\neq\ell \\ (p-1)-0+1 & k=l \\ \end{cases} \\
\langle \Psi_k,\Psi_\ell\rangle  &= \begin{cases} 0 & k\neq\ell\\ p & k=l \\ \end{cases}
\end{align*}

\end{proof}

We can generalize the result of the above proof further as

$$ \langle \Psi_k,\Psi_\ell\rangle  = p\delta(k-\ell) $$

This works well because the inner product of a vector with itself as the \emph{norm} squared, and the inner product with any other orthogonal vector is 0.
$$\langle \Psi_k,\Psi_k\rangle  = \norm{\Psi_k}^2 = p$$

A few properties about the inner product:
\begin{align*}
\langle f,g\rangle  &= f^Tg^* \\
\langle \alpha f,g\rangle  &= \alpha\langle f,g\rangle  \\
\langle f,\beta g\rangle  &= \beta^* \langle f,g\rangle  \\
\langle \sum_k \alpha_k f_k, g\rangle  &= \sum_k \alpha_k\langle f_k,g\rangle  \\
\end{align*}

So to find $X_\ell$, we can project $\vec{x}$ onto $\Psi_\ell$. 
\begin{align*}
\langle \vec{x}, \Psi_\ell\rangle  &= \langle X_0\Psi_0 + \cdots + X_\ell\Psi_\ell + \cdots + X_{p-1}\Psi_{p-1}, \Psi_\ell\rangle  \\
\langle \vec{x}, \Psi_\ell\rangle  &= X_0\langle \Psi_0,\Psi_\ell\rangle  + \cdots + X_\ell\langle \Psi_\ell,\Psi_\ell\rangle  + \cdots + X_{p-1}\langle \Psi_{p-1},\Psi_\ell\rangle  \\
\langle \vec{x}, \Psi_\ell\rangle  &= X_\ell\langle \Psi_\ell,\Psi_\ell\rangle  \quad \mbox{(all other inner products were 0)}\\
X_\ell &= \frac{\langle \vec{x}, \Psi_\ell\rangle  }{\langle \Psi_\ell,\Psi_\ell\rangle }\\
X_\ell &= \frac{\langle \vec{x}, \Psi_\ell\rangle  }{p}\\
X_\ell &= \frac{\vec{x}^T\Psi_\ell^* }{p}\\
X_\ell &= \frac{1}{p}\sum \limits_{n=0}^{p-1}x(n)\Psi_\ell^*(n) \\
X_\ell &= \frac{1}{p}\sum \limits_{n=0}^{p-1}x(n)e^{-i\ell\omega_0n} \\
\end{align*}

With the discrete fourier series, we can write signals in two distinct forms. We can write a signal in the time domain as a series of complex exponentials which can tell us what happens in the frequency domain:

\begin{nicebox}
\begin{align*}
 x(n) &= \sum \limits_{k=\langle p\rangle }X_ke^{ik\omega_0n}  \quad &\mbox{(synthesis equation)}
\end{align*}
\end{nicebox}

The coefficient in the frequency domain tells us the amount that a certain frequency contributes to the overall signal, which is given by the running sum of the product of the signal in the time domain and the frequency of interest:

\begin{nicebox}
\begin{align*}
 X_k &= \frac{1}{p} \sum \limits_{n=\langle p\rangle }x(n)e^{-ik\omega_0n} \quad &\mbox{(analysis equation)}
\end{align*}
\end{nicebox}

\begin{example}
Find the period and DFS expansion of $x(n) = \sin(2\pi n/3)$. 

To find the period, simply set the inside of the sine function to $2\pi$:
\begin{align*}
\frac{2\pi p}{3} &= 2\pi \\
p &= 3
\end{align*}

Here is a cool method for solving. Luckily, the sine is easily written as the sum of complex exponentials:

\begin{align*}
x(n) &= \sin(2\pi n/3) \\
x(n) &= \frac{e^{i2\pi n/3}-e^{-i2\pi n/3}}{2i} \\
x(n) &= \frac{-1}{2i}e^{-i2\pi n/3} + 0 \cdot e^{i0n} + \frac{1}{2i} e^{i2\pi n/3} \quad \mbox{since } p = 3
\end{align*}
So quickly we can see that we have $e^{-i2\pi n/3}, e^{i0n}, e^{i2\pi n/3}$. This tells us we have $X_{-1} = \frac{-1}{2i}, X_0 = 0, X_1 = \frac{1}{2i}$.
\end{example}


Discrete Fourier Series