# Lecture Notes
**[Josh's Notes for Lecture 2](/Lecture_2.pdf)**
#Why the Fourier decomposition is possible?
A Fourier series is a function of the form
$$\sum_{n=-\infty}^\infty a_n e^{inx}$$ or $$\sum_{n=-\infty}^\infty b_n \cos(n x) + c_n \sin (n x),$$
depending on one's taste for the imaginary. The rumor on the street is that any periodic function (well, any nice one) can be expressed as a Fourier series: you hand me a function $f:[0,2\pi]\rightarrow \mathbb{C}$ and I hand you a list of real numbers $\{b_0,c_0,b_1,c_1,b_2,c_2,b_3,c_3,\dots\}$ such that
$$f(x) = \sum_{n=-\infty}^\infty b_n \cos(n x) + c_n \sin (n x).$$
If this exchange is always possible, there must be at least as many different lists of real numbers as there are nice periodic functions. So how many are there of each?
Infinity, of course. So to perform a meaningful check that the set of nice periodic functions is the same size as the set of lists of real numbers, we need a more refined notion of a size of a set than just giving its number of elements, or saying that it is infinite. We say that two sets have the same cardinality (our new word for size) if we can pair off their elements, giving a perfect matching between the sets.
For example, the open interval $(-\pi,\pi)$ has the same cardinality as $\mathbb R$. To see this, take the interval and bend it into a semicircle, then balance it on the real line. To find the point on the real line corresponding to a given number in the interval/on the semicircle, $\theta \in (-\pi,\pi)$, draw the straight line emanating from the centre of the circle at an angle $\theta$ with the vertical; it hits $\theta$ on the semicircle and its partner $x$ on the real line. Explicitly, the map takes $\theta \mapsto \tan \theta$.
There are, however, fewer natural numbers in $\mathbb N = \{1,2,3,\dots\}$ than there are real numbers in $\mathbb R$. Suppose to the contrary that it is possible to list the real numbers, or even just those in the interval $(0,1)$. Write that list down in binary, forming a big block extending infinitely downward (each row is a number), and to the right (the binary digits of each number). Read off the digits on the diagonal to get a number $x=0.010100110101110101011\dots$. Now toggle every digit of that number to get a new number $y$, say $0.101011001010001010100\dots$. This number $y$ is not anywhere on the list--it disagrees with the $n^{th}$ number on the list in its $n^{th}$ digit. Hence the list was incomplete.
A set is called countable if it has the same cardinality as the natural numbers, if its elements can be placed in an infinite list. The real numbers, we've just seen, are not countable.
Cardinality holds some surprises, though. For example, there are as many pairs of natural numbers as there are natural numbers; the set $\mathbb{N}\times\mathbb{N}$ is countable. They can be enumerated by following the zig-zag path through the cartesian grid of pairs below.
What is the cardinality of the set of periodic functions on $[-\pi,\pi]$? If we look at the set of all functions, where we demand no continuity or regularity or relationship between function values at nearby points, then there are rather many. The cardinality is $\mathbb R^{\mathbb R}$, which turns out to have the same size as $2^{\mathbb R}$, the set of subsets of the real numbers. On the homework, we will show that the set of lists of real numbers (ie, possible fourier series) has the same cardinality as $\mathbb R$, and that $2^{\mathbb R}$ has a larger cardinality. There just aren't enough fourier series that every arbitrary function could have its own. Luckily, we're not interested in most of those ugly beasts. We'd by happy knowing:
What is the cardinality of the set of *continuous* periodic functions on $[-\pi,\pi]$? To describe a continuous function $f:[-\pi,\pi]\rightarrow \mathbb R$, make a list of its values at the dyadic points $f(n\pi/2^m)$ as follows:
$$(f(0),f(-\pi),f(\pi),f(-\frac{\pi}{2}),f(\frac{\pi}{2}),f(-\frac{3\pi}{4}),f(-\frac{\pi}{4}),f(\frac{\pi}{4}),f(\frac{3\pi}{4}),\dots)$$
When you start graphing $f$ from the list above, drawing dots at each of the recorded values, a pointillist picture begins to emerge. Since $f$ is continuous, dense pointillism is a faithful representation of the function (more precisely, to recover $f(x)$, take a limit of dyadic numbers which approach $f$, and consider the limit of their images). Thus a continuous function on the interval can be described by a list of real numbers, just like a fourier series can be. Hence there are as many fourier series as there are continuous functions, and there is a chance that each continuous function could have its own. Cardinality is no obstruction, then: it is not a priori impossible that every continuous function could have its own fourier series.
#Why Fourier decomposition is plausible?
To show that Fourier series is plausible, let us consider some arbitrary trignometric functions and see if it is possible to express them as the sum of sines and cosines:
$1.\quad\sin^2(x) = ?$
Based on the double angle formula,
$$\cos(2x) = 1 - 2 \sin^2(x)$$
Rearranging,
$$\sin^2(x) = \frac{1-\cos(2x)}{2}$$
$2.\quad\sin(2x)\cdot\cos(2x) = ?$
Based on the double angle formula,
$$\qquad\sin(2x) = 2\sin(x)\cos(x)$$
Rearranging,
$$\begin{array}{ccl}
\sin(2x)\cdot\cos(x) & = & [2\sin(x)\cos(x)]\cdot\cos(x)\\
& = & 2 \sin(x) [ 1 - \sin^2(x)]\\
& = & 2\sin(x) - 2\sin^3(x)\\
\end{array}$$
Based on the triple angle formula,
$$\sin(3x) = 3\sin(x) - 4\sin^3(x)$$
Rearranging,
$$\sin^3(x) = \frac{3\sin(x)-\sin(3x)}{4}$$
Substituting back in the former equation, we get
$$
\begin{array} {ccl}
\sin(2x) & = & 2\sin(x) - 2 [\frac{3\sin(x)-\sin(3x)}{4}]\\
& = & \frac{1}{2}\sin(x) + \frac{1}{2}\sin(3x)\\
\end{array}
$$
Thus, we see that both these functions could be expressed as sums of sines and cosines. It is possible to show that every product of trignometric functions can be expressed as a sum of sines and cosines:
$$
\begin{array}{ccl}
e^{i\theta} & = & \cos \theta + i \sin \theta\\
e^{-i\theta} & = & \cos \theta - i \sin \theta\\
\end{array}
$$
Solving for $\cos \theta$ and $\sin \theta$
$$
\begin{array}{ccl}
\cos \theta & = & \frac{1}{2}e^{i\theta} + \frac{1}{2}e^{-i\theta}\\
\sin \theta & = & \frac{1}{2i}e^{i\theta} - \frac{1}{2i}e^{-i\theta}\\
\end{array}
$$
It is easy to show that any product of cosines and sines can be expressed as the product of exponentials which will reduce to a sum of sines and cosines.
As a final test to see if the Fourier series really could exist for any periodic function, we consider a periodic function with a sharp peak as shown below
If it is possible to approximate the above function using a sum of sines and cosines, then it can be argued that *any* continuous periodic function can be expressed in a similar way. This is because any function could be expressed as a number of peaks at every position.
It turns out that the above function can be approximated as the difference of two cosines, namely, $\cos^{2n}(x) + cos^{2n+1}(x)$
 
Summing these two functions we get the following:
#Why does the Fourier decomposition actually work?
##Initial Hypothesis
Now, to prove that the Fourier series is indeed true, we begin with the following hypothesis:
Let $f : \mathbb I \rightarrow \mathbb C$ be a continuous, periodic function where $I$ is some time interval(period of the function). Then it can be expressed as :
$$
\begin{array}{ccl}
f & = & \Sigma a_n \, e^{inx}\\
& = & a_0 + \Sigma a_n\cos nx + \Sigma b_n\sin nx\\
\end{array}
$$
##Definition of Inner Product of Functions
We begin proving this hypothesis by considering that any function on the right-hand side of our hypothesis is uniquely defined by the co-efficients of the terms $a_0$ through $a_n$ and $b_1$ through $b_n$. This can be taken to mean that every function is really a vector in a $2n+1$-dimensional 'Hilbert space'.(*perhaps someone can clarify this?*)
We now proceed to define certain operations on these functions in Hilbert space. One operation that will be particularly useful is that of the inner product of two functions:
$$
\begin{array}{ccl}
(f,g) & = & \int_0^{2\pi} f \, g \,dx\\
\mid f \mid ^2 = (f, f) & = & \int_0^{2\pi} f^2 \,dx\\
\end{array}
$$
This is the inner product of 2 real-number functions. For a function on complex numbers, the above definition must be altered as follows:
$$
\begin{array}{ccl}
(f,g) & = & \int_0^{2\pi} f \,\bar g \,dx\\
\mid f \mid ^2 = (f, f) & = & \int_0^{2\pi} f^2 \,dx\\
\end{array}
$$
*Note: These are purely definitions, and we are defining the inner product to ensure that the inner product of $f$ and $f$, called the *norm* of $f$, is a real number.*
##Basis Vectors of the Hilbert Space
The basis vectors of this Hilbert space are taken as follows:
basis vectors, $f_n = \frac{1}{\sqrt{2\pi}}e^{inx}$
Any basis vectors could conceivably have been used, so long as they are orthonormal. (*Note: These particular basis vectors are chosen to prove that Fourier series exists*)
To prove the orthonormality of the basis vectors, we compute:
$$
\begin{array}{ccl}
(f_n,f_m) & = & \int_0^{2\pi} \, \frac{1}{\sqrt{2\pi}} \, e^{inx} \, \bar {\frac{1}{\sqrt{2\pi}} \, e^{inx}} \, dx\\
& = & \frac{1}{2\pi} \, \int_0^{2\pi} \, e^{i(n-m)x} \, dx \\
\end{array}
$$
The exponential can be expanded using $e^{ikx} = \cos kx + i \sin kx$. Then, integrating, we get the following:
$$
\begin{array}{ccl}
n = m \Rightarrow (f_n,f_m) & = & 1\\
n \neq m \Rightarrow (f_n,f_m) & = & 0\\
\end{array}
$$
which is the condition of orthonormality (the vectors are perpendicular and each has a length of 1 unit).
##Determining Coefficients of the Basis vectors
In any vector space, the inner product of a vector and its basis vector gives the coefficient. For example, consider a 2-dimensional vector as shown below:
The above vector $\vec v$ can be expressed in terms of the basis vectors $\vec e_1$ and $\vec e_2$ as follows:
$$
\begin{array}{ccl}
\vec v & = & a_1 \, \vec e_1 + a_2 \, \vec e_2\\
& = & a_1 \, \left( \begin{array}{c}1\\0\end{array} \right) + a_2 \, \left( \begin{array}{c}0\\1\end{array} \right)\\
& = & \left( \begin{array}{c}a_1\\a_2\end{array} \right) \\
\end{array}
$$
So,
$$
\begin{array}{ccl}
\vec v . \vec e_1 & = & a_1\\
\vec v . \vec e_2 & = & a_2\\
\end{array}
$$
Extending this principle to the case of an n-dimensional vector:
Let $f$ be the periodic function expressed as $f= \Sigma a_n \frac{1}{\sqrt{2\pi}} \, e^{inx} = \Sigma a_n \, f_n$ where $a_n \in \mathbb C$ and $f_n$ are the basis vectors.
Inner product of the vector (in this case the function $f$) with the some basis vector $f_m$ is:
$$
\begin{array}{ccl}
(f, f_m) & = & \left( \Sigma a_n\,f_n , f_m \right)\\
& = & \Sigma a_n\,\left(f_n , f_m \right)\\
\end{array}
$$
Due to orthonormality of basis vectors, the inner product in the right-hand side of the above equation is $0$ for all terms except $n = m$.
Thus,
$$ (f, f_m) = a_m $$
Using the definition of the inner product,
$$ a_m = \int_0^{2\pi} \, f \, \frac{1}{\sqrt{2\pi}} \, e^ {-imx} \, dx $$
This is the common definition for the terms of the Fourier series.
##The Fourier series reproduces $f$
It is important to note at this point that we have simply expressed the periodic function $f$ in terms of a sum of arbitrary orthonormal vectors $f_n$. We haven't quite shown yet that the sum of orthonormal vectors actually completely represent $f$. Put in another way, there could be some components of $f$ that are not described by the vectors $f_n$.
**Theorem** Let $f:I\rightarrow \mathbb C$ be a continuous, periodic function with Fourier coefficients $a_n$, and suppose that the sum
$$\sum_{n=-\infty}^\infty a_n e^{inx}$$ converges for all $x$. Then
$$f(x) = \sum_{n=-\infty}^\infty a_n e^{inx}.$$
*Proof.*
Consider the difference $g:=f-\sum_{n=-\infty}^\infty a_n e^{inx}$.
****inner product with delta functions
#Why the Fourier decomposition is useful?
Applications will be covered on Monday July 5, 2010.