Which Fourier tool do you need?
Periodic or not, continuous or sampled -- the four representations this course builds, and when each applies.
Ask two questions about the signal in front of you: is it periodic, and is it a function of continuous time or a finite list of samples? The answers pick the representation -- reaching for a Fourier transform on a periodic signal (or a Fourier series on one that never repeats) is the single most common wrong turn in this course.
Periodic, continuous-time -> Fourier series
Let f be periodic with period T and let \omega_0 = 2\pi/T. If f has a Fourier series
f(t) \sim \frac{a_0}{2} + \sum_{n=1}^{\infty}\Big(a_n\cos(n\omega_0 t) + b_n\sin(n\omega_0 t)\Big)that may be integrated term by term, then the coefficients are forced to be
a_n = \frac{2}{T}\int_{-T/2}^{T/2} f(t)\cos(n\omega_0 t)\,dt \quad (n \ge 0), \qquad b_n = \frac{2}{T}\int_{-T/2}^{T/2} f(t)\sin(n\omega_0 t)\,dt \quad (n \ge 1).Example
The Euler formulas that pull every a_n, b_n, and the DC term out of f by orthogonality.
Show proof
The whole argument rests on the orthogonality of \{1, \cos(n\omega_0 t), \sin(n\omega_0 t)\}_{n\ge 1} over one period [-T/2, T/2]: for integers m, n \ge 1, \int_{-T/2}^{T/2}\cos(n\omega_0 t)\cos(m\omega_0 t)\,dt = \begin{cases} T/2 & n=m \\ 0 & n\ne m\end{cases}, \qquad \int_{-T/2}^{T/2}\sin(n\omega_0 t)\sin(m\omega_0 t)\,dt = \begin{cases} T/2 & n=m \\ 0 & n\ne m\end{cases}, and \int_{-T/2}^{T/2}\cos(n\omega_0 t)\sin(m\omega_0 t)\,dt = 0 for every n, m (an odd function integrated over a symmetric interval). Each of these follows from the product-to-sum identities, which turn every integrand into a sum of \cos or \sin of (n\pm m)\omega_0 t, and a full period of any nonzero-frequency sine or cosine integrates to 0.
Fix m \ge 1 and multiply both sides of the series by \cos(m\omega_0 t), then integrate over [-T/2, T/2], exchanging the sum and the integral (justified by the assumed term-by-term integrability): \int_{-T/2}^{T/2} f(t)\cos(m\omega_0 t)\,dt = \frac{a_0}{2}\int_{-T/2}^{T/2}\cos(m\omega_0 t)\,dt + \sum_{n=1}^\infty\Big(a_n\!\int_{-T/2}^{T/2}\!\cos(n\omega_0 t)\cos(m\omega_0 t)\,dt + b_n\!\int_{-T/2}^{T/2}\!\sin(n\omega_0 t)\cos(m\omega_0 t)\,dt\Big). The constant term vanishes (a full period of a nonzero-frequency cosine integrates to 0), every sine-cosine cross term vanishes by orthogonality, and every cosine-cosine term vanishes except n=m, which contributes a_m \cdot T/2. So the right side collapses to a_m T/2, giving a_m = \frac{2}{T}\int_{-T/2}^{T/2} f(t)\cos(m\omega_0 t)\,dt. The same argument with \sin(m\omega_0 t) in place of \cos(m\omega_0 t) isolates b_m the same way, since now every cosine-sine cross term and the constant term vanish, leaving b_m T/2.
For a_0, multiply by 1 instead and integrate: every n \ge 1 term vanishes (a full period of \cos or \sin), leaving \int_{-T/2}^{T/2} f(t)\,dt = \frac{a_0}{2}\cdot T, i.e. a_0 = \frac{2}{T}\int_{-T/2}^{T/2} f(t)\,dt — exactly the general a_n formula evaluated at n=0, since \cos(0) = 1, which is why the constant term is conventionally written a_0/2 rather than a_0.
Symbol
c_n
The single-index complex-form coefficient, once you'd rather sum one exponential family than two trig families.
Section
Real form vs. complex form
Aperiodic, continuous-time -> Fourier transform
Symbol
\mathcal{F}
The transform operator -- turns a non-repeating f(t) into a continuous spectrum \\hat f(\\omega), where a Fourier series would have nothing to lock its fundamental frequency onto.
Symbol
\hat{f}
Example
Discrete, finitely many samples -> the DFT
For a length-N sequence x_0, \dots, x_{N-1}, define the discrete Fourier transform X_k = \sum_{n=0}^{N-1} x_n\,e^{-i2\pi kn/N}, \qquad k = 0, \dots, N-1. Then the inverse DFT recovers x exactly: x_n = \frac{1}{N}\sum_{k=0}^{N-1} X_k\,e^{i2\pi kn/N}, \qquad n = 0, \dots, N-1. Moreover, if every x_n is real, then X_{N-k} = \overline{X_k} for k = 1, \dots, N-1 (conjugate symmetry) — so X_0 is always real, and if N is even, X_{N/2} is real as well, since each is its own conjugate partner.
The forward/inverse sums that replace an integral over all t with a finite sum over N samples.
Show proof
Both claims follow from the orthogonality of the N-th roots of unity: for integers k, k', \sum_{n=0}^{N-1} e^{i2\pi(k-k')n/N} = \begin{cases} N & k \equiv k' \pmod N \\ 0 & \text{otherwise,}\end{cases} which is a finite geometric series with ratio e^{i2\pi(k-k')/N} \ne 1 whenever k \not\equiv k' \pmod N, summing to 0 by the geometric sum formula, and trivially N (a sum of N ones) when k \equiv k'.
Invertibility. Substitute the definition of X_k into the proposed inverse formula and swap the (finite, so unconditionally valid) order of summation: \frac{1}{N}\sum_{k=0}^{N-1} X_k e^{i2\pi kn/N} = \frac{1}{N}\sum_{k=0}^{N-1}\left(\sum_{m=0}^{N-1} x_m e^{-i2\pi km/N}\right) e^{i2\pi kn/N} = \frac{1}{N}\sum_{m=0}^{N-1} x_m \sum_{k=0}^{N-1} e^{i2\pi k(n-m)/N}. By the orthogonality relation above (with k'=0, comparing exponent n-m), the inner sum over k is N when m = n and 0 otherwise, so the whole expression collapses to \frac{1}{N}\cdot x_n \cdot N = x_n, exactly the original sequence.
Conjugate symmetry. If every x_n is real, take the complex conjugate of X_k's defining sum: \overline{X_k} = \sum_{n=0}^{N-1} x_n\,e^{i2\pi kn/N} (the x_n are unaffected by conjugation since they're real). Since n is an integer, e^{-i2\pi n} = 1, so e^{i2\pi kn/N} = e^{i2\pi kn/N}\cdot e^{-i2\pi n} = e^{-i2\pi(N-k)n/N}. Substituting, \overline{X_k} = \sum_{n=0}^{N-1} x_n\, e^{-i2\pi(N-k)n/N} = X_{N-k}, exactly the definition of X_{N-k}. Taking k = N-k, i.e. k=0 or (when N is even) k = N/2, forces \overline{X_k} = X_k, i.e. X_k is real.
Section
The DFT as an N x N matrix
Need it fast, at scale -> the FFT
Let N be even, and let X_k = \sum_{n=0}^{N-1} x_n\,e^{-i2\pi kn/N} be the length-N DFT of x_0,\dots,x_{N-1}. Splitting the sum into even-indexed and odd-indexed samples expresses X_k in terms of two length-(N/2) DFTs, E_k (of x_0, x_2, x_4,\dots) and O_k (of x_1, x_3, x_5,\dots):
X_k = E_k + W_N^{\,k}\,O_k, \qquad X_{k+N/2} = E_k - W_N^{\,k}\,O_k, \qquad k = 0, \dots, \tfrac{N}{2}-1,where W_N^{\,k} = e^{-i2\pi k/N} is the twiddle factor. Recursing on this split (each half-size DFT is itself split again, down to size-1 DFTs, which are trivial: the identity) computes the full DFT in O(N\log N) operations, instead of the O(N^2) the defining sum costs directly.
Same DFT sum, computed in O(N\\log N) instead of O(N^2) by recursively splitting even/odd indices.
Show proof
Separate the defining sum by parity of n: write n=2r for the even terms and n=2r+1 for the odd terms, each with r = 0,\dots,\tfrac N2 - 1: X_k = \sum_{r=0}^{N/2-1} x_{2r}\,e^{-i2\pi k(2r)/N} + \sum_{r=0}^{N/2-1} x_{2r+1}\,e^{-i2\pi k(2r+1)/N}. In the first sum, e^{-i2\pi k(2r)/N} = e^{-i2\pi kr/(N/2)} — exactly the kernel of a length-(N/2) DFT in r, evaluated at frequency index k. In the second sum, factor out the part not depending on r: e^{-i2\pi k(2r+1)/N} = e^{-i2\pi k/N}\cdot e^{-i2\pi kr/(N/2)}. So X_k = \underbrace{\sum_{r=0}^{N/2-1} x_{2r}\,e^{-i2\pi kr/(N/2)}}_{E_k} \;+\; e^{-i2\pi k/N}\underbrace{\sum_{r=0}^{N/2-1} x_{2r+1}\,e^{-i2\pi kr/(N/2)}}_{O_k} = E_k + W_N^{\,k}\,O_k. As length-(N/2) DFTs, E_k and O_k are periodic in k with period N/2: E_{k+N/2} = E_k and O_{k+N/2} = O_k. The twiddle factor, however, flips sign every half-period: W_N^{\,k+N/2} = e^{-i2\pi(k+N/2)/N} = e^{-i2\pi k/N}\cdot e^{-i\pi} = -W_N^{\,k}. So evaluating the same split sum at index k + N/2 (for k = 0,\dots,\tfrac N2-1) gives X_{k+N/2} = E_{k+N/2} + W_N^{\,k+N/2}O_{k+N/2} = E_k - W_N^{\,k}O_k — the two outputs X_k and X_{k+N/2} share the same pair (E_k, O_k) and differ only in the sign attached to W_N^{\,k}O_k, which is exactly one "butterfly": two inputs (E_k, O_k) producing two outputs (X_k, X_{k+N/2}) with a single complex multiplication (W_N^{\,k}O_k) and two additions.
Complexity. Let T(N) be the operation count for a length-N DFT computed this way. Computing E_k and O_k costs 2T(N/2), and combining them into all N outputs via N/2 butterflies costs O(N) more, giving the recurrence T(N) = 2T(N/2) + O(N). Unrolling this recursion \log_2 N times (until the base case T(1) = O(1) is reached) accumulates O(N) work at each of \log_2 N levels, for a total of T(N) = O(N\log N) — asymptotically far below the O(N^2) of evaluating the defining sum directly for every k.