Formula & theorem reference

For every n, 0 \le a_n + |a_n| \le 2|a_n| (this holds whether a_n is positive, negative, or zero: if a_n\ge 0 the middle expression is 2a_n; if a_n<0 it's 0). Since \sum|a_n| converges, so does \sum 2|a_n|, and the Direct Comparison Test then gives that \sum (a_n+|a_n|) converges too. Writing a_n = (a_n+|a_n|) - |a_n| expresses the original series as a difference of two convergent series, and a difference of convergent series converges (term-by-term subtraction of two convergent partial sums converges to the difference of their limits).

Let F(t)=\int_a^t f(x)\,dx. Since f\ge0, F is nondecreasing in t, so F(t) either grows without bound or approaches a finite limit — there is no other option for a nondecreasing function. If \int_a^\infty g\,dx converges to some value L, then for every t\ge a, F(t)=\int_a^t f\,dx \le \int_a^t g\,dx \le L, since f\le g pointwise and g\ge 0 makes \int_a^t g\,dx itself nondecreasing in t with limit L. A nondecreasing function bounded above by L must converge to some limit at most L — it cannot grow without bound — so \int_a^\infty f\,dx converges. The second bullet is the direct contrapositive: if f's integral grew without bound, the same inequality F(t)\le\int_a^t g\,dx would force g's integral to grow without bound as well.

Substitute x = i\theta into the Maclaurin series for e^x and use i^2=-1, i^3=-i, i^4=1 (the pattern repeats every four powers): e^{i\theta} = \sum_{n=0}^{\infty}\frac{(i\theta)^n}{n!} = 1 + i\theta - \frac{\theta^2}{2!} - i\frac{\theta^3}{3!} + \frac{\theta^4}{4!} + i\frac{\theta^5}{5!} - \cdots Collecting the terms with no factor of i and the terms with one factor of i into two separate sums gives e^{i\theta} = \underbrace{\left(1 - \frac{\theta^2}{2!} + \frac{\theta^4}{4!} - \cdots\right)}_{\cos\theta} + i\underbrace{\left(\theta - \frac{\theta^3}{3!} + \frac{\theta^5}{5!} - \cdots\right)}_{\sin\theta}. The first parenthesis is exactly the Maclaurin series for \cos\theta and the second is exactly the Maclaurin series for \sin\theta, so e^{i\theta} = \cos\theta + i\sin\theta.

If \mathbf{v} = \mathbf{0} both sides are 0 and the inequality holds trivially, so assume \mathbf{v} \neq \mathbf{0}.

Build a function of a single real variable t by looking at the squared length of \mathbf{u} - t\mathbf{v}. A squared length can never be negative, so for every t, 0 \le \lVert\mathbf{u} - t\mathbf{v}\rVert^2 = (\mathbf{u} - t\mathbf{v})\cdot(\mathbf{u} - t\mathbf{v}).

Expand the dot product using bilinearity: 0 \le \mathbf{u}\cdot\mathbf{u} - 2t\,(\mathbf{u}\cdot\mathbf{v}) + t^2\,(\mathbf{v}\cdot\mathbf{v}) = \lVert\mathbf{v}\rVert^2\,t^2 - 2(\mathbf{u}\cdot\mathbf{v})\,t + \lVert\mathbf{u}\rVert^2.

This is a quadratic in t with positive leading coefficient \lVert\mathbf{v}\rVert^2 (since \mathbf{v} \neq \mathbf{0}), and it never dips below 0 — so it can have at most one real root, meaning its discriminant cannot be positive: \left(-2(\mathbf{u}\cdot\mathbf{v})\right)^2 - 4\lVert\mathbf{v}\rVert^2\lVert\mathbf{u}\rVert^2 \le 0.

Simplify: 4(\mathbf{u}\cdot\mathbf{v})^2 \le 4\lVert\mathbf{u}\rVert^2\lVert\mathbf{v}\rVert^2 \quad\Longrightarrow\quad (\mathbf{u}\cdot\mathbf{v})^2 \le \lVert\mathbf{u}\rVert^2\lVert\mathbf{v}\rVert^2.

Taking square roots of both (nonnegative) sides gives |\mathbf{u}\cdot\mathbf{v}| \le \lVert\mathbf{u}\rVert\,\lVert\mathbf{v}\rVert.

Equality case. The discriminant is exactly 0 precisely when the quadratic touches 0 at its unique root t_0, i.e. when \lVert\mathbf{u} - t_0\mathbf{v}\rVert^2 = 0 for some t_0 — which forces \mathbf{u} - t_0\mathbf{v} = \mathbf{0}, so \mathbf{u} = t_0\mathbf{v}. Equality in the inequality therefore holds exactly when \mathbf{u} is a scalar multiple of \mathbf{v} (covering \mathbf{u} = \mathbf{0} as the t_0 = 0 case).

Sanity check: take \mathbf{u} = \mathbf{v}. Then the left side is |\mathbf{u}\cdot\mathbf{u}| = \lVert\mathbf{u}\rVert^2 and the right side is \lVert\mathbf{u}\rVert\,\lVert\mathbf{u}\rVert = \lVert\mathbf{u}\rVert^2 — equality, exactly as the parallel case demands since a vector is trivially a scalar multiple of itself.

Drop a perpendicular from the tip of \mathbf{v} down onto the line through \mathbf{u}; this forms a right triangle with hypotenuse |\mathbf{v}| and angle \theta between \mathbf{u} and \mathbf{v}. Exactly as in Chapter 8, the leg lying along \mathbf{u}'s line — the scalar projection — has length |\mathbf{v}|\cos\theta (adjacent equals hypotenuse times cosine). From the theorem above, \cos\theta = \frac{\mathbf{u}\cdot\mathbf{v}}{|\mathbf{u}|\,|\mathbf{v}|}, so the scalar projection simplifies to

The vector projection points along \mathbf{u}'s own direction, so multiply this scalar length by the unit vector \frac{\mathbf{u}}{|\mathbf{u}|}:

Existence. Let \{\mathbf{u}_1, \dots, \mathbf{u}_p\} be an orthogonal basis for W (one always exists, by Gram–Schmidt if no other is in hand). Define

Each term of \hat{\mathbf y} is a scalar multiple of some \mathbf{u}_i \in W, and W is closed under linear combinations, so \hat{\mathbf y} \in W outright — no further check needed there. The work is showing \mathbf{z} \in W^\perp, and for that it suffices to show \mathbf{z} is orthogonal to every basis vector \mathbf{u}_i, since orthogonality to a spanning set of W forces orthogonality to all of W. Fix i and compute \mathbf{z}\cdot\mathbf{u}_i, using that \mathbf{u}_i\cdot\mathbf{u}_j = 0 for j \ne i (orthogonality of the basis) so every term of \hat{\mathbf y} except the i-th drops out of the dot product:

So \mathbf{z} \perp \mathbf{u}_i for every i, hence \mathbf{z} \in W^\perp, and \mathbf{y} = \hat{\mathbf y} + \mathbf{z} is a decomposition of the required form. That \hat{\mathbf y} is exactly \operatorname{proj}_W\mathbf{y} is just the definition of the projection onto W built from an orthogonal basis of W.

Uniqueness. Suppose \mathbf{y} also decomposes as \mathbf{y} = \hat{\mathbf y}' + \mathbf{z}' with \hat{\mathbf y}' \in W and \mathbf{z}' \in W^\perp. Subtracting the two decompositions of \mathbf{y} gives

The left side lies in W, since W is a subspace and both \hat{\mathbf y}, \hat{\mathbf y}' \in W; the right side lies in W^\perp for the same reason applied to \mathbf{z}, \mathbf{z}' \in W^\perp. So this common vector belongs to W \cap W^\perp. But a vector orthogonal to every vector in W — including itself, if it lies in W — must have zero length: taking \mathbf{v} = \hat{\mathbf y} - \hat{\mathbf y}' as that vector, \mathbf{v} \in W and \mathbf{v} \in W^\perp together force \mathbf{v}\cdot\mathbf{v} = 0, so \mathbf{v} = \mathbf{0}. Hence \hat{\mathbf y} = \hat{\mathbf y}' and, from the subtracted equation, \mathbf{z} = \mathbf{z}' as well. The decomposition is unique.

Sanity check: take W = \operatorname{span}\{(1,0,0),(0,1,0)\}, the xy-plane inside \mathbb{R}^3, and \mathbf{y} = (2,3,5). The orthogonal basis \{(1,0,0),(0,1,0)\} gives \hat{\mathbf y} = (2,3,0) and \mathbf{z} = (0,0,5), which is indeed orthogonal to both basis vectors — exactly the geometrically obvious split of \mathbf{y} into its in-plane part and its part along the perpendicular z-axis.

(\Leftarrow) n independent eigenvectors give A = PDP^{-1}. Suppose v_1, \dots, v_n are linearly independent eigenvectors of A, with Av_i = \lambda_i v_i. Let P be the matrix with these vectors as its columns, and let D = \operatorname{diag}(\lambda_1, \dots, \lambda_n). Multiplying A into P column by column, AP = A\begin{bmatrix} v_1 & \cdots & v_n \end{bmatrix} = \begin{bmatrix} Av_1 & \cdots & Av_n \end{bmatrix} = \begin{bmatrix} \lambda_1 v_1 & \cdots & \lambda_n v_n \end{bmatrix}. Multiplying P by D on the right scales each column of P by the matching diagonal entry of D, producing the very same matrix: PD = \begin{bmatrix} v_1 & \cdots & v_n \end{bmatrix} \operatorname{diag}(\lambda_1,\dots,\lambda_n) = \begin{bmatrix} \lambda_1 v_1 & \cdots & \lambda_n v_n \end{bmatrix}. So AP = PD. Because P's columns are n linearly independent vectors in \mathbb{R}^n, P is invertible, and right-multiplying both sides by P^{-1} gives A = PDP^{-1}.

(\Rightarrow) A = PDP^{-1} gives n independent eigenvectors. Suppose A = PDP^{-1} with P invertible and D = \operatorname{diag}(\lambda_1, \dots, \lambda_n). Then AP = PD, and reading that equation column by column exactly as above shows Av_i = \lambda_i v_i, where v_i is the i-th column of P. Each v_i is nonzero — a zero column would make P singular — so v_1,\dots,v_n are eigenvectors of A. Since P is invertible, its columns are linearly independent, which produces the needed n independent eigenvectors.

Sanity check: take A = \begin{bmatrix} 4 & 1 \\ 0 & 3 \end{bmatrix}, upper triangular, so its eigenvalues sit on the diagonal: \lambda_1 = 4, \lambda_2 = 3. Solving (A - 4I)v = 0 gives eigenvector v_1 = (1,0), and (A-3I)v = 0 gives v_2 = (1,-1). These two are not scalar multiples of each other, so they're independent, and the theorem guarantees A = PDP^{-1} with P = \begin{bmatrix} 1 & 1 \\ 0 & -1 \end{bmatrix} and D = \begin{bmatrix} 4 & 0 \\ 0 & 3 \end{bmatrix} — which a direct multiplication PDP^{-1} confirms reproduces A.

(\Leftarrow) Orthogonal diagonalizability forces symmetry. Suppose A = QDQ^{\mathsf T} with Q orthogonal and D diagonal. Diagonal matrices equal their own transpose, and transposing a product reverses the order of its factors, so A^{\mathsf T} = (QDQ^{\mathsf T})^{\mathsf T} = (Q^{\mathsf T})^{\mathsf T}D^{\mathsf T}Q^{\mathsf T} = QDQ^{\mathsf T} = A. So A is symmetric. The rest of the proof handles the harder direction.

Symmetric matrices have only real eigenvalues. Let \lambda be an eigenvalue of A, allowing for the moment that it might be complex, with eigenvector v (possibly with complex entries), so Av = \lambda v. Let \bar v denote the entrywise complex conjugate of v, and consider the scalar \bar v^{\mathsf T} A v. Computing it one way, \bar v^{\mathsf T} A v = \bar v^{\mathsf T}(\lambda v) = \lambda (\bar v^{\mathsf T} v) = \lambda \lVert v \rVert^2, since \bar v^{\mathsf T} v = \sum_i \overline{v_i} v_i = \sum_i |v_i|^2 = \lVert v \rVert^2 is real and positive (v \neq 0, being an eigenvector). Computing the same scalar the other way, using A^{\mathsf T} = A and that \bar v^{\mathsf T} A v is a 1\times 1 matrix and so equal to its own transpose, \bar v^{\mathsf T} A v = \left(\bar v^{\mathsf T} A v\right)^{\mathsf T} = v^{\mathsf T} A^{\mathsf T} \bar v = v^{\mathsf T} A \bar v. Taking the complex conjugate of Av = \lambda v gives A\bar v = \bar\lambda \bar v (since A has real entries, conjugation passes through it untouched), so v^{\mathsf T} A \bar v = v^{\mathsf T}(\bar\lambda \bar v) = \bar\lambda (v^{\mathsf T}\bar v) = \bar\lambda \lVert v\rVert^2, using v^{\mathsf T}\bar v = \overline{\bar v^{\mathsf T} v} = \lVert v\rVert^2 again. The two computations of \bar v^{\mathsf T} A v must agree: \lambda \lVert v \rVert^2 = \bar\lambda \lVert v \rVert^2. Since \lVert v \rVert^2 \neq 0, this forces \lambda = \bar\lambda, i.e. \lambda is real. So every eigenvalue of A is real, and consequently every eigenvalue has a real eigenvector (a real matrix minus a real multiple of I_n has a real null space).

Eigenvectors for distinct eigenvalues are orthogonal. Let Av_1 = \lambda_1 v_1 and Av_2 = \lambda_2 v_2 with \lambda_1 \neq \lambda_2. Using symmetry, \lambda_1 (v_1 \cdot v_2) = (Av_1) \cdot v_2 = v_1^{\mathsf T}A^{\mathsf T} v_2 = v_1^{\mathsf T}Av_2 = v_1 \cdot (Av_2) = \lambda_2(v_1 \cdot v_2). So (\lambda_1 - \lambda_2)(v_1 \cdot v_2) = 0, and since \lambda_1 \neq \lambda_2, this forces v_1 \cdot v_2 = 0.

Building Q by induction on n. The base case n=1 is trivial: any 1\times 1 matrix is already diagonal, and Q = [1] is orthogonal. For the inductive step, assume every symmetric (n-1)\times(n-1) matrix is orthogonally diagonalizable, and let A be a symmetric n \times n matrix. By the real-eigenvalue fact above, A has a real eigenvalue \lambda_1 with a real, nonzero eigenvector; rescale it to a unit vector q_1, so Aq_1 = \lambda_1 q_1 and \lVert q_1 \rVert = 1. Extend \{q_1\} to an orthonormal basis \{q_1, q_2, \dots, q_n\} of \mathbb{R}^n (extend to any basis and apply Gram–Schmidt, which leaves q_1 fixed since it is already a unit vector orthogonal to nothing else yet chosen), and let P be the orthogonal matrix with these vectors as columns.

The subspace W = \operatorname{span}(q_2,\dots,q_n) = q_1^\perp is invariant under A: for w \in W, (Aw)\cdot q_1 = w \cdot (Aq_1) = w \cdot (\lambda_1 q_1) = \lambda_1(w\cdot q_1) = 0, using symmetry in the first step exactly as above, so Aw is again orthogonal to q_1, i.e. Aw \in W. Consequently P^{\mathsf T}AP has the block form P^{\mathsf T}AP = \begin{bmatrix} \lambda_1 & 0 \\ 0 & A_1 \end{bmatrix} for some symmetric (n-1)\times(n-1) matrix A_1: the first column of P^{\mathsf T}AP is P^{\mathsf T}(Aq_1) = P^{\mathsf T}(\lambda_1 q_1) = \lambda_1 e_1 (since P^{\mathsf T}q_1 = e_1, q_1 being the first column of the orthogonal matrix P), giving the zero block below \lambda_1; and P^{\mathsf T}AP is symmetric because A is, which forces the zero block to the right of \lambda_1 as well. By the inductive hypothesis, A_1 = Q_1D_1Q_1^{\mathsf T} for some orthogonal (n-1)\times(n-1) matrix Q_1 and diagonal D_1. Setting Q = P\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix}, \qquad D = \begin{bmatrix} \lambda_1 & 0 \\ 0 & D_1 \end{bmatrix}, the block-diagonal factor is orthogonal (its columns are orthonormal, being e_1 together with the orthonormal columns of Q_1), so Q is a product of orthogonal matrices and hence orthogonal itself. Unwinding the block product, Q^{\mathsf T}AQ = \begin{bmatrix} 1 & 0 \\ 0 & Q_1^{\mathsf T} \end{bmatrix}P^{\mathsf T}AP\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & Q_1^{\mathsf T} \end{bmatrix}\begin{bmatrix} \lambda_1 & 0 \\ 0 & A_1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix} = \begin{bmatrix} \lambda_1 & 0 \\ 0 & Q_1^{\mathsf T}A_1Q_1 \end{bmatrix} = D, so A = QDQ^{\mathsf T} with Q orthogonal and D diagonal, completing the induction.

Sanity check: take the symmetric matrix A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}. Its characteristic equation is (2-\lambda)^2 - 1 = 0, so \lambda_1 = 3 and \lambda_2 = 1 — both real, as guaranteed. Solving (A-3I)v=0 gives v_1 = (1,1), and (A-I)v=0 gives v_2 = (1,-1); these two are orthogonal (v_1 \cdot v_2 = 1 - 1 = 0), exactly as the theorem predicts for eigenvectors of distinct eigenvalues. Normalizing gives q_1 = \frac{1}{\sqrt2}(1,1) and q_2 = \frac{1}{\sqrt2}(1,-1), and setting Q = \begin{bmatrix} 1/\sqrt2 & 1/\sqrt2 \\ 1/\sqrt2 & -1/\sqrt2 \end{bmatrix}, D = \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix}, a direct multiplication confirms QDQ^{\mathsf T} = A.

If \mathbf{v} = \mathbf{0} both sides are 0 and the inequality holds trivially, so assume \mathbf{v} \neq \mathbf{0}.

Build a function of a single real variable t by looking at the squared length of \mathbf{u} - t\mathbf{v}. A squared length can never be negative, so for every t, 0 \le \lVert\mathbf{u} - t\mathbf{v}\rVert^2 = (\mathbf{u} - t\mathbf{v})\cdot(\mathbf{u} - t\mathbf{v}).

Expand the dot product using bilinearity: 0 \le \mathbf{u}\cdot\mathbf{u} - 2t\,(\mathbf{u}\cdot\mathbf{v}) + t^2\,(\mathbf{v}\cdot\mathbf{v}) = \lVert\mathbf{v}\rVert^2\,t^2 - 2(\mathbf{u}\cdot\mathbf{v})\,t + \lVert\mathbf{u}\rVert^2.

This is a quadratic in t with positive leading coefficient \lVert\mathbf{v}\rVert^2 (since \mathbf{v} \neq \mathbf{0}), and it never dips below 0 — so it can have at most one real root, meaning its discriminant cannot be positive: \left(-2(\mathbf{u}\cdot\mathbf{v})\right)^2 - 4\lVert\mathbf{v}\rVert^2\lVert\mathbf{u}\rVert^2 \le 0.

Simplify: 4(\mathbf{u}\cdot\mathbf{v})^2 \le 4\lVert\mathbf{u}\rVert^2\lVert\mathbf{v}\rVert^2 \quad\Longrightarrow\quad (\mathbf{u}\cdot\mathbf{v})^2 \le \lVert\mathbf{u}\rVert^2\lVert\mathbf{v}\rVert^2.

Taking square roots of both (nonnegative) sides gives |\mathbf{u}\cdot\mathbf{v}| \le \lVert\mathbf{u}\rVert\,\lVert\mathbf{v}\rVert.

Equality case. The discriminant is exactly 0 precisely when the quadratic touches 0 at its unique root t_0, i.e. when \lVert\mathbf{u} - t_0\mathbf{v}\rVert^2 = 0 for some t_0 — which forces \mathbf{u} - t_0\mathbf{v} = \mathbf{0}, so \mathbf{u} = t_0\mathbf{v}. Equality in the inequality therefore holds exactly when \mathbf{u} is a scalar multiple of \mathbf{v} (covering \mathbf{u} = \mathbf{0} as the t_0 = 0 case).

Sanity check: take \mathbf{u} = \mathbf{v}. Then the left side is |\mathbf{u}\cdot\mathbf{u}| = \lVert\mathbf{u}\rVert^2 and the right side is \lVert\mathbf{u}\rVert\,\lVert\mathbf{u}\rVert = \lVert\mathbf{u}\rVert^2 — equality, exactly as the parallel case demands since a vector is trivially a scalar multiple of itself.

Existence. Let \{\mathbf{u}_1, \dots, \mathbf{u}_p\} be an orthogonal basis for W (one always exists, by Gram–Schmidt if no other is in hand). Define

Each term of \hat{\mathbf y} is a scalar multiple of some \mathbf{u}_i \in W, and W is closed under linear combinations, so \hat{\mathbf y} \in W outright — no further check needed there. The work is showing \mathbf{z} \in W^\perp, and for that it suffices to show \mathbf{z} is orthogonal to every basis vector \mathbf{u}_i, since orthogonality to a spanning set of W forces orthogonality to all of W. Fix i and compute \mathbf{z}\cdot\mathbf{u}_i, using that \mathbf{u}_i\cdot\mathbf{u}_j = 0 for j \ne i (orthogonality of the basis) so every term of \hat{\mathbf y} except the i-th drops out of the dot product:

So \mathbf{z} \perp \mathbf{u}_i for every i, hence \mathbf{z} \in W^\perp, and \mathbf{y} = \hat{\mathbf y} + \mathbf{z} is a decomposition of the required form. That \hat{\mathbf y} is exactly \operatorname{proj}_W\mathbf{y} is just the definition of the projection onto W built from an orthogonal basis of W.

Uniqueness. Suppose \mathbf{y} also decomposes as \mathbf{y} = \hat{\mathbf y}' + \mathbf{z}' with \hat{\mathbf y}' \in W and \mathbf{z}' \in W^\perp. Subtracting the two decompositions of \mathbf{y} gives

The left side lies in W, since W is a subspace and both \hat{\mathbf y}, \hat{\mathbf y}' \in W; the right side lies in W^\perp for the same reason applied to \mathbf{z}, \mathbf{z}' \in W^\perp. So this common vector belongs to W \cap W^\perp. But a vector orthogonal to every vector in W — including itself, if it lies in W — must have zero length: taking \mathbf{v} = \hat{\mathbf y} - \hat{\mathbf y}' as that vector, \mathbf{v} \in W and \mathbf{v} \in W^\perp together force \mathbf{v}\cdot\mathbf{v} = 0, so \mathbf{v} = \mathbf{0}. Hence \hat{\mathbf y} = \hat{\mathbf y}' and, from the subtracted equation, \mathbf{z} = \mathbf{z}' as well. The decomposition is unique.

Sanity check: take W = \operatorname{span}\{(1,0,0),(0,1,0)\}, the xy-plane inside \mathbb{R}^3, and \mathbf{y} = (2,3,5). The orthogonal basis \{(1,0,0),(0,1,0)\} gives \hat{\mathbf y} = (2,3,0) and \mathbf{z} = (0,0,5), which is indeed orthogonal to both basis vectors — exactly the geometrically obvious split of \mathbf{y} into its in-plane part and its part along the perpendicular z-axis.

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.

Write the N-th partial sum as a single integral against the Dirichlet kernel D_N(u) = \dfrac{\sin\big((N+\tfrac12)\omega_0 u\big)}{\sin(\omega_0 u/2)}: substituting the coefficient formulas and summing the resulting geometric-style series of cosines gives S_N(t) = \frac{1}{T}\int_{-T/2}^{T/2} f(t-u)\,D_N(u)\,du, where D_N satisfies \frac{1}{T}\int_{-T/2}^{T/2} D_N(u)\,du = 1 for every N and concentrates increasingly sharply near u=0 as N\to\infty (its central lobe narrows like 1/N, even though — unlike a genuine approximate identity — it also has decaying side ripples, which is exactly what produces the Gibbs phenomenon at a jump rather than spoiling convergence away from one).

Split the integral into a piece near u=0 and the remainder. On the remainder, f(t-u)/\sin(\omega_0 u/2) (paired appropriately with the one-sided limits subtracted off) is piecewise continuous, so the Riemann–Lebesgue lemma — a piecewise-continuous function's integral against \sin\big((N+\tfrac12)\omega_0 u\big) vanishes as N \to \infty because the integrand oscillates faster and faster — shows that piece contributes 0 in the limit. Near u=0, the piecewise-smoothness hypothesis (in particular, the one-sided derivatives existing at t) controls how fast f(t-u) approaches f(t^\mp) as u \to 0^\mp closely enough that the concentrating kernel picks out exactly the average of the two one-sided limits, \tfrac12\big(f(t^-)+f(t^+)\big), in the limit N\to\infty. This is the classical localization principle: whether the series converges at t, and to what, depends only on the behavior of f in an arbitrarily small neighborhood of t — consistent with a jump elsewhere on the period having no effect on convergence at a distant point of continuity.

Existence. Let \{\mathbf{u}_1, \dots, \mathbf{u}_p\} be an orthogonal basis for W (one always exists, by Gram–Schmidt if no other is in hand). Define

Each term of \hat{\mathbf y} is a scalar multiple of some \mathbf{u}_i \in W, and W is closed under linear combinations, so \hat{\mathbf y} \in W outright — no further check needed there. The work is showing \mathbf{z} \in W^\perp, and for that it suffices to show \mathbf{z} is orthogonal to every basis vector \mathbf{u}_i, since orthogonality to a spanning set of W forces orthogonality to all of W. Fix i and compute \mathbf{z}\cdot\mathbf{u}_i, using that \mathbf{u}_i\cdot\mathbf{u}_j = 0 for j \ne i (orthogonality of the basis) so every term of \hat{\mathbf y} except the i-th drops out of the dot product:

So \mathbf{z} \perp \mathbf{u}_i for every i, hence \mathbf{z} \in W^\perp, and \mathbf{y} = \hat{\mathbf y} + \mathbf{z} is a decomposition of the required form. That \hat{\mathbf y} is exactly \operatorname{proj}_W\mathbf{y} is just the definition of the projection onto W built from an orthogonal basis of W.

Uniqueness. Suppose \mathbf{y} also decomposes as \mathbf{y} = \hat{\mathbf y}' + \mathbf{z}' with \hat{\mathbf y}' \in W and \mathbf{z}' \in W^\perp. Subtracting the two decompositions of \mathbf{y} gives

The left side lies in W, since W is a subspace and both \hat{\mathbf y}, \hat{\mathbf y}' \in W; the right side lies in W^\perp for the same reason applied to \mathbf{z}, \mathbf{z}' \in W^\perp. So this common vector belongs to W \cap W^\perp. But a vector orthogonal to every vector in W — including itself, if it lies in W — must have zero length: taking \mathbf{v} = \hat{\mathbf y} - \hat{\mathbf y}' as that vector, \mathbf{v} \in W and \mathbf{v} \in W^\perp together force \mathbf{v}\cdot\mathbf{v} = 0, so \mathbf{v} = \mathbf{0}. Hence \hat{\mathbf y} = \hat{\mathbf y}' and, from the subtracted equation, \mathbf{z} = \mathbf{z}' as well. The decomposition is unique.

Sanity check: take W = \operatorname{span}\{(1,0,0),(0,1,0)\}, the xy-plane inside \mathbb{R}^3, and \mathbf{y} = (2,3,5). The orthogonal basis \{(1,0,0),(0,1,0)\} gives \hat{\mathbf y} = (2,3,0) and \mathbf{z} = (0,0,5), which is indeed orthogonal to both basis vectors — exactly the geometrically obvious split of \mathbf{y} into its in-plane part and its part along the perpendicular z-axis.

The key fact is that S_N is the orthogonal projection of f onto the (2N+1)-dimensional span of \{1, \cos(\omega_0 t), \dots, \cos(N\omega_0 t), \sin(\omega_0 t), \dots, \sin(N\omega_0 t)\}, built from exactly the same orthogonality relations used to derive the coefficient formulas. A defining property of an orthogonal projection is that the residual f - S_N is orthogonal to everything in that span — in particular to S_N itself, since S_N lies in the span: \int_{-T/2}^{T/2} (f - S_N)\,S_N\,dt = 0.

Expand the nonnegative quantity \int_{-T/2}^{T/2}(f-S_N)^2\,dt using this: 0 \le \int_{-T/2}^{T/2} (f-S_N)^2\,dt = \int_{-T/2}^{T/2} f^2\,dt - 2\int_{-T/2}^{T/2} f\,S_N\,dt + \int_{-T/2}^{T/2} S_N^2\,dt. Since \int (f-S_N)S_N = 0 expands to \int f\,S_N = \int S_N^2, the middle and last terms combine: -2\int f S_N + \int S_N^2 = -\int f S_N - \int S_N^2 + \int S_N^2 = -\int S_N^2 (using \int fS_N = \int S_N^2 again). So the inequality becomes 0 \le \int_{-T/2}^{T/2} f^2\,dt - \int_{-T/2}^{T/2} S_N^2\,dt, \qquad\text{i.e.}\qquad \int_{-T/2}^{T/2} S_N^2\,dt \le \int_{-T/2}^{T/2} f^2\,dt. Finally, \int_{-T/2}^{T/2} S_N^2\,dt = T\left[\left(\frac{a_0}{2}\right)^2 + \frac12\sum_{n=1}^N(a_n^2+b_n^2)\right] by the same orthogonality relations applied to S_N's own definition (every cross term between different harmonics in S_N^2 integrates to 0; only the squared terms survive). Substituting and dividing by T gives Bessel's Inequality.

This is the N\to\infty equality case of Bessel's Inequality, which holds because the trigonometric system \{1, \cos(n\omega_0 t), \sin(n\omega_0 t)\} is a complete orthogonal system on L^2([-T/2,T/2]): the N-th partial sum S_N (the orthogonal projection of f onto the span of the first N harmonics) converges to f in mean-square, \int_{-T/2}^{T/2} (f - S_N)^2\,dt \to 0 as N \to \infty.

Bessel's Inequality already gives, for every N, T\left[\left(\frac{a_0}{2}\right)^2 + \frac{1}{2}\sum_{n=1}^{N}(a_n^2+b_n^2)\right] = \int_{-T/2}^{T/2} S_N(t)^2\,dt \le \int_{-T/2}^{T/2} f(t)^2\,dt, with the gap between the two sides equal to \int_{-T/2}^{T/2}(f-S_N)^2\,dt (expand \int f^2 = \int (f-S_N)^2 + 2\int(f-S_N)S_N + \int S_N^2 and note the cross term vanishes, since S_N is exactly the orthogonal projection of f onto its own span). Completeness is precisely the statement that this gap shrinks to 0, so letting N \to \infty turns the inequality into the stated equality, dividing through by T.

Sanity check. For f(t) = \cos(\omega_0 t) itself (period T), the only nonzero coefficient is a_1 = 1, so the right side is \tfrac12(1)^2 = \tfrac12. The left side is the mean square of a cosine over a full period, \frac{1}{T}\int_{-T/2}^{T/2}\cos^2(\omega_0 t)\,dt = \tfrac12, matching exactly.

If \mathbf{v} = \mathbf{0} both sides are 0 and the inequality holds trivially, so assume \mathbf{v} \neq \mathbf{0}.

Build a function of a single real variable t by looking at the squared length of \mathbf{u} - t\mathbf{v}. A squared length can never be negative, so for every t, 0 \le \lVert\mathbf{u} - t\mathbf{v}\rVert^2 = (\mathbf{u} - t\mathbf{v})\cdot(\mathbf{u} - t\mathbf{v}).

Expand the dot product using bilinearity: 0 \le \mathbf{u}\cdot\mathbf{u} - 2t\,(\mathbf{u}\cdot\mathbf{v}) + t^2\,(\mathbf{v}\cdot\mathbf{v}) = \lVert\mathbf{v}\rVert^2\,t^2 - 2(\mathbf{u}\cdot\mathbf{v})\,t + \lVert\mathbf{u}\rVert^2.

This is a quadratic in t with positive leading coefficient \lVert\mathbf{v}\rVert^2 (since \mathbf{v} \neq \mathbf{0}), and it never dips below 0 — so it can have at most one real root, meaning its discriminant cannot be positive: \left(-2(\mathbf{u}\cdot\mathbf{v})\right)^2 - 4\lVert\mathbf{v}\rVert^2\lVert\mathbf{u}\rVert^2 \le 0.

Simplify: 4(\mathbf{u}\cdot\mathbf{v})^2 \le 4\lVert\mathbf{u}\rVert^2\lVert\mathbf{v}\rVert^2 \quad\Longrightarrow\quad (\mathbf{u}\cdot\mathbf{v})^2 \le \lVert\mathbf{u}\rVert^2\lVert\mathbf{v}\rVert^2.

Taking square roots of both (nonnegative) sides gives |\mathbf{u}\cdot\mathbf{v}| \le \lVert\mathbf{u}\rVert\,\lVert\mathbf{v}\rVert.

Equality case. The discriminant is exactly 0 precisely when the quadratic touches 0 at its unique root t_0, i.e. when \lVert\mathbf{u} - t_0\mathbf{v}\rVert^2 = 0 for some t_0 — which forces \mathbf{u} - t_0\mathbf{v} = \mathbf{0}, so \mathbf{u} = t_0\mathbf{v}. Equality in the inequality therefore holds exactly when \mathbf{u} is a scalar multiple of \mathbf{v} (covering \mathbf{u} = \mathbf{0} as the t_0 = 0 case).

Sanity check: take \mathbf{u} = \mathbf{v}. Then the left side is |\mathbf{u}\cdot\mathbf{u}| = \lVert\mathbf{u}\rVert^2 and the right side is \lVert\mathbf{u}\rVert\,\lVert\mathbf{u}\rVert = \lVert\mathbf{u}\rVert^2 — equality, exactly as the parallel case demands since a vector is trivially a scalar multiple of itself.

Existence. Let \{\mathbf{u}_1, \dots, \mathbf{u}_p\} be an orthogonal basis for W (one always exists, by Gram–Schmidt if no other is in hand). Define

Each term of \hat{\mathbf y} is a scalar multiple of some \mathbf{u}_i \in W, and W is closed under linear combinations, so \hat{\mathbf y} \in W outright — no further check needed there. The work is showing \mathbf{z} \in W^\perp, and for that it suffices to show \mathbf{z} is orthogonal to every basis vector \mathbf{u}_i, since orthogonality to a spanning set of W forces orthogonality to all of W. Fix i and compute \mathbf{z}\cdot\mathbf{u}_i, using that \mathbf{u}_i\cdot\mathbf{u}_j = 0 for j \ne i (orthogonality of the basis) so every term of \hat{\mathbf y} except the i-th drops out of the dot product:

So \mathbf{z} \perp \mathbf{u}_i for every i, hence \mathbf{z} \in W^\perp, and \mathbf{y} = \hat{\mathbf y} + \mathbf{z} is a decomposition of the required form. That \hat{\mathbf y} is exactly \operatorname{proj}_W\mathbf{y} is just the definition of the projection onto W built from an orthogonal basis of W.

Uniqueness. Suppose \mathbf{y} also decomposes as \mathbf{y} = \hat{\mathbf y}' + \mathbf{z}' with \hat{\mathbf y}' \in W and \mathbf{z}' \in W^\perp. Subtracting the two decompositions of \mathbf{y} gives

The left side lies in W, since W is a subspace and both \hat{\mathbf y}, \hat{\mathbf y}' \in W; the right side lies in W^\perp for the same reason applied to \mathbf{z}, \mathbf{z}' \in W^\perp. So this common vector belongs to W \cap W^\perp. But a vector orthogonal to every vector in W — including itself, if it lies in W — must have zero length: taking \mathbf{v} = \hat{\mathbf y} - \hat{\mathbf y}' as that vector, \mathbf{v} \in W and \mathbf{v} \in W^\perp together force \mathbf{v}\cdot\mathbf{v} = 0, so \mathbf{v} = \mathbf{0}. Hence \hat{\mathbf y} = \hat{\mathbf y}' and, from the subtracted equation, \mathbf{z} = \mathbf{z}' as well. The decomposition is unique.

Sanity check: take W = \operatorname{span}\{(1,0,0),(0,1,0)\}, the xy-plane inside \mathbb{R}^3, and \mathbf{y} = (2,3,5). The orthogonal basis \{(1,0,0),(0,1,0)\} gives \hat{\mathbf y} = (2,3,0) and \mathbf{z} = (0,0,5), which is indeed orthogonal to both basis vectors — exactly the geometrically obvious split of \mathbf{y} into its in-plane part and its part along the perpendicular z-axis.

Treat \frac{dy}{dx} as a genuine ratio for a moment (this is a shortcut that a full proof by the chain rule justifies rigorously): dividing both sides by h(y) gives \frac{1}{h(y)}\,dy = g(x)\,dx. Integrate the left side with respect to y and the right side with respect to x — the two sides need not share a variable of integration at all, since each is being integrated on its own. The chain rule confirms this is legitimate: if H(y) is an antiderivative of \frac{1}{h(y)}, differentiating H(y(x)) = \int g(x)\,dx + C implicitly with respect to x gives H'(y)\cdot\frac{dy}{dx} = g(x), i.e. \frac{1}{h(y)}\cdot\frac{dy}{dx} = g(x) — exactly the original equation, recovered.

The formula is the T\to\infty limit of the Fourier series inversion already established for periodic functions, made precise by treating f as "periodic with infinite period." Restrict attention to f on [-T/2, T/2] and extend it periodically with period T; its complex Fourier series is f(t) \sim \sum_n c_n e^{in\omega_0 t} with \omega_0 = 2\pi/T and c_n = \frac{1}{T}\int_{-T/2}^{T/2} f(t)e^{-in\omega_0 t}\,dt. Multiplying and dividing by T, f(t) \sim \sum_{n=-\infty}^{\infty} \Big(\underbrace{\int_{-T/2}^{T/2} f(t)e^{-in\omega_0 t}\,dt}_{\to\ \hat f(n\omega_0)\text{ as }T\to\infty}\Big) e^{in\omega_0 t}\,\frac{\omega_0}{2\pi}. As T \to \infty: the spacing \omega_0 = 2\pi/T between consecutive harmonics shrinks to 0, so the discrete frequencies n\omega_0 sweep out the continuum, the bracketed quantity converges to \hat f(n\omega_0) (the periodic extension agrees with f on an interval growing to cover all of \mathbb{R}), and the sum over n — spaced \omega_0 apart and weighted by \omega_0 — converges to a Riemann sum for an integral over \omega: f(t) \;\longleftarrow\; \sum_n \hat f(n\omega_0)\,e^{in\omega_0 t}\,\frac{\omega_0}{2\pi} \;\longrightarrow\; \frac{1}{2\pi}\int_{-\infty}^{\infty} \hat f(\omega)\,e^{i\omega t}\,d\omega. The midpoint-at-a-jump behavior, rather than plain equality to f(t) everywhere, carries over unchanged from the periodic case, since it is a strictly local property (the Dirichlet convergence theorem's own localization principle) unaffected by letting the period grow.

Fix \varepsilon>0. Every f\in L^1(\mathbb R) can be approximated, in the L^1 norm, as closely as desired by a step function — a finite sum of scaled, shifted indicator functions of bounded intervals, g(t)=\sum_{k=1}^N c_k\,\mathbb 1_{[a_k,b_k]}(t). (Step functions being dense in L^1(\mathbb R) is a standard fact taken as given at this course's level, the same way this course elsewhere uses dominated convergence informally rather than proving it from scratch.) Choose such a g with \|f-g\|_1<\varepsilon/2.

Each indicator function's own transform is an explicit sinc-shaped function: \widehat{\mathbb 1_{[a,b]}}(\omega)=\displaystyle\int_a^b e^{-i\omega t}\,dt=\dfrac{e^{-i\omega a}-e^{-i\omega b}}{i\omega}, which is O(1/|\omega|) and so tends to 0 as |\omega|\to\infty. A finite linear combination of functions that each tend to 0 also tends to 0, so \hat g(\omega)\to0 as well: pick M large enough that |\hat g(\omega)|<\varepsilon/2 for every |\omega|>M.

Section 5's own bound, |\hat h(\omega)|\le\|h\|_1 for every \omega, applied to h=f-g rather than to f itself, gives |\hat f(\omega)-\hat g(\omega)|\le\|f-g\|_1<\varepsilon/2 — for every \omega, not just large ones. Combining both pieces by the triangle inequality, for every |\omega|>M: |\hat f(\omega)|\le|\hat f(\omega)-\hat g(\omega)|+|\hat g(\omega)| <\frac\varepsilon2+\frac\varepsilon2=\varepsilon. Since \varepsilon>0 was arbitrary, this shows \hat f(\omega)\to0 as |\omega|\to\infty.

The formula is the T\to\infty limit of the Fourier series inversion already established for periodic functions, made precise by treating f as "periodic with infinite period." Restrict attention to f on [-T/2, T/2] and extend it periodically with period T; its complex Fourier series is f(t) \sim \sum_n c_n e^{in\omega_0 t} with \omega_0 = 2\pi/T and c_n = \frac{1}{T}\int_{-T/2}^{T/2} f(t)e^{-in\omega_0 t}\,dt. Multiplying and dividing by T, f(t) \sim \sum_{n=-\infty}^{\infty} \Big(\underbrace{\int_{-T/2}^{T/2} f(t)e^{-in\omega_0 t}\,dt}_{\to\ \hat f(n\omega_0)\text{ as }T\to\infty}\Big) e^{in\omega_0 t}\,\frac{\omega_0}{2\pi}. As T \to \infty: the spacing \omega_0 = 2\pi/T between consecutive harmonics shrinks to 0, so the discrete frequencies n\omega_0 sweep out the continuum, the bracketed quantity converges to \hat f(n\omega_0) (the periodic extension agrees with f on an interval growing to cover all of \mathbb{R}), and the sum over n — spaced \omega_0 apart and weighted by \omega_0 — converges to a Riemann sum for an integral over \omega: f(t) \;\longleftarrow\; \sum_n \hat f(n\omega_0)\,e^{in\omega_0 t}\,\frac{\omega_0}{2\pi} \;\longrightarrow\; \frac{1}{2\pi}\int_{-\infty}^{\infty} \hat f(\omega)\,e^{i\omega t}\,d\omega. The midpoint-at-a-jump behavior, rather than plain equality to f(t) everywhere, carries over unchanged from the periodic case, since it is a strictly local property (the Dirichlet convergence theorem's own localization principle) unaffected by letting the period grow.

This is the N\to\infty equality case of Bessel's Inequality, which holds because the trigonometric system \{1, \cos(n\omega_0 t), \sin(n\omega_0 t)\} is a complete orthogonal system on L^2([-T/2,T/2]): the N-th partial sum S_N (the orthogonal projection of f onto the span of the first N harmonics) converges to f in mean-square, \int_{-T/2}^{T/2} (f - S_N)^2\,dt \to 0 as N \to \infty.

Bessel's Inequality already gives, for every N, T\left[\left(\frac{a_0}{2}\right)^2 + \frac{1}{2}\sum_{n=1}^{N}(a_n^2+b_n^2)\right] = \int_{-T/2}^{T/2} S_N(t)^2\,dt \le \int_{-T/2}^{T/2} f(t)^2\,dt, with the gap between the two sides equal to \int_{-T/2}^{T/2}(f-S_N)^2\,dt (expand \int f^2 = \int (f-S_N)^2 + 2\int(f-S_N)S_N + \int S_N^2 and note the cross term vanishes, since S_N is exactly the orthogonal projection of f onto its own span). Completeness is precisely the statement that this gap shrinks to 0, so letting N \to \infty turns the inequality into the stated equality, dividing through by T.

Sanity check. For f(t) = \cos(\omega_0 t) itself (period T), the only nonzero coefficient is a_1 = 1, so the right side is \tfrac12(1)^2 = \tfrac12. The left side is the mean square of a cosine over a full period, \frac{1}{T}\int_{-T/2}^{T/2}\cos^2(\omega_0 t)\,dt = \tfrac12, matching exactly.

This is the T\to\infty limit of Parseval's Identity for Fourier Series, made precise by the same period-to-infinity argument used to derive the Fourier Transform Inversion Formula. Restrict f to [-T/2,T/2] and extend it periodically with period T; its complex Fourier coefficients are c_n = \frac1T\int_{-T/2}^{T/2}f(t)e^{-in\omega_0t}\,dt, with \omega_0=2\pi/T, and the periodic Parseval identity states \frac1T\int_{-T/2}^{T/2}|f(t)|^2\,dt = \sum_{n=-\infty}^{\infty}|c_n|^2. As T\to\infty, the bracketed quantity defining c_n converges to \hat f(n\omega_0) (the same convergence used in the Inversion Formula's own derivation), so c_n \approx \hat f(n\omega_0)/T. Substituting and multiplying both sides by T, \int_{-T/2}^{T/2}|f(t)|^2\,dt \approx \sum_{n=-\infty}^{\infty} \frac{|\hat f(n\omega_0)|^2}{T} = \sum_{n=-\infty}^{\infty} |\hat f(n\omega_0)|^2\,\frac{\omega_0}{2\pi}, using 1/T=\omega_0/(2\pi). The right side, spaced \omega_0 apart and weighted by \omega_0, is a Riemann sum for an integral over \omega; as T\to\infty, \omega_0\to0, the left side's domain grows to cover all of \mathbb R, and the sum converges to \int_{-\infty}^{\infty}|f(t)|^2\,dt = \frac1{2\pi}\int_{-\infty}^{\infty}|\hat f(\omega)|^2\,d\omega, the claimed identity.

Sanity check. For f(t)=e^{-t^2} (Gaussian, a=1), with \hat f(\omega)=\sqrt\pi\,e^{-\omega^2/4}: the left side is \int_{-\infty}^{\infty}e^{-2t^2}\,dt=\sqrt{\pi/2}. The right side is \frac1{2\pi}\int_{-\infty}^{\infty}\pi e^{-\omega^2/2}\,d\omega = \frac1{2\pi}\cdot\pi\sqrt{2\pi} = \sqrt{\pi/2}, matching exactly.

Write out the transform of the convolution as a double integral over \mathbb{R}^2 and swap the order of integration (justified by Fubini's theorem when f, g are absolutely integrable): \mathcal{F}[f*g](\omega) = \int_{-\infty}^{\infty}\left(\int_{-\infty}^{\infty} f(\tau)g(t-\tau)\,d\tau\right)e^{-i\omega t}\,dt = \int_{-\infty}^{\infty} f(\tau)\left(\int_{-\infty}^{\infty} g(t-\tau)e^{-i\omega t}\,dt\right)d\tau. Substitute u = t - \tau (t = u + \tau, dt = du) in the inner integral: \int_{-\infty}^{\infty} g(t-\tau)e^{-i\omega t}\,dt = \int_{-\infty}^{\infty} g(u)e^{-i\omega(u+\tau)}\,du = e^{-i\omega\tau}\int_{-\infty}^{\infty} g(u)e^{-i\omega u}\,du = e^{-i\omega\tau}\,\hat g(\omega). Substituting back, \mathcal{F}[f*g](\omega) = \int_{-\infty}^{\infty} f(\tau)\,e^{-i\omega\tau}\,\hat g(\omega)\,d\tau = \hat g(\omega)\int_{-\infty}^{\infty} f(\tau)e^{-i\omega\tau}\,d\tau = \hat g(\omega)\,\hat f(\omega), since \hat g(\omega) does not depend on \tau and factors out of the remaining integral, which is exactly \hat f(\omega).

Dual statement. The same computation run with the roles of "time" and "frequency" exchanged (using the inversion formula in place of the forward transform) shows multiplication in time transforms to a (scaled) convolution in frequency: \mathcal{F}[fg](\omega) = \frac{1}{2\pi}(\hat f * \hat g)(\omega) — the factor of \frac{1}{2\pi} tracks this convention's placement of that constant in the inversion formula rather than the forward transform.

Sampling f at spacing \Delta t is modeled by multiplying f(t) by a train of unit impulses spaced \Delta t apart, \sum_n \delta(t - n\Delta t). Multiplication in time is (by the Fourier convolution theorem's dual statement) convolution in frequency, and the Fourier transform of an impulse train is itself an impulse train, spaced \omega_s = 2\pi f_s = 2\pi/\Delta t apart in \omega. So sampling replaces \hat f(\omega) with infinitely many shifted copies of itself, \sum_k \hat f(\omega - k\omega_s), spaced \omega_s apart — the spectrum gets periodized.

Since \hat f is supported only on (-2\pi B, 2\pi B), the shifted copies are non-overlapping exactly when the spacing \omega_s = 2\pi f_s exceeds the width 4\pi B of that support, i.e. f_s > 2B. Under that condition, the original \hat f(\omega) can be recovered from the sampled spectrum by an ideal low-pass filter: multiply by a rectangular window that is 1 on (-2\pi B, 2\pi B) (or, more simply, on (-\omega_s/2, \omega_s/2), any gap between copies) and 0 elsewhere, which passes the central copy unchanged and zeroes out every shifted replica. Multiplying by that rectangle in frequency corresponds to convolving with its inverse transform in time, and the inverse transform of an ideal rectangular low-pass filter is exactly a \operatorname{sinc} function scaled to that cutoff — convolving the sample train with this \operatorname{sinc} reproduces f pointwise, which is exactly the stated reconstruction formula.

If instead f_s \le 2B, the shifted copies of \hat f overlap, and the overlapping parts of \hat f(\omega - k\omega_s) for different k add together in a way that cannot be undone by any filter — the periodized spectrum no longer determines the original \hat f uniquely, so no reconstruction formula, sinc-based or otherwise, can recover f from those samples in general.

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.

Write x and X as column vectors related by X=Fx, F_{kn}=e^{-2\pi ikn/N}, the matrix from this chapter's own DFT-as-a-matrix development. The left side is \sum_n|x_n|^2 = x^Hx, where x^H is x's conjugate transpose. The right side's numerator is \sum_k|X_k|^2 = X^HX = (Fx)^H(Fx) = x^HF^HFx. This chapter's own inverse-DFT theorem already establishes F^HF=NI (proved there directly from the orthogonality of the N-th roots of unity). Substituting, X^HX = x^H(NI)x = N\,x^Hx = N\sum_n|x_n|^2. Dividing both sides by N gives \frac1N\sum_k|X_k|^2 = \sum_n|x_n|^2, the stated identity, with no hypothesis beyond x being a length-N sequence — real or complex, since nothing in the derivation used x being real.

Sanity check. For x=(3,1) (N=2), the forward DFT (this chapter's own running example) gives X=(4,2). Left side: 3^2+1^2=10. Right side: \frac12(4^2+2^2)=\frac12(16+4)=\frac12(20)=10 — matching exactly, confirming both the identity and the \frac1N scaling it needs (dropping that factor would give 20, not 10).

Compute the j-th entry of Cv_k directly from the circulant structure: (Cv_k)_j = \sum_{m=0}^{N-1} C_{jm}\,(v_k)_m = \sum_{m=0}^{N-1} c_{(j-m)\bmod N}\,e^{i2\pi km/N}. Reindex with p = (j-m)\bmod N, so m \equiv j - p \pmod N; as m ranges over 0,\dots,N-1, p also ranges bijectively over 0,\dots,N-1. Since e^{i2\pi km/N} is periodic in m with period N, it may be evaluated using m \equiv j-p \pmod N directly: (Cv_k)_j = \sum_{p=0}^{N-1} c_p\, e^{i2\pi k(j-p)/N} = e^{i2\pi kj/N}\sum_{p=0}^{N-1} c_p\, e^{-i2\pi kp/N} = (v_k)_j \cdot \lambda_k. This holds for every j, so Cv_k = \lambda_k v_k: v_k is an eigenvector of C with eigenvalue \lambda_k, for every k.

Since \{v_0,\dots,v_{N-1}\} are N linearly independent vectors (they are, up to the shared 1/N scale factor, the columns of the invertible inverse-DFT matrix — invertible by DFT Invertibility above) and each is an eigenvector of C, they form a full eigenbasis: writing V for the matrix with these columns v_k (so V = N\cdot F^{-1}, and V^{-1} = \tfrac1N F where F is the forward-DFT matrix), this is exactly the matrix statement C = V\operatorname{diag}(\lambda_0,\dots,\lambda_{N-1})\,V^{-1} — the scale factor cancels between V and V^{-1}, so the diagonalization is identical whether stated with V or with the DFT matrices themselves. In particular, applying C to any vector reduces to an elementwise multiplication after a change of basis to the frequency domain — the linear-algebra fact underneath the discrete convolution theorem (circular convolution by c becomes multiplication by \operatorname{DFT}(c) after transforming).

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.

The exponential kernel factors as a product of a purely-m term and a purely-n term: e^{-i2\pi(km/M + ln/N)} = e^{-i2\pi km/M}\cdot e^{-i2\pi ln/N}. Substituting this into the defining double sum and pulling the m-independent factor e^{-i2\pi km/M} outside the inner sum over n (a finite sum, so reordering is unconditionally valid): X_{k,l} = \sum_{m=0}^{M-1} e^{-i2\pi km/M} \sum_{n=0}^{N-1} x_{m,n}\,e^{-i2\pi ln/N} = \sum_{m=0}^{M-1} e^{-i2\pi km/M}\,Y_{m,l}, which is exactly the stated two-stage computation: the inner sum over n is a length-N DFT applied to row m (producing Y_{m,l}), and the outer sum over m is a length-M DFT applied down column l of Y. Symmetric factoring — pulling out the n-independent factor first instead — gives the columns-then-rows order with the identical final sum X_{k,l}, confirming the order doesn't matter.

Consequence for computation. Rather than evaluating the double sum directly for every (k,l) pair, at O(M^2N^2) total cost, the 2-D DFT can be computed as M independent length-N 1-D DFTs (one per row) followed by N independent length-M 1-D DFTs (one per column). Using the FFT for each 1-D transform, this costs O(MN\log N) for the row pass plus O(MN\log M) for the column pass, i.e. O(MN\log(MN)) overall — the same divide-and-conquer speedup the 1-D FFT gets, applied once per dimension.

A full proof needs moment generating functions or characteristic functions, beyond this course's own scope. The intuition: \bar X_n is itself a sum of n independent pieces (each X_i/n), and summing many independent pieces smooths out any one piece's own irregular shape -- the same mechanism this course's own sums-of-independent-variables material already builds toward, pushed to its limit as n grows without bound.

The formula is the T\to\infty limit of the Fourier series inversion already established for periodic functions, made precise by treating f as "periodic with infinite period." Restrict attention to f on [-T/2, T/2] and extend it periodically with period T; its complex Fourier series is f(t) \sim \sum_n c_n e^{in\omega_0 t} with \omega_0 = 2\pi/T and c_n = \frac{1}{T}\int_{-T/2}^{T/2} f(t)e^{-in\omega_0 t}\,dt. Multiplying and dividing by T, f(t) \sim \sum_{n=-\infty}^{\infty} \Big(\underbrace{\int_{-T/2}^{T/2} f(t)e^{-in\omega_0 t}\,dt}_{\to\ \hat f(n\omega_0)\text{ as }T\to\infty}\Big) e^{in\omega_0 t}\,\frac{\omega_0}{2\pi}. As T \to \infty: the spacing \omega_0 = 2\pi/T between consecutive harmonics shrinks to 0, so the discrete frequencies n\omega_0 sweep out the continuum, the bracketed quantity converges to \hat f(n\omega_0) (the periodic extension agrees with f on an interval growing to cover all of \mathbb{R}), and the sum over n — spaced \omega_0 apart and weighted by \omega_0 — converges to a Riemann sum for an integral over \omega: f(t) \;\longleftarrow\; \sum_n \hat f(n\omega_0)\,e^{in\omega_0 t}\,\frac{\omega_0}{2\pi} \;\longrightarrow\; \frac{1}{2\pi}\int_{-\infty}^{\infty} \hat f(\omega)\,e^{i\omega t}\,d\omega. The midpoint-at-a-jump behavior, rather than plain equality to f(t) everywhere, carries over unchanged from the periodic case, since it is a strictly local property (the Dirichlet convergence theorem's own localization principle) unaffected by letting the period grow.

(\Leftarrow) n independent eigenvectors give A = PDP^{-1}. Suppose v_1, \dots, v_n are linearly independent eigenvectors of A, with Av_i = \lambda_i v_i. Let P be the matrix with these vectors as its columns, and let D = \operatorname{diag}(\lambda_1, \dots, \lambda_n). Multiplying A into P column by column, AP = A\begin{bmatrix} v_1 & \cdots & v_n \end{bmatrix} = \begin{bmatrix} Av_1 & \cdots & Av_n \end{bmatrix} = \begin{bmatrix} \lambda_1 v_1 & \cdots & \lambda_n v_n \end{bmatrix}. Multiplying P by D on the right scales each column of P by the matching diagonal entry of D, producing the very same matrix: PD = \begin{bmatrix} v_1 & \cdots & v_n \end{bmatrix} \operatorname{diag}(\lambda_1,\dots,\lambda_n) = \begin{bmatrix} \lambda_1 v_1 & \cdots & \lambda_n v_n \end{bmatrix}. So AP = PD. Because P's columns are n linearly independent vectors in \mathbb{R}^n, P is invertible, and right-multiplying both sides by P^{-1} gives A = PDP^{-1}.

(\Rightarrow) A = PDP^{-1} gives n independent eigenvectors. Suppose A = PDP^{-1} with P invertible and D = \operatorname{diag}(\lambda_1, \dots, \lambda_n). Then AP = PD, and reading that equation column by column exactly as above shows Av_i = \lambda_i v_i, where v_i is the i-th column of P. Each v_i is nonzero — a zero column would make P singular — so v_1,\dots,v_n are eigenvectors of A. Since P is invertible, its columns are linearly independent, which produces the needed n independent eigenvectors.

Sanity check: take A = \begin{bmatrix} 4 & 1 \\ 0 & 3 \end{bmatrix}, upper triangular, so its eigenvalues sit on the diagonal: \lambda_1 = 4, \lambda_2 = 3. Solving (A - 4I)v = 0 gives eigenvector v_1 = (1,0), and (A-3I)v = 0 gives v_2 = (1,-1). These two are not scalar multiples of each other, so they're independent, and the theorem guarantees A = PDP^{-1} with P = \begin{bmatrix} 1 & 1 \\ 0 & -1 \end{bmatrix} and D = \begin{bmatrix} 4 & 0 \\ 0 & 3 \end{bmatrix} — which a direct multiplication PDP^{-1} confirms reproduces A.

Compute the j-th entry of Cv_k directly from the circulant structure: (Cv_k)_j = \sum_{m=0}^{N-1} C_{jm}\,(v_k)_m = \sum_{m=0}^{N-1} c_{(j-m)\bmod N}\,e^{i2\pi km/N}. Reindex with p = (j-m)\bmod N, so m \equiv j - p \pmod N; as m ranges over 0,\dots,N-1, p also ranges bijectively over 0,\dots,N-1. Since e^{i2\pi km/N} is periodic in m with period N, it may be evaluated using m \equiv j-p \pmod N directly: (Cv_k)_j = \sum_{p=0}^{N-1} c_p\, e^{i2\pi k(j-p)/N} = e^{i2\pi kj/N}\sum_{p=0}^{N-1} c_p\, e^{-i2\pi kp/N} = (v_k)_j \cdot \lambda_k. This holds for every j, so Cv_k = \lambda_k v_k: v_k is an eigenvector of C with eigenvalue \lambda_k, for every k.

Since \{v_0,\dots,v_{N-1}\} are N linearly independent vectors (they are, up to the shared 1/N scale factor, the columns of the invertible inverse-DFT matrix — invertible by DFT Invertibility above) and each is an eigenvector of C, they form a full eigenbasis: writing V for the matrix with these columns v_k (so V = N\cdot F^{-1}, and V^{-1} = \tfrac1N F where F is the forward-DFT matrix), this is exactly the matrix statement C = V\operatorname{diag}(\lambda_0,\dots,\lambda_{N-1})\,V^{-1} — the scale factor cancels between V and V^{-1}, so the diagonalization is identical whether stated with V or with the DFT matrices themselves. In particular, applying C to any vector reduces to an elementwise multiplication after a change of basis to the frequency domain — the linear-algebra fact underneath the discrete convolution theorem (circular convolution by c becomes multiplication by \operatorname{DFT}(c) after transforming).

This is the N\to\infty equality case of Bessel's Inequality, which holds because the trigonometric system \{1, \cos(n\omega_0 t), \sin(n\omega_0 t)\} is a complete orthogonal system on L^2([-T/2,T/2]): the N-th partial sum S_N (the orthogonal projection of f onto the span of the first N harmonics) converges to f in mean-square, \int_{-T/2}^{T/2} (f - S_N)^2\,dt \to 0 as N \to \infty.

Bessel's Inequality already gives, for every N, T\left[\left(\frac{a_0}{2}\right)^2 + \frac{1}{2}\sum_{n=1}^{N}(a_n^2+b_n^2)\right] = \int_{-T/2}^{T/2} S_N(t)^2\,dt \le \int_{-T/2}^{T/2} f(t)^2\,dt, with the gap between the two sides equal to \int_{-T/2}^{T/2}(f-S_N)^2\,dt (expand \int f^2 = \int (f-S_N)^2 + 2\int(f-S_N)S_N + \int S_N^2 and note the cross term vanishes, since S_N is exactly the orthogonal projection of f onto its own span). Completeness is precisely the statement that this gap shrinks to 0, so letting N \to \infty turns the inequality into the stated equality, dividing through by T.

Sanity check. For f(t) = \cos(\omega_0 t) itself (period T), the only nonzero coefficient is a_1 = 1, so the right side is \tfrac12(1)^2 = \tfrac12. The left side is the mean square of a cosine over a full period, \frac{1}{T}\int_{-T/2}^{T/2}\cos^2(\omega_0 t)\,dt = \tfrac12, matching exactly.

This is the N\to\infty equality case of Bessel's Inequality, which holds because the trigonometric system \{1, \cos(n\omega_0 t), \sin(n\omega_0 t)\} is a complete orthogonal system on L^2([-T/2,T/2]): the N-th partial sum S_N (the orthogonal projection of f onto the span of the first N harmonics) converges to f in mean-square, \int_{-T/2}^{T/2} (f - S_N)^2\,dt \to 0 as N \to \infty.

Bessel's Inequality already gives, for every N, T\left[\left(\frac{a_0}{2}\right)^2 + \frac{1}{2}\sum_{n=1}^{N}(a_n^2+b_n^2)\right] = \int_{-T/2}^{T/2} S_N(t)^2\,dt \le \int_{-T/2}^{T/2} f(t)^2\,dt, with the gap between the two sides equal to \int_{-T/2}^{T/2}(f-S_N)^2\,dt (expand \int f^2 = \int (f-S_N)^2 + 2\int(f-S_N)S_N + \int S_N^2 and note the cross term vanishes, since S_N is exactly the orthogonal projection of f onto its own span). Completeness is precisely the statement that this gap shrinks to 0, so letting N \to \infty turns the inequality into the stated equality, dividing through by T.

Sanity check. For f(t) = \cos(\omega_0 t) itself (period T), the only nonzero coefficient is a_1 = 1, so the right side is \tfrac12(1)^2 = \tfrac12. The left side is the mean square of a cosine over a full period, \frac{1}{T}\int_{-T/2}^{T/2}\cos^2(\omega_0 t)\,dt = \tfrac12, matching exactly.