\documentclass[12pt,a4paper]{article}
\usepackage{amsmath,amsxtra,amsthm,amssymb,makeidx,graphics,xr}
\theoremstyle{plain}
\externaldocument{Topic}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheoremstyle{citing}{3pt}{3pt}{\itshape}{0pt}{\bfseries}%
{.}{ }{\thmnote{#3}}\theoremstyle{citing}\newtheorem*{varthm}{}
\DeclareMathOperator{\var}{var}
\DeclareMathOperator{\Cl}{Cl}
\DeclareMathOperator{\Int}{Int}
\renewcommand{\emptyset}{\varnothing}
\theoremstyle{remark}
\newtheorem{question}[theorem]{Exercise}
\begin{document}
\title{Proofs for some results in\\Topics in Analysis}
\author{T.~W.~K\"{o}rner}
\maketitle
\vspace{5\baselineskip}
\begin{footnotesize}
{\bf Small print} These proofs are offered on an `as is' basis.
I will not necessarily give the same proofs or use
the same notation in the lectures. I very much hope
that students will only consult these notes if they
cannot provide their own proofs.  These
notes are intended for home use (if at all) and not
as a means of following the live lectures.

There are certainly many small errors and quite likely
some big ones.
I should {\bf very much} appreciate being told
of any corrections or possible improvements
to these notes.

These notes are written in
\LaTeXe\ and should be available
in tex, ps, pdf and dvi format
from my home page
\begin{center}
{\bf http://www.dpmms.cam.ac.uk/\~{}twk/}
\end{center}
\end{footnotesize}
\newpage
\begin{proof}[Solution for Exercise~\ref{E;Balls}]
  (i) If $y\in B(x,r)$ then
$\delta=r-d(x,y)>0$. Now observe that, if $z\in B(y,\delta)$,
then 
\[d(x,z)\leq d(x,y)+d(y,z)<d(y,x)+\delta<r.\]

(ii) If $y_{n}\in\bar{B}(x,r)$ and $y_{n}\xrightarrow[d]{}y$,
then
\[d(x,y)\leq d(x,y_{n})+d(y_{n},y)\leq r+d(y_{n},y)\rightarrow r,\]
so $d(x,y)\leq r$ and $y\in \bar{B}(x,r)$.

(iii) Suppose that $X\setminus E$ is not open. Then there
is a point $y\notin E$ such that $B(y,r)\cap E\neq \emptyset$
whenever $r>0$.
Choose $y_{n}\in B(y,1/n)\cap E$. We have $y_{n}\in E$,
$y_{n}\xrightarrow[d]{}y$ and yet $y\notin E$. Thus $E$ is not closed.

(iii) Suppose that $X\setminus E$ is not closed. Then there
is a sequence $y_{n}\notin E$ with
$y_{n}\xrightarrow[d]{}y$ and yet $y\in E$.
Thus $B(y,r)\nsubseteq E$ for all $r>0$ and $E$ is not open.
\end{proof}
\begin{proof}[Solution for Exercise~\ref{E;convergent Cauchy}]
  Suppose $x_{n}\xrightarrow[d]{}x$.
Let $\epsilon>0$. We can find an $N$ such that
$d(x_{n},x)<\epsilon/2$ for all $n\geq N$. It follows that
\[d(x_{n},x_{m})\leq d(x_{n},x)+d(x,x_{m})
<\epsilon/2+\epsilon/2=\epsilon\]
for all $n,\,m\geq N$.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;fast Cauchy}]
(i) Let $\epsilon>0$. We  can find an $N$
such that $d(x_{n},x_{m})<\epsilon/2$ for $m,\,n\geq N$.
We can now find a $J$ such that $n(J)\geq N$ and
$d(x_{n(J)},x)<\epsilon/2$. We now observe that, if
$m\geq N$, we get
\[d(x_{m},x)\leq d(x_{m},x_{n(J)})+d(x_{n(J)},x)
<\epsilon/2+\epsilon/2=\epsilon.\]

(ii) If $x_{n}$ is Cauchy, we can find a strictly increasing
sequence $n(j)$ with
\[d(x_{n},x_{m})<\epsilon(j)\]
for all $n,\, m\geq n(j)$. By hypothesis, $x_{n(j)}$ converges
as $j\rightarrow\infty$. Part~(i) now tells us 
that the sequence $x_{n}$
converges.
\end{proof} 
\begin{proof}[Solution to Exercise~\ref{E;closed Cauchy}]
(i) Observe that, whenever $x,\,y,\,z\in Y$,
\begin{gather*}
d_{Y}(x,y)=d(x,y)\geq 0,\\
d_{Y}(x,y)=0\Leftrightarrow d(x,y)=0\Leftrightarrow x=y,\\
d_{Y}(x,y)=d(x,y)=d(y,x)=d_{Y}(y,x),\\
d_{Y}(x,y)+d_{Y}(y,z)=d(x,y)+d(y,z)\geq d(x,z)
=d_{Y}(x,z).
\end{gather*}

(ii) Suppose the sequence $x_{n}$ is Cauchy in $(Y,d_{Y})$.
Then the sequence $x_{n}$ is Cauchy in $(X,d)$, so
$x_{n}\rightarrow x$ for some $x\in X$. But $Y$ is closed,
so $x\in Y$ and $x_{n}\rightarrow x$ in $(Y,d_{Y})$.

(iii) If $y_{n}\in Y$ and $y_{n}\rightarrow y$ in $(X,d)$,
then $y_{n}$ is Cauchy in $(X,d)$, so Cauchy in $(Y,d_{Y})$, so
$y_{n}\rightarrow z$ in $(Y,d_{y})$ for some $z\in Y$.
It follows that $y_{n}\rightarrow z$ in $(X,d)$ so,
by the uniqueness of limits, $y=z\in Y$. Thus $Y$ is closed.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Euclid} for $n=2$] 
We prove the
case when $n=2$. Suppose
that ${\mathbf x}_{n}=(x_{n},y_{n})$
is Cauchy in ${\mathbb R}^{2}$. Since
\[|x_{n}-x_{m}|\leq \|{\mathbf x}_{n}-{\mathbf x}_{m}\|,\]
$x_{n}$ is Cauchy in ${\mathbb R}$,
and by our 1A theorem (Theorem~\ref{T;junior Cauchy})
converges to a limit $x$.
Similarly $y_{n}$ converges to a limit $y$ in ${\mathbb R}$.
If we set ${\mathbf x}=(x,y)$, then
\[\|{\mathbf x}_{n}-{\mathbf x}\|\leq |x_{n}-x|+|y_{n}-y|
\rightarrow 0\]
as $n\rightarrow\infty$.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Bolzano}]
  We prove the case $m=2$.
Write ${\mathbf x}_{n}=(x_{n},y_{n})$. We have
that $x_{n}$ is a bounded sequence in ${\mathbb R}$ and
so (by the 1A result) there exists an $x\in{\mathbb R}$
and a sequence $n(j)\rightarrow\infty$ such that
$x_{n(j)}\rightarrow x$ as $j\rightarrow\infty$. 
Now  $y_{n(j)}$ is a bounded sequence 
in ${\mathbb R}$ and
so there exists a $y\in{\mathbb R}$
and a sequence $j(k)\rightarrow\infty$
such that $y_{n(j(k))}\rightarrow y$
as $k\rightarrow\infty$. Now set $r(k)=n(j(k))$
and ${\mathbf x}=(x,y)$ to obtain
$r(k)\rightarrow\infty$
and ${\mathbf x}_{r(k)}\rightarrow{\mathbf x}$
as $k\rightarrow\infty$. 
\end{proof}
\begin{proof}[Theorem~\ref{T;closed bounded}]
(i) Since ${\mathbf x}_{r}\in E$, we know that the
${\mathbf x}_{r}$ form a bounded sequence and so
have a convergent subsequence 
${\mathbf x}_{r(k)}\rightarrow{\mathbf x}$.
Since $E$ is closed, ${\mathbf x}\in E$.

(ii) If $E$ is not bounded, we can find ${\mathbf x}_{r}\in E$ 
with $\|{\mathbf x}_{r+1}\|\geq \|{\mathbf x}_{r}\|+1$.
If $r>s$  
\[\|{\mathbf x}_{r}-{\mathbf x}_{s}\|\geq
\|{\mathbf x}_{r}\|-\|{\mathbf x}_{s}\|\geq 1,\]
so no subsequence can be Cauchy and so no subsequence can converge.

If  $E$ is not closed, we can find ${\mathbf x}_{r}\in E$
and ${\mathbf x}\notin E$ such that 
${\mathbf x}_{r}\rightarrow{\mathbf x}$. Any subsequence
of ${\mathbf x}_{r}$ will still converge to  ${\mathbf x}\notin E$.
\end{proof}
\begin{proof}[Solution to Exercise~\ref{E;topological continuity}]
(i) Suppose $f^{-1}(U)$ is open whenever $U$ is. 
If $x\in X$, $\epsilon>0$, we know that $B(f(x),\epsilon)$
is an open subset of $Y$, so $f^{-1}\big(B(f(x),\epsilon)\big)$
is an open subset of $X$ containing $x$. Thus we can find a 
$\delta>0$ with 
$B(x,\delta)\subseteq f^{-1}\big(B(f(x),\epsilon)\big)$.
In other words,
\[z\in B(x,\delta)\Rightarrow f(z)\in B(f(x),\epsilon).\]
Thus $f$ is continuous.

Conversely, if $f$ is continuous and $U$ open in $Y$,
then, given $x\in X$ with $f(x)\in U$, we can find a
$\delta>0$ such that $B(f(x),\delta)\subseteq U$
and an $\epsilon>0$ such that
\[z\in B(x,\delta)\Rightarrow f(z)\in B(f(x),\epsilon).\]
Thus $B(x,\epsilon)\subseteq f^{-1}(U)$. We have shown
that $f^{-1}(U)$ is open.

(ii) Complementation. If $f^{-1}(F)$ is closed for
all $F$ closed then
\[U\ \text{open}\Rightarrow Y\setminus U\ \text{closed}
\Rightarrow X\setminus f^{-1}(U)=f^{-1}(Y\setminus U)
\ \text{closed}
\Rightarrow f^{-1}(U)\ \text{open},\]
so $f$ is continuous.

The converse is proved similarly.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;distance closed}]
  If $d(x,A)=0$, then we can find
$x_{n}\in A$ such that $d(x_{n},x)\leq 1/n$, so $x_{n}\rightarrow x$. 
But $A$ is closed, so $x\in A$.

Let $x,\,y\in X$. Given $\epsilon>0$, we can find $a\in A$ such
that $d(x,a)\leq d(x,A)+\epsilon$. Now
\[d(y,A)\leq d(y,a)\leq d(x,y)+d(x,a)\leq d(x,y)+d(x,A)+\epsilon.\]
Since $\epsilon$ was arbitrary, 
\[d(y,A)\leq  d(x,y)+d(x,A).\]
The same argument shows that $d(x,A)\leq d(x,y)+d(y,A)$ so
\[|d(x,A)-d(y,A)|\leq d(x,y).\]
This shows that the map $x\mapsto d(x,A)$ is continuous.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Compact image}]
Suppose that $y_{n}\in f(E)$. Then $y_{n}=f(x_{n})$
for some $x_{n}\in E$. By the Bolzano--Weierstrass
property, we can find $n(j)\rightarrow\infty$ and $x\in E$
such that $x_{n(j)}\rightarrow x$ as $j\rightarrow\infty$. 
Now, by continuity,
\[y_{n(j)}=f(x_{n(j)})\rightarrow f(x)\in f(E)\]
so we are done.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;compact bound}]
 By Theorem~\ref{T;Compact image}, $f(E)$ is closed and
bounded. Since $f(E)$ is non-empty, it has a supremum 
(see 1A), $\alpha$, say. By the definition of the
supremum, we can find ${\mathbf a}_{n}\in E$
such that 
\[\alpha-1/n\leq f({\mathbf a}_{n})\leq \alpha.\]
By the Bolzano--Weierstrass
property, we can find $n(j)\rightarrow\infty$
and ${\mathbf a}\in E$
such that ${\mathbf a}_{n(j)}\rightarrow{\mathbf a}$ 
as $j\rightarrow\infty$. We have
$f({\mathbf a}_{n(j)})\rightarrow f({\mathbf a})$,
so $f({\mathbf a})=\alpha$. Thus
\[f({\mathbf a})\geq f({\mathbf x})\]
for all ${\mathbf x}\in E$. We find ${\mathbf b}$
in a similar manner.
\end{proof}     
\begin{proof}[Proof of Theorem~\ref{T;Fundamental Algebra}]
Let $n\geq 1$.
Suppose $P(z)=\sum_{j=0}^{n}a_{j}z^{j}$ where, without
loss of generality, we take $a_{n}=1$. 

If $R\geq 2(2+\sum_{j=0}^{n-1}|a_{j}|)$,
then, whenever $|z|\geq R$, we have
\begin{align*}
|P(z)|&\geq |z|^{n}- \sum_{j=0}^{n-1}|a_{j}||z|^{j}\\
&=|z|^{n}\left(1-\sum_{j=0}^{n-1}|a_{j}||z|^{j-n}\right)\\
&\geq |z|^{n}/2>|a_{0}|.
\end{align*}

Since $\bar{D}_{R}=\{z\in{\mathbb C}:|z|\leq R\}$ is closed
and bounded (that is to say compact) and the map $z\mapsto|P(z)|$
is continuous, $|P|$ attains a minimum on $\bar{D}_{R}$
at a point $z_{0}$, say. By the previous paragraph,
$|z_{0}|<R$ (since $|P(z_{0})|\leq |P(0)|)$ and so
we can find a $\delta>0$ such that $|P(z)|\geq |P(z_{0})|$
for all $|z-z_{0}|<\delta$.

By replacing $P(z)$ by $P(z-z_{0})$, we may assume
that $z_{0}=0$ so that $|P(z)|\geq |P(0)|$
for all $|z|<\delta$. If $a_{0}=0$, then we have
$P(0)=0$ and we are done.

We show that the assumption that $a_{0}\neq 0$ leads to 
a contradiction. Observe that
\[P(z)=\sum_{j=m}^{n}a_{j}z^{j}+a_{0}
=a_{0}\left(1-\sum_{j=m}^{n}b_{j}z^{j}\right)\]
with $a_{m}\neq 0$ and so $b_{m}\neq 0$. Choose $\theta$ 
so that $b_{m}\exp(im\theta)$ is real and positive.
Then
\[|P(\eta\exp i\theta)|\leq |a_{0}|-|b_{m}|\eta^{m}
+|a_{0}|\eta^{m+1}\sum_{j=m}^{n}|b_{j}|
\leq |a_{0}|-|b_{m}|\eta^{m}/2<|P(0)|\]
when $\eta$ is strictly positive and sufficiently
small. We have the required
contradiction.
\end{proof}
\begin{proof}[Solution to Exercise~\ref{E;roots}]
(i) Let $S(m)$ be the statement that, if 
$P$ is a polynomial of degree $n$ with $n\leq m$
and $a\in{\mathbb C}$,
then there exists a polynomial $Q$ of degree $n-1$ and an
$r\in{\mathbb C}$ such that
\[P(z)=(z-a)Q(z)+r.\]

Suppose that $S(m)$ is true and $P$ is a polynomial of degree
$m+1$. Then $P(z)=Az^{m+1}+Q(z)$ where $A\neq 0$ and $Q$
is a polynomial of degree at most $m$. We have
\[P(z)=A(z-a)z^{m}+q(z)\]
where $q(z)=Q(z)+az^{m}$, so $q$ is a polynomial of degree
at most $m$ and, by the inductive hypothesis,
\[q(z)=(z-a)u(z)+r\]
with $u$ a polynomial of degree at most $m-1$.
Thus $P(z)=(z-a)Q(z)+r$ with $Q(z)=A z^{m}+u(z)$.
We have shown that $S(m+1)$ is true.

Now $S(1)$ is true, since $cz+d=c(z-a)+(d-ca)$, so the required 
result follows by induction.

(ii) We have $P(z)=(z-a)Q(z)+r$ by (i). Setting $z=a$, we have
$0=P(a)=r$ so $r=0$ and the result follows.


(iii) If $P_{n}$ has degree $n\geq 1$, then the fundamental theorem
of algebra tells us that $P_{n}$ has a root $a_{n}$. By~(ii),
there exists a polynomial $P_{n-1}$ of degree $n-1$
such that
\[P(z)=(z-a_{n})P_{n-1}(z).\]
Using induction, we deduce that
\[P_{n}(z)=P_{0}(z)\prod_{j=1}^{n}(z-a_{j}),\]
where $P_{0}(z)$ is a polynomial of degree $0$,
that is to say, $P_{0}(z)=A$ with $A$ a constant.

(iv) If $P$ is not the zero polynomial,
then (iii) tells we can find $m\leq n$
such that
\[P(z)=A\prod_{j=1}^{m}(z-a_{j})\]
with $A,\,a_{1},\,a_{2},\,\dots,\,a_{m}\in{\mathbb C}$
and  $A\neq 0$.
Now $P(z)=0$ if and only if $z=a_{j}$ for some $1\leq j\leq m$.
The result follows.
\end{proof}
\begin{proof}[Solution to Exercise~\ref{E;boundaries}]
There are a wide variety of ways of doing this
exercise. Any way that works is fine.

(i) If $x\in \Int E$, we can find a $\delta>0$ such
that $B(x,2\delta)\subseteq E$. If $y\in B(x,\delta)$,
then, by the triangle inequality,
\[z\in B(y,\delta)\Rightarrow z\in B(x,2\delta)\subseteq E.\]
Thus $\Int E$ is open.

If $V$ is open and $V\subseteq E$, then, if $v\in V$,
there exists a $\delta>0$ with $B(v,\delta)\subseteq V\subseteq E$.
Thus $V\subseteq \Int E$.

(ii) If $x_{n}\in \Cl E$ and $x_{n}\rightarrow x$,
then we can find $y_{n}\in E$ such that $d(y_{n},x_{n})<1/n$.
By the triangle inequality,
\[d(y_{n},x)\leq d(y_{n},x_{n})+d(x_{n},x)\rightarrow 0+0=0\]
so $x\in \Cl E$.

If $F$ is closed and $F\supseteq E$, then, whenever
$x_{n}\in E$ and $x_{n}\rightarrow x$, we have $x_{n}\in F$,
so $x\in F$. Thus $F\supseteq \Cl E$.

(iii) The complement of an open set is closed and the intersection
of two closed sets is closed, so
\[\partial E=\Cl E\cap (\Int E)^{c}\]
is closed.

(iv) If $E$ is closed, then we can find an $R>0$
such that $E\subseteq\bar{B}(0,R)$. Since $\bar{B}(0,R)$
is closed, $\Cl E\subseteq \bar{B}(0,R)$.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;up Laplace}]
  We prove the result for $m=2$.
Since 
$\Cl\Omega$ is compact, we know that $\phi$ attains a maximum
at some point $(x_{0},y_{0})\in\Cl\Omega$. We need to show that
it is impossible that $(x_{0},y_{0})\in\Omega$.

Suppose, if possible, that $(x_{0},y_{0})\in\Omega$. Since
$\Omega$ is open, we can find a $\delta>0$ such that
$B\big((x_{0},y_{0}),\delta\big)\subseteq\Omega$. 
Consider the function
$f(y)=\phi(x_{0},y)$ defined for $y\in(y_{0}-\delta,y_{0}+\delta)$.
We have $f$ twice differentiable with a maximum at $y_{0}$.
Thus, by 1A analysis, $f''(y_{0})\leq 0$. It follows that
\[\frac{\partial^{2}\phi}{\partial y^{2}}(x_{0},y_{0})\leq 0.\]
The same argument applies for the partial derivatives with 
respect to $x$, so
\[\triangledown^{2}\phi(x_{0},y_{0})=
\frac{\partial^{2}\phi}{\partial x^{2}}(x_{0},y_{0})
+\frac{\partial^{2}\phi}{\partial y^{2}}(x_{0},y_{0})\leq 0\]
contradicting our hypotheses.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;down Laplace}]
Again we prove the 
result for $m=2$.
Let $\psi(x,y)=x^{2}+y^{2}$. Since $\psi$ is continuous and
$\Cl\Omega$ is compact, we know that there exists a $M$ with
$M\geq\psi(x,y)$ for all $(x,y)\in\Cl\Omega$. By direct calculation,
$\triangledown^{2}\psi=4$ everywhere. 

Set $\phi_{n}=\phi+n^{-1}\psi$. Then $\phi_{n}$ satisfies the conditions
of Lemma~\ref{L;up Laplace} with $\epsilon=4/n$. It follows that
there is an ${\mathbf x}_{n}=(x_{n},y_{n})\in\partial \Omega$ with
\[\phi_{n}({\mathbf x}_{n})\geq \phi_{n}({\mathbf t})\]
for all ${\mathbf t}\in\Cl\Omega$. Automatically,
\[\phi({\mathbf x}_{n})\geq \phi({\mathbf t})-8M/n.\]
Since $\partial \Omega$ is compact, we can find an
${\mathbf x}\in\partial \Omega$
and $n(j)\rightarrow\infty$ such that 
${\mathbf x}_{n(j)}\rightarrow{\mathbf x}$. By continuity
\[\phi({\mathbf x})\geq \phi({\mathbf t})\]
for all ${\mathbf t}\in\Cl\Omega$.
\end{proof}
\begin{proof}[Solution to Exercise~\ref{E;analytic maximum}]
  The map $z\mapsto|f(z)|$ is continuous so, by compactness,
there exists a $z_{0}=x_{0}+iy_{0}\in \Cl\Omega$ with
$|f(z_{0})|\geq |f(z)|$ for all $z\in\Cl\Omega$. By replacing
$f(z)$ by $e^{i\theta}f(z)$, we may assume that $f(z_{0})$ is real
and positive. 

Write $f(x+iy)=u(x,y)+iv(x,y)$ with $u$ and $v$ real. We have
\[u(x_{0},y_{0})=|f(z_{0})|\geq |f(x+iy)|\geq u(x,y)\]
and $u$ satisfies Laplace's equation. Thus there exists
a $x_{1}+iy_{1}=z_{1}\in \partial\Omega$ such that
$u(x_{1},y_{1})=u(x_{0},y_{0})$ and so $|f(z_{1})|\geq|f(z)|$
for all $z\in\Cl\Omega$.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;unique Laplace}]
Observe that,
if $\tau=\phi-\psi$, then $\tau$ satisfies the conditions
of Theorem~\ref{T;down Laplace} and so attains its maximum
on $\partial \Omega$. But $\tau=0$ on $\partial\Omega$. Thus
$\tau({\mathbf x})\leq 0$ for ${\mathbf x}=\Cl\Omega$. The same argument
applied to $-\tau$ shows that 
$-\tau({\mathbf x})\leq 0$ for ${\mathbf x}=\Cl\Omega$.
Thus $\tau=0$ on $\Cl\Omega$ and we are done.
\end{proof}
\begin{proof}[Solution to Exercise~\ref{E;no Laplace}]
  (i) If ${\mathbf x}\in\Omega$, then, setting
\[\delta=\min\{\|{\mathbf x}\|,1-\|{\mathbf x}\|\},\]
we have $\delta>0$ and $B({\mathbf x},\delta)\subseteq\Omega$.
Thus $\Omega$ is open. 

Observe that $(0,1/n)\rightarrow (0,0)$, so 
${\boldsymbol 0}\in\Cl\Omega$. Again, if $\|{\mathbf x}\|=1$,
then $(1-1/n){\mathbf x}\rightarrow{\mathbf x}$, so
${\mathbf x}\in\Cl\Omega$. Thus 
$\Cl\Omega\supseteq\bar{B}({\boldsymbol 0},1)$. Since
$\bar{B}({\boldsymbol 0},1)$ is closed 
$\Cl\Omega=\bar{B}({\boldsymbol 0},1)$.

Finally,
\[\partial\Omega=\Cl \Omega\setminus\Int\Omega
=\Cl \Omega\setminus\Omega=
\{{\mathbf x}\in{\mathbb R}^{2}\,:\,\|{\mathbf x}\|=1\}
\cup\{{\boldsymbol 0}\}.\]

(ii) Let $T$ be a rotation with centre the origin.
If $\psi=\phi T$, then (using the chain rule if you do not know
the result already from applied courses)
\[\triangledown^{2}\psi=0.\]
But
\[\psi({\mathbf x})
=\begin{cases}
0&\text{if $\|{\mathbf x}\|=1$},\\
1&\text{if ${\mathbf x}={\boldsymbol 0}$}.
\end{cases}
\]
Thus, by uniqueness,  $\psi=\phi$ and so,
since $T$ was an arbitrary rotation, 
\[\phi({\mathbf x})=f(\|{\mathbf x}\|)\]
for some function $f:[0,1]\rightarrow {\mathbb R}$.

(iii) The chain rule gives
\[\frac{\partial \phi}{\partial x}
=f'(r)\frac{x}{r}
\ \text{and}
\ \frac{\partial^{2} \phi}{\partial x^{2}}
=f''(r)\frac{x^{2}}{r^{2}}+f'(r)\left(\frac{1}{r}-\frac{x^{2}}{r^{3}}
\right)\]
so, using the parallel result for derivatives with respect to $y$,
\[\triangledown^{2}\phi=f''(r)+f'(r)r^{-1}
=r^{-1}\frac{d\ }{dr}\big(rf(r)\big).\]
(Or we can just quote this result from applied courses.)
Thus
\[\frac{d\ }{dr}\big(rf(r)\big)=0\]
so $rf'(r)=B$ and $f(r)=A+B\log r$ for appropriate
constants $A$ and $B$. 

(iv) We need $f(r)\rightarrow 1$ as $r\rightarrow 0+$,
so $B=0$ and $A=1$. This gives $f(1)=1$, contradicting
the condition
$\phi({\mathbf x})
=0$ if $\|{\mathbf x}\|=1$.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;fix you}]
Observe that
$f=g^{-1}Fg$ is a continuous function from $\bar{D}$
to $\bar{D}$ and so, by Theorem~\ref{T;fix disc},
has a fixed point $w$. Set $a=g(w)$.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Brouwer retracts}]
\noindent{(i)$\Rightarrow$ (ii)} Suppose, if possible, that there
exists a continuous function $g:{\bar D}\rightarrow\partial D$
with $g({\mathbf x})={\mathbf x}$ for all ${\mathbf x}\in \partial D$.
If $T$ is a rotation through $\pi$ about ${\boldsymbol 0}$,
then $f=T\circ g$ is a continuous function from ${\bar D}$
to itself with no fixed points, contradicting~(i).

\noindent{(ii)$\Rightarrow$ (i)} Suppose, if possible, that
$f:{\bar D}\rightarrow {\bar D}$ is a continuous function 
with no fixed points. If we define 
\[E=\{({\mathbf x},{\mathbf y})\in {\bar D}^{2}
\,:\,{\mathbf x}\neq{\mathbf y}\}\]
and $u:E\rightarrow \partial D$ by taking $u({\mathbf x},{\mathbf y})$ to be the
point where the straight line joining ${\mathbf x}$ to ${\mathbf y}$ in the
indicated direction cuts $\partial D$ then $u$ is continuous.
(We shall take this as geometrically obvious. 
The algebraic details are messy
(but made easier if you use the fact
that the composition of continuous functions is continuous).
The really conscientious student
can do Exercise~\ref{A1.14}.)
Using the chain rule for continuous functions, we see that
\[g({\mathbf x})=u\big({\mathbf x},f({\mathbf x})\big)\]
defines a retraction mapping from $\bar{D}$ to $\partial D$,
contradicting (ii).
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;more retract}]
\noindent{(i)$\Rightarrow$(ii)} Suppose, if possible,
that $\tilde{k}$ exists with
the properties stated in (ii), Then, 
if $T$ is a rotation through $\pi$, 
about ${\boldsymbol 0}$,
we see that $f=T\circ\tilde{k}$ is a continuous map from $\bar{D}$ 
to $\bar{D}$
without a fixed point. By Theorem~\ref{T;Brouwer retracts}
this contradicts (i).

\noindent{(ii)$\Rightarrow$(i)} If $\tilde{k}$ is a continuous retract 
from $\bar{D}$ to $\partial D$, then it certainly satisfies (ii).

\noindent{(iii)$\Leftrightarrow$(ii)} We use an argument of the type used for
Lemma~\ref{L;fix you}.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;colour me}]

  \noindent{(ii)$\Rightarrow$(i)} Let $h:{\bar T}\rightarrow{\partial T}$
be continuous with $h(I)\subseteq I$, $h(J)\subseteq J$,
$h(K)\subseteq K$. Let $A=h^{-1}(I)$, $B=h^{-1}(J)$, $C=h^{-1}(K)$.
Since $h$ is continuous $A$, $B$ and $C$ are closed. Since
$I\cup J\cup K={\partial D}$, $A\cup B\cup C={\bar D}$.
But 
\[A\cap B\cap C=h^{-1}(I)\cap h^{-1}(J)\cap h^{-1}(K)=
h^{-1}(I\cap J\cap K)=h^{-1}(\emptyset)=\emptyset\]
contradicting~(ii).

\noindent{(i)$\Rightarrow$(ii)}
Suppose that $A$, $B$ and $C$ are closed subsets of $T$ with
$A\supseteq I$, $B\supseteq J$, $C\supseteq K$,
$A\cup B\cup C=T$,
and $A\cap B\cap C=\emptyset$.

We consider $T$
as the triangle
\[T=\{(x,y,z)\in{\mathbb R}^{3}\,:\,
x+y+z=1,\ x,\,y,\,z\geq 0\}.\]
(In my school days we called these `barycentric
coordinates'.)
If ${\mathbf x}\in T$, we know that
${\mathbf x}$ lies in at most two of the sets $A$, $B$
and $C$ so (by Lemma~\ref{L;distance closed})
at least one of $d({\mathbf x},A)$, $d({\mathbf x}, B)$
and $d({\mathbf x}, C)$ is non-zero. Thus
\[h({\mathbf x})=\frac{1}
{d({\mathbf x},A)+d({\mathbf x}, B)
+d({\mathbf x}, C)}
{\big(d({\mathbf x},A),d({\mathbf x}, B),d({\mathbf x}, C)\big)}\]
defines a continuous function $h:T\rightarrow T$.
If ${\mathbf x}\in I$, then $d({\mathbf x},A)=0$
and so $h({\mathbf x})\in I$. Similarly
$h(J)\subseteq J$ and $h(K)\subseteq K$
contradicting (i).
\end{proof}
\begin{proof}[Proof of Theorem~\ref{L;Sperner}]
Given
an edge of the grid joining vertices $u$
and $v$ we assign a value $E(u,v)$ to the edge
by a rule which ensures that, if $u$ and $v$
have the same colour, $E(u,v)=0$, if $u$ and $v$,
have different colours $X$ and $Y$, then
$E(u,v)=\zeta(X,Y)$ with $\zeta(X,Y)=-\zeta(Y,X)$
and $\zeta(X,Y)=\pm 1$.

The table which follows gives an example.
\begin{center}
\begin{tabular}{ccc}
colour $u$&colour $v$&$E(u,v)$\\
R&R&0\\
R&G&1\\
R&B&-1\\
G&R&-1\\
G&G&0\\
G&B&1\\
B&R&1\\
B&G&-1\\
B&B&0
\end{tabular}
\end{center}
If $uvw$ is a grid triangle then, by inspection, the sum of the
edge values (going round anticlockwise) is zero unless
all of the vertices have different colours. By considering 
internal cancellation, the total sum of the edge values
is the sum of the edge values going round the outer edge
and this is non-zero. Thus one of the grid triangles
must have all three vertices of different colours.
\end{proof}
\begin{proof}[Proof of  Lemma~\ref{L;colour me}~(ii)]
Suppose that $A$, $B$ and $C$ are closed subsets of $T$ with
$A\supseteq I$, $B\supseteq J$ and $C\supseteq K$
and $A\cup B\cup C=T$.

Take a triangular grid formed by $n$ equally spaced
parallel lines for each of the three sides dividing 
$T$ into a grid of congruent triangles. Colour the
vertices red, blue or green so that
all the red vertices lie in $A$, all the blue vertices 
lie in $B$ and all the green vertices lie in $C$, 
making sure that the outside edges are coloured
as required by Lemma~\ref{L;Sperner}.

Lemma~\ref{L;Sperner} tells us that there is a grid
triangle with vertex ${\mathbf a}_{n}$ red, so in $A$,
vertex ${\mathbf b}_{n}\in B$ and ${\mathbf c}_{n}\in C$.
By compactness, we can find $n(j)\rightarrow\infty$
and ${\mathbf x}\in T$ such that 
${\mathbf a}_{n(j)}\rightarrow {\mathbf x}$
and so 
${\mathbf b}_{n(j)}\rightarrow {\mathbf x}$,
${\mathbf c}_{n(j)}\rightarrow {\mathbf x}$.
Since $A$, $B$ and $C$ are closed
${\mathbf x}\in A\cap B\cap C$, 
so  $A\cap B\cap C\ne\emptyset$  
\end{proof}
\begin{proof}[Solution for Exercise~\ref{E;reverse Markov}]
  $T$ is a closed triangle in the appropriate plane.
If ${\mathbf X}\in T$ and we write ${\mathbf y}=T{\mathbf x}$,
then $y_{i}\geq 0$ and
\[
\sum_{i=1}^{3}y_{i}=\sum_{i=1}^{3}\sum_{j=1}^{3}a_{ij}x_{j}
=\sum_{j=1}^{3}\sum_{i=1}^{3}a_{ij}x_{j}\\
=\sum_{j=1}^{3}x_{j}=1,
\]
so ${\mathbf y}\in T$. Thus $T$ is a continuous map of $T$ into itself
and has a fixed point ${\mathbf e}$.
We observe that ${\mathbf e}$
is an eigenvector lying in $T$ with eigenvalue $1$.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Nash stable}]
Let ${\tilde E}=\{(p,1-p,q,1-q)\,:\,0\leq p,q\leq 1\}$.
(Thus ${\tilde E}$ is
a two dimensional square embedded in ${\mathbb R}^{4}$.)

Suppose $({\mathbf p},{\mathbf q})\in {\tilde E}$. Write
\[u_{1}({\mathbf p},{\mathbf q})=
\max\{0,A(1,0,{\mathbf q})-A({\mathbf p},{\mathbf q})\}.\]
Thus $u_{1}$ is Albert's expected gain if, 
instead of choosing ${\mathbf p}$
when Bertha chooses ${\mathbf q}$, he chooses $(1,0)$ and 
Bertha maintains her choice \emph{provided this is positive}
and $u_{1}$ is zero otherwise. Similarly
\[u_{2}({\mathbf p},{\mathbf q})=
\max\{0,A(0,1,{\mathbf q})-A({\mathbf p},{\mathbf q})\},\]
so $u_{2}$  is Albert's expected gain if, 
instead of choosing ${\mathbf p}$
when Bertha chooses ${\mathbf q}$, he chooses $(0,1)$ and 
Bertha maintains her choice \emph{provided this is positive}
and $u_{2}$ is zero otherwise.
In the same way, we take
\[v_{1}({\mathbf p},{\mathbf q})=
\max\{0,B({\mathbf p},1,0)-B({\mathbf p},{\mathbf q})\}.\]
and
\[v_{2}({\mathbf p},{\mathbf q})=
\max\{0,B({\mathbf p},0,1)-B({\mathbf p},{\mathbf q})\}.\]

Now define
\[g({\mathbf p},{\mathbf q})=({\mathbf p}',{\mathbf q}')\]
with
\[{\mathbf p}'=\frac{{\mathbf p}+{\mathbf u}({\mathbf p},{\mathbf q})}
{1+u_{1}({\mathbf p},{\mathbf q})+u_{2}({\mathbf p},{\mathbf q})}\]
and
\[{\mathbf q}'=\frac{{\mathbf q}+{\mathbf v}({\mathbf p},{\mathbf q})}
{1+v_{1}({\mathbf p},{\mathbf q})+v_{2}({\mathbf p},{\mathbf q})}.\]
We observe that $g$ is a well defined continuous function from
${\tilde E}$ into itself and so 
has a fixed point $({\mathbf p}^{*},{\mathbf q}^{*})$.

We claim that  $({\mathbf p}^{*},{\mathbf q}^{*})$ is a Nash stable point.

Suppose, if possible, that 
$A\big((r,1-r),{\mathbf q}^{*}\big)>A\big((p^{*},1-p^{*}),{\mathbf q}^{*}\big)$.
Without loss of generality, we may suppose that $r>p^{*}$ so that
\[A\big((1,0),{\mathbf q}^{*}\big)>A\big((p^{*},1-p^{*}),{\mathbf q}^{*}\big)\]
and
\[A\big((0,1),{\mathbf q}^{*}\big)<A\big((p^{*},1-p^{*}),{\mathbf q}^{*}\big).\]
Thus $u_{1}({\mathbf p}^{*},{\mathbf q}^{*})>0$ and
$u_{2}({\mathbf p}^{*},{\mathbf q}^{*})=0$, whence ${\mathbf p}^{*}=(1,0)$
and $u_{1}({\mathbf p}^{*},{\mathbf q}^{*})=0$ which contradicts our earlier
assertion. 

We have shown that
\[A\big({\mathbf p}^{*},{\mathbf q}^{*}\big)
\geq A\big((p,1-p),{\mathbf q}^{*}\big)\]
for all $1\geq p\geq 0$. The same argument shows that
\[B\big({\mathbf p}^{*},{\mathbf q}^{*}\big)
\geq B\big({\mathbf p}^{*},(q,1-q)\big)\]
for all $1\geq q\geq 0$ so we are done.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;chicken}]
  Suppose that $A$ swerves with probability $a$
and $B$ with probability $b$. The value of the game to $A$ is
\[V(a,b)=-ab+10(1-a)b-5a(1-b)-100(1-a)(1-b).\]
If $0<a<1$,$0<b<1$
\[\frac{\partial V}{\partial a}(a,b)=95-106b,\]
so by symmetry we have a Nash equilibrium point $(a,b)=(95/106,95/106)$.
However 
\[V(a,0)=-5a-100(1-a)=95a-100, V(a,1)=10-11a\]
so, again using symmetry, $(1,0)$ and $(0,1)$ are also
Nash equilibrium points.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;convex transform}] 
If ${\mathbf x}',\,{\mathbf y}'\in E'$
and $0\leq t\leq 1$, then
\[x_{j}'=a_{j}x_{j}+b_{j},\ y_{j}'=a_{j}y_{j}+b_{j}\]
with ${\mathbf x},\,{\mathbf y}\in E$
and so
\[tx_{j}'+(1-t)y_{j}'=a_{j}(tx_{j}+(1-t)y_{j})+b_{j}\]
for all $j$. But $t{\mathbf x}+(1-t){\mathbf y}\in E$, 
since $E$ is convex,
so $t{\mathbf x}'+(1-t){\mathbf y}'\in E'$
and is convex.

We now recall Theorem~\ref{T;Compact image}
and observe that
$E'$ is the continuous image of a compact set so compact.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;push to  one side}]
 If ${\mathbf x}\in K$ and $0\leq t\leq 1$, 
then, since
${\mathbf 1}\in K$ and $K$ is convex, we have
\[(1-t){\mathbf 1}+t{\mathbf x}\in K\] so, by our hypothesis,
\begin{align*}
1&\geq \prod_{j=1}^{n}\big(tx_{j}+(1-t)\big)=\prod_{j=1}^{n}\big(1+t(x_{j}-1)\big)\\
&=1+t\sum_{j=1}^{n}(x_{j}-1)+t^{2}P(t)
\end{align*}
where $P$ is a polynomial with coefficients depending on ${\mathbf x}$.
It follows that, if $0\leq t\leq 1$, we have
\[0\geq \sum_{j=1}^{n}(x_{j}-1)+tP(t).\]
Allowing $t\rightarrow 0+$ gives
\[0\geq \sum_{j=1}^{n}(x_{j}-1),\]
which is the desired result.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;happy Nash}]
The Nash conditions mean that the problem is 
invariant under affine transformation
(i.e. transformations of the type discussed in  
Exercise~\ref{E;convex transform}).
Thus we may assume that ${\mathbf s}={\boldsymbol 0}$.
If the hyperboloid $\prod_{j=1}^{n} y_{j}=K$
touches the convex set $E'$ at  ${\bf y}$ (with $y_{j}>0$)
then the transformation $x_{j}=K^{-1/n}y_{j}/y_{j}^{*}$
gives a hyperboloid $\prod_{j=1}^{n} x_{j}=1$
touching a convex set $E$ at  $(1,1,\ldots,1)$.

Thus we may assume that ${\mathbf s}={\boldsymbol 0}$
and 
$x_{1}^{*}=x_{2}^{*}=\dots=x_{n}^{*}=1$.

By Lemma~\ref{L;push to one side}, we have
\[K\subseteq L=\left\{{\mathbf x}:\sum_{j=1}^{n}x_{j}\leq n\right\},\]
and, by the independence of irrelevant alternatives,
if ${\mathbf x}^{*}$ is best for $L$, it is best for $K$.
Now $L$ is symmetric so any best point ${\mathbf x}$ for $L$
must lie on $x_{1}=x_{2}=\ldots=x_{n}$. But, amongst these points, only
${\mathbf x}^{*}$ is Pareto optimal so we are done.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;pushier}]
  By compactness, there is
a point ${\mathbf x}^{*}$ where $f$ attains its maximum. By
translation, we may suppose ${\mathbf s}={\boldsymbol 0}$
and, re-scaling the axes, we may suppose 
${\mathbf x}^{*}={\mathbf e}=(1,1,\ldots,1)$.

Lemma~\ref{L;push to  one side} tells us that
\[\{{\mathbf k}\in K\,:\,k_{j}\geq 0\ \forall j\}\subseteq 
\{{\mathbf x}\in K\,:\,x_{j}\geq 0\ \forall j
\ \text{and}\ x_{1}+x_{2}+\ldots+x_{n}=n\}.\]
The uniqueness of the maximum now follows from the conditions
for equality in the arithmetic geometric inequality.
\end{proof}
\begin{proof}[Solution for Exercise~\ref{E;Cauchy example}]
(i) We use induction on $n$ to show that $E$ is $n$ 
times differentiable with 
\[E^{(n)}(t)=P_{n}(1/t)E(t)\]
for all $t\neq 0$ and some polynomial $P_{n}$.

The result is certainly true for $n=0$ with $P_{0}=1$.
If it is true for $n=m$, then the standard rules for 
differentiation show that $E^{(m)}$ is differentiable with
\[E^{(m+1)}(t)=t^{-2}P_{m}'(1/t)E(t)-2t^{-3}P_{m}(1/t)E(t)=P_{m+1}(1/t)E(t)\]
for all $t\neq 0$ and the polynomial 
$P_{m+1}(s)=s^{2}P_{m}'(s)-2s^{3}P_{m}(s)$.

(ii)  We use induction on $n$ to show that $E$ is $n$ 
times differentiable at $0$ with 
\[E^{(n)}(0)=0.\]

The result is true for $n=0$.
If it is true for $n=m$, then 
\[\frac{E^{(m)}(h)-E^{(m)}(0)}{h}=h^{-1}P(h^{-1})E(h)\rightarrow 0\]
as $h\rightarrow 0$, so it is true for $n=m+1$.

(iii) We have
\[E(t)\neq 0=\sum_{n=0}^{\infty}\frac{0}{n!}t^{n}
=\sum_{n=0}^{\infty}\frac{E^{(n)}(0)}{n!}t^{n}\]
for all $t\neq 0$, as stated.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;interpolate polynomial}]
(i) If $P$ and $Q$ have degree at most $n$
and 
\[P(x_{j})=Q(x_{j})=f(x_{j})\]
for $0\leq j\leq n$,
then $P-Q$ is a polynomial of degree at most $n$
vanishing at at least $n+1$ points. Thus $P-Q=0$,
by Exercise~\ref{E;roots}, so $P=Q$.

(ii) We observe that $e_{j}(x_{i})=1$ if $i=j$, but
$e_{j}(x_{i})=0$ otherwise and that $e_{j}$ is a 
polynomial of degree $n$. Thus 
\[P=\sum_{j=0}^{n}f(x_{j})e_{j}\]
is a polynomial of degree at most $n$ with
\[P(x_{i})=\sum_{j=0}^{n}f(x_{j})e_{j}(x_{i})
=f(x_{i})\] 
for $0\leq i\leq n$.

(iii) It is easy to check that ${\mathcal P}_{n}$
is a vector space. Part~(ii) shows that the $e_{j}$ span
${\mathcal P}_{n}$. If
\[\sum_{j=0}^{n}\lambda_{j}e_{j}=0,\]
then 
\[\lambda_{i}=\sum_{j=0}^{n}\lambda_{j}e_{j}(x_{i})=0\]
for each $i$,  so the the $e_{j}$
are linearly independent.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Chebychev polynomials}]
By de Moivre's theorem,
\begin{align*}
\cos& n\theta+i\sin n\theta=(\cos\theta+i\sin\theta)^{n}\\
&=\sum_{r=0}^{n}i^{r}\binom{n}{r}(\cos\theta)^{n-r}(\sin \theta)^{r}\\
&=\sum_{0\leq 2r\leq n}(-1)^{r}
\binom{n}{2r}(\cos\theta)^{n-2r}(\sin \theta)^{2r}\\
&\qquad\qquad+i\sin\theta\sum_{0\leq 2r\leq n-1}(-1)^{r}
\binom{n}{2r+1}(\cos\theta)^{n-1-2r}(\sin \theta)^{2r}\\
&=\sum_{0\leq 2r\leq n}(-1)^{r}
\binom{n}{2r}(\cos\theta)^{n-2r}\big(1-(\cos\theta)^{2}\big)^{r}\\
&\qquad\qquad+i\sin\theta\sum_{0\leq 2r\leq n-1}(-1)^{r}
\binom{n}{2r+1}(\cos\theta)^{n-1-2r}\big(1-(\cos \theta)^{2}\big)^{r}\\
&=T_{n}(\cos\theta)+i\sin\theta U_{n-1}(\cos\theta),
\end{align*}
where $T_{n}$ is a polynomial of degree at most $n$
and $U_{n-1}$ a polynomial of degree at most $n-1$.

Taking real and imaginary parts, we obtain
\[T_{n}(\cos\theta)=\cos n\theta\]
for all $\theta$ and
\[U_{n-1}(\cos\theta)=\frac{\sin n\theta}{\sin\theta}\]
for $\sin\theta\neq 0$, $U_{n-1}(1)=n$, $U_{n-1}(-1)=(-1)^{n-1}n$ .
The roots of $U_{n-1}$ and $T_{n}$ can be read off
directly and show that the two polynomials have full 
degree.

The coefficient of $t^{n}$ in $T_{n}$ is
\[\sum_{0\leq 2r\leq n}\binom{n}{2r}
=\frac{1}{2}\big((1+1)^{n}+(1-1)^{n}\big)=2^{n-1}\]
for $n\geq 1$.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;distinct metrics}]
 The key result that we use in (i) and (ii) is
that, if $f\in C([0,1])$, $f(t)\geq 0$ for all $t\in[0,1]$
and $\int_{0}^{1}f(t)\,dt=0$, then   
$f(t)=0$ for all $t\in[0,1]$.

(i)  Observe that
\[\|f\|_{1}=\int_{0}^{1}|f(t)|\,dt\geq 0\]
and that, if $\|f\|_{1}=0$, then
\[\int_{0}^{1}|f(t)|\,dt=0,\]
so $|f(t)|=0$ for
all $t$, so $f(t)=0$ for all $t$ and $f=0$.

Further
\[\|\lambda f\|_{1}=\int_{0}^{1}|\lambda||f(t)|\,dt
=|\lambda|\int_{0}^{1}|f(t)|\,dt=|\lambda|\|f\|_{1}\]
and, since $|f(t)+g(t)|\leq |f(t)|+|g(t)|$, we have
\[\|f+g\|_{1}=\int_{0}^{1}|f(t)+g(t)|\,dt
\leq \int_{0}^{1}|f(t)|+|g(t)|\,dt=\|f\|_{1}+\|g\|_{1},\]
so we have a norm.

(ii) We have 
\[\langle f,f\rangle=\int_{0}^{1}f(t)^{2}\,dt\geq 0.\]

If  $\langle f,f\rangle=0$, then $\int_{0}^{1}f(t)^{2}\,dt=0$,
so $f(t)^{2}=0$ for
all $t$, so $f(t)=0$ for all $t$ and $f=0$.

We have 
\[
\langle f,g\rangle=\int_{0}^{1}f(t)g(t)\,dt
=\int_{0}^{1}g(t)f(t)\,dt
=\langle g,f \rangle\]
and
\begin{align*}
\langle f+g,h\rangle
&=\int_{0}^{1}(f(t)+g(t))h(t)\,dt\\
&=\int_{0}^{1}f(t)h(t)\,dt+\int_{0}^{1}g(t)h(t)\,dt
=\langle f,h\rangle
+\langle g,h\rangle
\end{align*}
whilst
\[\langle\lambda f,g\rangle
=\int_{0}^{1}\lambda f(t)g(t)\,dt
=\lambda\int_{0}^{1}f(t)g(t)\,dt
=\lambda\langle f,g\rangle,\]
so we have an inner product.

(iii) Observe that $|f(t)|\geq 0$,so 
\[\|f\|_{\infty}=\sup_{t\in[0,1]}|f(t)|\geq 0,\]
that
\[\|f\|_{\infty}=0\Rightarrow\sup_{t\in[0,1]} |f(t)|=0
\Rightarrow |f(t)|=0\ \forall t\Rightarrow f=0,\]
that
\[\|\lambda f\|_{\infty}=\sup_{t\in[0,1]}|\lambda f(t)|
=\sup_{t\in[0,1]}|\lambda||f(t)|=|\lambda|\sup_{t\in[0,1]}|f(t)|
=\lambda \|f\|_{\infty},\]
and, that, since $|f(t)+g(t)|\leq |f(t)|+|g(t)|$,
\begin{align*}
\|f+g\|_{\infty}&=\sup_{t\in[0,1]}|f(t)+g(t)|
\leq \sup_{t\in[0,1]}(|f(t)|+|g(t)|)\\
&\leq \sup_{t,s\in[0,1]}(|f(t)|+|g(s)|)=\|f\|_{\infty}+\|g\|_{\infty},
\end{align*}
so we are done.

The Cauchy--Schwarz inequality gives
\[\|f\|_{2}=\|f\|_{2}\|1\|_{2}\geq\langle |f|,1\rangle=\|f\|_{1}.\]
First year analysis gives
\[\|f\|_{\infty}=\|f^{2}\|^{1/2}_{\infty}
\geq\left(\int_{0}^{1}f(t)^{2}\,dt\right)^{1/2}=\|f\|_{2}.\].

If $f_{n}$ is as stated, $\|f_{n}\|_{1}=2\int_{0}^{1/n}nt\,dt=1/n$,
$\|f_{n}\|_{\infty}=1$ and
\[\|f_{n}\|_{2}=\left(2\int_{0}^{1/n}(nt)^{2}\,dt\right)^{1/2}
=\left(\frac{2}{3n}\right)^{1/2}.\]
Thus
$\|f_{n}\|_{\infty}/\|f_{2}\|_{1}=(3/2)^{1/2}n^{1/2}\rightarrow\infty$
and $\|f_{n}\|_{2}/\|f_{1}\|_{1}=(2/3)^{1/2}n^{1/2}\rightarrow\infty$
as $n\rightarrow\infty$. We have genuinely different
measures of distance.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;uniform continuity}]
Suppose that $f$ is not uniformly continuous.
Then we can find an $\epsilon>0$
and ${\mathbf x}_{n},\,{\mathbf y}_{n}\in E$ such that
\[\|{\mathbf x}_{n}-{\mathbf y}_{n}\|\leq 1/n
\ \text{and}\ \|f({\mathbf x}_{n})-f({\mathbf y}_{n})\|\geq \epsilon.\]
By compactness, we can find ${\mathbf e}\in E$
and $n(j)\rightarrow\infty$ such that 
${\mathbf x}_{n(j)}\rightarrow{\mathbf e}$.
The triangle inequality tells us that
${\mathbf y}_{n(j)}\rightarrow{\mathbf e}$
and so
\[\|f({\mathbf x}_{n(j)})-f({\mathbf y}_{n(j)})\|
\leq \|f({\mathbf x}_{n(j)})-f({\mathbf e})\|+
\|f({\mathbf y}_{n(j)})-f({\mathbf e})\|
\rightarrow 0+0=0.\]
We have a contradiction.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Chebychev}]
By replacing $X$ by $Y=X-{\mathbb E}X$,
we may suppose that ${\mathbb E}X=0$.

Let
\[{\mathbb I}_{{\mathbb R}\setminus (-a,a)}(t)=
\begin{cases}0&\text{if $|t|<a$},\\
1&\text{otherwise.}
\end{cases}\]
Then 
\[\frac{t^{2}}{a^{2}}\geq {\mathbb I}_{{\mathbb R}\setminus (-a,a)}(t)\]
for all $t$, so, automatically,
\[\frac{X^{2}}{a^{2}}\geq {\mathbb I}_{{\mathbb R}\setminus (-a,a)}(X)\]
and
\[\frac{\sigma^{2}}{a^{2}}
={\mathbb E}\frac{X^{2}}{a^{2}}
\geq{\mathbb E} {\mathbb I}_{{\mathbb R}\setminus (-a,a)}(X)
=\Pr(|X|\geq a).\]
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Bernstein}]
(i) We have
\begin{align*}
p_{n}(t)&={\mathbb E}f(Y_{n}(t))\\
&=\sum_{j=0}^{n}f(j/n)\Pr(X_{1}+X_{2}+\dots+X_{n}=j)\\
&=\sum_{j=0}^{n}\binom{n}{j}f(j/n)t^{j}(1-t)^{n-j}.
\end{align*}

(ii) Automatically,
\[{\mathbb E}Y_{n}={\mathbb E}\frac{X_{1}+X_{2}+\dots+X_{n}}{n}
=\frac{{\mathbb E}X_{1}+{\mathbb E}X_{2}+\dots+{\mathbb E}X_{n}}{n}
=\frac{nt}{n}=t\]
and, since the $X_{j}$ are independent,
\begin{align*}
\var Y_{n}&=\var\frac{X_{1}+X_{2}+\dots+X_{n}}{n}
=n^{-2}\var(X_{1}+X_{2}+\dots+X_{n})\\
&=n^{-2}(\var X_{1}+\var X_{2}+\ldots+\var X_{n})\\
&=n^{-1}\var X_{1}=n^{-1}t(1-t)\leq n^{-1}.
\end{align*}

Let $\epsilon>0$. By uniform continuity we can find
an $\eta>0$ such that $|f(t)-f(s)|\leq\epsilon$ for $|t-s|\leq\eta$
and $t,\,s\in[0,1]$. Thus, using Chebychev's inequality,
\begin{align*}
|p_{n}(t)-f(t)|&=\big|{\mathbb E}\big(f(Y_{n})-f(t)\big)\big|
\leq {\mathbb E}|f(Y_{n})-f(t)|\\
&\leq \epsilon\Pr(|Y_{n}-t|<\eta)+2\|f\|_{\infty}\Pr(|Y_{n}-t|\geq\eta)\\
&\leq \epsilon+2\|f\|_{\infty}\Pr(|Y_{n}-{\mathbb E}Y_{n}|\geq\eta)\\
&\leq \epsilon+2\|f\|_{\infty}\eta^{-2}/n\leq 3\epsilon,
\end{align*}
provided only that $n\geq \epsilon^{-1}(2\|f\|+1)\eta^{-2}$. Since
$\epsilon$ is arbitrary, the result follows.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Chebychev equiripple}]
Without loss of generality, suppose that
\[f(a_{j})-P(a_{j})=(-1)^{j}\sigma\ \text{for all $0\leq j\leq n$}.\]
Suppose, if possible, that $Q$ is a polynomial of degree
$n-1$ or less  such that $\|P-f\|_{\infty}>\|Q-f\|_{\infty}$.

We look at $R=P-Q$. Note first that $R$ is a polynomial of degree
at most $n-1$. If $j$ is odd,
\begin{align*}
R(a_{j})&=\big(P(a_{j})-f(a_{j})\big)+\big(f(a_{j})-Q(a_{j})\big)\\
&=|P(a_{j})-f(a_{j})|+\big(f(a_{j})-Q(a_{j})\big)\\
&\geq |P(a_{j})-f(a_{j})|-\|Q-f\|_{\infty}
=\|P-f\|_{\infty}-\|Q-f\|_{\infty}>0.
\end{align*}
and a similar argument shows that 
\[R(a_{j})<0\]
when $j$ is even. 

The intermediate value theorem now tells that $R$ has at least $n$
zeros, so $R=0$ and $P=Q$, contradicting our initial assumption.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;nice Chebychev}]
  If $t=\cos\theta$, then
\[t^{n}-S_{n}(t)=2^{1-n}T_{n}(t)=2^{1-n}\cos n\theta\]
Thus 
\[|t^{n}-S_{n}(t)|\leq 2^{1-n}\]
for $t\in [-1,1]$ and
\[t^{n}-S_{n}(t)=(-1)^{j}2^{1-n}\]
for $t=\cos j\pi/n$ $[0\leq j\leq n]$.

The stated result now follows from the equiripple criterion.
\end{proof}
\begin{proof}[Proof of Corollary~\ref{C;naught for naught}]
(i) This is just a restatement of Theorem~\ref{T;nice Chebychev}.

(ii) Let $\Gamma(n)$ be the statement given in (ii)
with the extra condition $\epsilon_{n}\leq 1$.
$\Gamma(0)$ is true with $\epsilon_{0}=1$ by inspection.

Suppose that $\Gamma_{n}$ is true, that
$P(t)=\sum_{j=0}^{n+1}a_{j}t^{j}$ 
is a polynomial of degree at most $n+1$, 
and that $|a_{k}|\geq 1$ for some
$n+1\geq k\geq 0$. If $|a_{n+1}|\leq\epsilon_{n}/2$,
then
\[P(t)=a_{n+1}t^{n+1}+Q(t)\]
where $Q(t)=\sum_{j=0}^{n}a_{j}t^{j}$
is a polynomial of degree at most $n+1$ and $|a_{k}|\geq 1$ for some
$n\geq k\geq 0$. Thus
\[\|P\|_{\infty}\geq\|Q\|_{\infty}-|a_{n+1}|\geq \epsilon_{n}/2.\]

On the other hand, if  $|a_{n+1}|\geq\epsilon_{n}/2$,
then part~(i) tells us that
\[\|P\|_{\infty}\geq 2^{-n+1}\epsilon_{n}/2=2^{-n}\epsilon_{n}.\]
Thus, whatever the value of $a_{n+1}$,
\[\|P\|_{\infty}\geq 2^{-n-1}\epsilon_{n}\]
and $\Gamma(n+1)$ holds with $\epsilon_{n+1}=2^{-n-1}\epsilon_{n}$.

The required result holds by induction.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;best approximation exists}]
By rescaling and translation, we may suppose
that $[a,b]=[-1,1]$.
Consider the map $F:{\mathbb R}^{n+1}\rightarrow{\mathbb R}$
given by $F({\mathbf a})=\|f-Q\|_{\infty}$ where
\[Q(t)=\sum_{j=0}^{n}a_{j}t^{j}.\]
Recalling the inequality 
$\big||d(f,g)|-|d(f,h)|\big|\leq d(g,h)$, we have
\[|F({\mathbf a})-F({\mathbf b})|\leq\sup_{t\in[-1,1]}
\left| \sum_{j=0}^{n}a_{j}t^{j}-\sum_{j=0}^{n}b_{j}t^{j}\right|
\leq\sum_{j=0}^{n}|a_{j}-b_{j}|\leq (n+1)\|{\mathbf a}-{\mathbf b}\|,\]
so $F$ is continuous. Also
\[F({\mathbf a})\geq \sup_{t\in[-1,1]}
\left| \sum_{j=0}^{n}a_{j}t^{j}\right|-\|f\|_{\infty}\]
so, by Corollary~\ref{C;naught for naught}~(ii),
we can find a $K>0$ such that
\[{\mathbf a}\notin[-K,K]^{n+1}\Rightarrow
  F({\mathbf a})\geq F({\boldsymbol 0}).\]

By compactness, $F$ attains a minimum at some point
${\mathbf p}\in [-K,K]^{n+1}$ and 
\[P(t)=\sum_{j=0}^{n}p_{j}t^{j}\]
is the required polynomial.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;numerical}]
As in Lemma~\ref{L;interpolate polynomial},
we take
\[e_{k}(x)=\prod_{j\neq k}\frac{x-x_{j}}{x_{k}-x_{j}}.\]
If 
\[\int_{a}^{b}P(x)\,dx=\sum_{j=0}^{n}A_{j}P(x_{j})\]
for all polynomials of degree $n$ or less,
then, setting $P=e_{k}$, gives us
\[A_{k}=\int_{a}^{b}e_{k}(x)\,dx,\]
proving uniqueness.

On the other hand, if $P$ has degree $n$ or less,
\[Q=P-\sum_{j=0}^{n}P(x_{j})e_{j}\]
has degree $n$ or less but vanishes at the $n+1$
points $x_{j}$. Thus $Q=0$ and
\[P=\sum_{j=0}^{n}P(x_{j})e_{j},\]
whence
\[\int_{a}^{b}P(x)\,dx=\sum_{j=0}^{n}A_{j}P(x_{j})\]
with
\[A_{j}=\int_{a}^{b}e_{j}(x)\,dx.\]
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;Gramm}]
Linear independence
shows that  ${\mathbf v}\neq {\boldsymbol 0}$. 
We have $\|{\mathbf e}_{n+1}\|=\|{\mathbf v}\|^{-1}\|{\mathbf v}\|=1$.
Now
\begin{align*}
\langle{\mathbf v},{\mathbf e}_{k}\rangle
&=\left\langle{\mathbf f}-\sum_{j=1}^{n}
\langle{\mathbf f},{\mathbf e}_{j}\rangle
{\mathbf e}_{j},{\mathbf e}_{k}
\right\rangle\\
&=\langle{\mathbf f},{\mathbf e}_{k}\rangle
-\sum_{j=1}^{n}
\langle{\mathbf f},{\mathbf e}_{j}\rangle
\langle{\mathbf e}_{k},{\mathbf e}_{j}\rangle\\
&=\langle{\mathbf f},{\mathbf e}_{k}\rangle
-\langle{\mathbf f},{\mathbf e}_{k}\rangle=0
\end{align*}
so
$\langle{\mathbf e}_{n+1},{\mathbf e}_{k}\rangle=0$
for all $1\leq k\leq n$.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;Legendre roots}]
Suppose that $p_{n}$ has $k$ roots
$\alpha_{j}$ of \emph{odd} order
(that is to say the polynomial changes sign at the root) on $(-1,1)$.
If we set $Q(t)=\prod_{j=1}^{k}(t-\alpha_{j})$,
then $p_{n}(t)Q(t)$ is a continuous single
signed not everywhere zero function so
\[\int_{-1}^{1}Q(t)p_{n}(t)\,dt\neq 0.\]
Thus $Q$ has degree at least $n$, so $k\geq n$.

It follows that $k=n$ and all of the roots of $p_{n}$ 
are simple lying in $(-1,1)$.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Gauss}]
(i) By long division, $Q=p_{n}S+T$, where $S$ and $T$
are polynomials of degree at most $n-1$. Thus
\begin{align*}
\int_{-1}^{1}&Q(x)\,dx=\int_{-1}^{1}S(x)p_{n}(x)\,dx+
\int_{-1}^{1}T(x)\,dx=\int_{-1}^{1}T(x)\,dx\\
&=\sum_{j=1}^{n}A_{j}T(\alpha_{j})
=\sum_{j=1}^{n}A_{j}T(\alpha_{j})
+\sum_{j=1}^{n}A_{j}p_{n}(\alpha_{j})S(\alpha_{j})
=\sum_{j=1}^{n}A_{j}Q(\alpha_{j}).
\end{align*}

(ii) Let $P(x)=\prod_{j=1}^{n}(x-\beta_{j})$.
If $R$ is a polynomial of degree $n-1$
or less,
then $RP$ has degree at most $2n-1$,
so
\[\int_{-1}^{1}R(x)P(x)\,dx
=\sum_{j=1}^{n}B_{j}R(\beta_{j})P(\beta_{j}).\]
Thus $\langle P,R\rangle=0$ for all polynomials
of degree $n-1$ or less, so $P$ is a scalar multiple
of the $n$th Legendre polynomial
$p_{n}$  and the $\beta_{j}$ are the roots $p_{n}$.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;nice quadrature}]
(i) Let 
\[P_{k}(x)=\left(
\prod_{j\neq k}\frac{x-x_{j}}{x_{k}-x_{j}}\right)^{2}.\]
Then $P_{k}$ has degree $2n-2$, so
\[0<\int_{-1}^{1}P_{k}(x)\,dx=\sum_{j=1}^{n}A_{j}P_{k}(\alpha_{j})=A_{k}.\]

(ii) Taking $P=1$ in the formula, we obtain
\[2=\int_{-1}^{1}1\,dx=\sum_{j=1}^{n}A_{j}.\]

(iii) We have
\begin{align*}
\left|\int_{-1}^{1}f(x)\,dx\right.&\left.-
\sum_{j=1}^{n}A_{j}f(\alpha_{j})\right|\\
&=\left|\int_{-1}^{1}\big(f(x)-P(x)\big)\,dx-
\sum_{j=1}^{n}A_{j}\big(f(\alpha_{j})-P(\alpha_{j})\big)\right|\\
&\leq\left|\int_{-1}^{1}\big(f(x)-P(x)\big)\,dx\right|
+\left| \sum_{j=1}^{n}A_{j}\big(f(\alpha_{j})-P(\alpha_{j})\big)\right|\\
&\leq \int_{-1}^{1}|f(x)-P(x)|\,dx
+\sum_{j=1}^{n}A_{j}|f(\alpha_{j})-P(\alpha_{j})|\\
&\leq 2\|f-P\|_{\infty}+\sum_{j=1}^{n}A_{j}\|f-P\|_{\infty}
\leq 4\|f-P\|_{\infty}.
\end{align*}

(iv) Let $\epsilon>0$.
By Weierstrass's theorem, we can find a polynomial
$P$ such that $\|f-P\|_{\infty}\leq\epsilon/4$.
Then, if $n$ is greater than the degree of $P$,
part~(iii) tells us that
\[\left|\int_{-1}^{1}f(x)\,dx-G_{n}f\right|\leq 4\|f-P\|_{\infty}
\leq\epsilon.\]
\end{proof}
\begin{proof}
(i) Let 
\[P_{k}(x)=\left(
\prod_{j\neq k}\frac{x-x_{j}}{x_{k}-x_{j}}\right)^{2}.\]
Then $P_{k}$ has degree $2n-2$, so
\[0<\int_{-1}^{1}P_{k}(x)\,dx=\sum_{j=1}^{n}A_{j}P_{k}(\alpha_{j})=A_{k}.\]

(ii) Taking $P=1$ in the formula, we obtain
\[2=\int_{-1}^{1}1\,dx=\sum_{j=1}^{n}A_{j}.\]

(iii) We have
\begin{align*}
\left|\int_{-1}^{1}f(x)\,dx\right.&\left.-
\sum_{j=1}^{n}A_{j}f(\alpha_{j})\right|\\
&=\left|\int_{-1}^{1}\big(f(x)-P(x)\big)\,dx-
\sum_{j=1}^{n}A_{j}\big(f(\alpha_{j})-P(\alpha_{j})\big)\right|\\
&\leq\left|\int_{-1}^{1}\big(f(x)-P(x)\big)\,dx\right|
+\left| \sum_{j=1}^{n}A_{j}\big(f(\alpha_{j})-P(\alpha_{j})\big)\right|\\
&\leq \int_{-1}^{1}|f(x)-P(x)|\,dx
+\sum_{j=1}^{n}A_{j}|f(\alpha_{j})-P(\alpha_{j})|\\
&\leq 2\|f-P\|_{\infty}+\sum_{j=1}^{n}A_{j}\|f-P\|_{\infty}
\leq 4\|f-P\|_{\infty}.
\end{align*}

(iv) Let $\epsilon>0$.
By Weierstrass's theorem, we can find a polynomial
$P$ such that $\|f-P\|_{\infty}\leq\epsilon/4$.
Then, if $n$ is greater than the degree of $P$,
part~(iii) tells us that
\[\left|\int_{-1}^{1}f(x)\,dx-G_{n}f\right|\leq 4\|f-P\|_{\infty}
\leq\epsilon.\]
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L,from compact}]
It is a standard observation about metric spaces $(X,d)$
that, since
$d(x,y)+d(y,z)\geq d(x,z)$, we have
$d(y,z)\geq d(x,z)-d(x,y)$ and similarly
$d(y,z)=d(z,y)\geq d(x,y)-d(x,z)$, so that
\[d(y,z)\geq |d(x,z)-d(x,y)|.\]

Thus, if we write $f({\mathbf x})=
\|{\mathbf a}-{\mathbf x}\|$, 
we have
\[|f({\mathbf x})-f({\mathbf y})|\leq\|{\mathbf x}-{\mathbf y}\|,\]
so $f$ is continuous and attains its minimum
on the compact set $E$.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;unique convex 1}]
(i) Consider $n=2$,
\[E=\{(x,y)\,:\,x^{2}+y^{2}=1\}
\ \text{and}\ {\mathbf e}={\boldsymbol 0}.\]
Any point of $E$ will do.

(ii) Suppose that $E$ is convex, 
${\mathbf e},\ {\mathbf f}\in E$ and
$\|{\mathbf a}-{\mathbf e}\|=\|{\mathbf a}-{\mathbf f}\|$.
Then 
\[\frac{{\mathbf e}+{\mathbf f}}{2}\in E,\]
but the parallelogram law tells us that
\begin{align*}
4\|{\mathbf a}-{\mathbf e}\|^{2}&=
2\|{\mathbf a}-{\mathbf e}\|^{2}+\|{\mathbf a}-{\mathbf f}\|^{2}\\
&=\|({\mathbf a}-{\mathbf e})+({\mathbf a}-{\mathbf f})\|^{2}
+\|({\mathbf a}-{\mathbf e})-({\mathbf a}-{\mathbf f})\|^{2}\\
&=4\left\|{\mathbf a}-\frac{{\mathbf e}+{\mathbf f}}{2}\right\|^{2}
+\|{\mathbf e}-{\mathbf f}\|^{2}
\end{align*}
and so
\[\left\|{\mathbf a}-\frac{{\mathbf e}+{\mathbf f}}{2}\right\|
\leq \|{\mathbf a}-{\mathbf e}\|\]
with equality only if ${\mathbf e}={\mathbf f}$.
(Alternatively draw a diagram and use a little school geometry
to obtain the same result.)
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;compact compact}]
 (i) Recall that, if ${\mathbf u}\in{\mathbb R}^{n}$,
then we can find ${\mathbf v}\in F$ such that
$\|{\mathbf u}-{\mathbf v}\|=d({\mathbf u},F)$.
If ${\mathbf u}'\in{\mathbb R}^{n}$, then
\[d({\mathbf u}',F)\leq\|{\mathbf u}'-{\mathbf v}\|
\leq\|{\mathbf u}'-{\mathbf u}\|+\|{\mathbf u}-{\mathbf v}\|
=\|{\mathbf u}'-{\mathbf u}\|+d({\mathbf u},F).\]
The same argument shows that
$d({\mathbf u},F)\leq
\|{\mathbf u}'-{\mathbf u}\|+d({\mathbf u}',F)$.
Thus 
\[|d({\mathbf u},F)-d({\mathbf u}',F)|\leq
\|{\mathbf u}'-{\mathbf u}\|.\]
and the map ${\mathbf u}\mapsto d({\mathbf u},F)$ is continuous.
By compactness, it attains its minimum on $E$
and this is the required result.

(ii) Choose ${\mathbf u}\in E$.
Since $F$ is bounded we can find an $R$
such that $B({\boldsymbol u},R)\supseteq F$. Let
\[E^{*}=\bar{B}({\mathbf u},2R+1)\cap E.\]
If ${\mathbf e}\in E\setminus E^{*}$, then 
$d({\mathbf e},F)\geq d({\mathbf u},F)+1$.

Since $E^{*}$ is compact, part~(i) tells us that there
exist a ${\mathbf e}\in E^{*}$ and a ${\mathbf f}\in F$
such that 
\[\|{\mathbf e}-{\mathbf f}\|=\inf_{{\mathbf y}\in E^{*}}d({\mathbf y},F)\]
and so by the previous paragraph
\[\|{\mathbf e}-{\mathbf f}\|=\inf_{{\mathbf y}\in E}d({\mathbf y},F)\]

(iii) Let $n=1$, $E=\{r+1/r\,:\,r\in{\mathbb Z},\ r\geq 2\}$
and $F=\{r\,:\,r\in{\mathbb Z},\ r\geq 2\}$.
We have $E$ and $F$ closed and $\tau(E,F)=0$, but
$|e-f|>0$ for all $e\in E$, $f\in F$.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;unique convex 2}]
Repeat the counter-example of Exercise~\ref{E;unique convex 1}.
Take $n=2$,
\[E=\{(x,y)\,:\,x^{2}+y^{2}=1\},\ F=\{{\boldsymbol 0}\}.\]
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;first try Hausdorff}]
(i) follows directly from the definition.
(Alternatively take the ${\mathbf e}$ and
${\mathbf f}$ of Lemma~\ref{L;compact compact}~(i) and observe that
$\tau(E,f)=\|{\mathbf e}-{\mathbf f}\|\geq 0$.)

Lemma~\ref{L;compact compact}~(i) also shows that
\[\tau(F,E)\leq \|{\mathbf e}-{\mathbf f}\|=\tau(E,F).\]
Interchanging $E$ and $F$, yields $\tau(E,F)\leq\tau(F,E)$
so $\tau(E,F)=\tau(F,E)$. 

If we work with $n=1$, setting $E=\{0\}$, $F=\{0,1\}$, 
gives $\tau(E,F)=0$, but $E\neq F$.

If we work with $n=1$, then 
setting $E=\{0\}$, $F=\{0,1\}$, $G=\{1\}$ 
gives $\tau(E,F)+\tau(F,G)=0+0=0$, but $\tau(E,G)=1$.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;Hausdorff try 2}]
In our proof of Lemma~\ref{L;compact compact}~(i)
we showed that the map ${\mathbf u}\mapsto d({\mathbf u},F)$
is continuous. It follows that it attains its maximum on 
the compact set $E$.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;Hausdorff try 3}]
Since $d({\mathbf e},F)\geq 0$ for all ${\mathbf e}$,
we have $\sigma(E,F)\geq 0$.

If $n=1$, $E=\{0\}$, $F=[0,1]$, then
$\sigma(E,F)=0$, but $\sigma(F,E)=1$,
so conditions~(ii)
and~(iii) fail.

\[\sigma(E,F)=0
\Leftrightarrow d({\mathbf e},F)=0\ \forall {\mathbf e}\in E
\Leftrightarrow {\mathbf e}\in F\ \forall{\mathbf e}\in E
\Leftrightarrow E\subseteq F.\]
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;start Hausdorff}]
Given ${\mathbf e}\in E$, we can find ${\mathbf f}\in F$
such that $\|{\mathbf e}-{\mathbf f}\|=d({\mathbf e},F)$.
If ${\mathbf g}\in G$, then
\begin{align*}
d({\mathbf e},G)
&\leq\|{\mathbf e}-{\mathbf g}\|\leq
\|{\mathbf e}-{\mathbf f}\|+\|{\mathbf f}-{\mathbf g}\|\\
&=d({\mathbf e},F)+\|{\mathbf f}-{\mathbf g}.\|
\end{align*}
Since ${\mathbf g}\in G$ was arbitrary,
\[d({\mathbf e},G)\leq d({\mathbf e},F)+d({\mathbf f},G)
\leq \sigma(E,F)+\sigma(F,G)\]
and so 
\[\sigma(E,G)\leq \sigma(E,F)+\sigma(F,G).\]
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Hausdorff hurrah}]
Observe that
\begin{gather*}
\rho(E,F)=\sigma(E,F)+\sigma(F,E)\geq 0\\
\rho(E,F)=0\Leftrightarrow\sigma(E,F)=\sigma(F,E)=0
\Leftrightarrow E\subseteq F,\ F\subseteq E\Leftrightarrow E=F\\
\rho(E,F)=\sigma(E,F)+\sigma(F,E)
=\sigma(F,E)+\sigma(E,F)=\rho(F,E)\\
\rho(E,F)+\rho(F,G)
=\sigma(E,F)+\sigma(F,G)+\sigma(G,F)+\sigma(F,E)\\
\geq \sigma(E,G)+\sigma(G,E)=\rho(E,G),
\end{gather*}
as desired.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;decreasing compact}]
(i) This part may be familiar from~1B. 
(Indeed the reader may
well be able to supply a more sophisticated
proof.) Since the intersection of
closed sets is closed and the intersection of bounded sets
is bounded we only have to show that $K$ is non-empty.
 
Choose
${\mathbf x}_{n}\in K_{n}$. Since $K_{1}$ is compact and 
${\mathbf x}_{n}\in K_{1}$ for every $n$ we can find
an ${\mathbf x}\in K_{1}$ and $n(j)\geq j$ such
that  ${\mathbf x}_{n(j)}\rightarrow{\mathbf x}$
(in the Euclidean metric) as $j\rightarrow\infty$

Automatically, 
\[{\mathbf x}_{n(j)}\in K_{n(j)}\subseteq K_{j}\subseteq K_{p}\]
for all $j\geq p$, so, since $K_{p}$ is closed,
${\mathbf x}\in K_{p}$ for all $p\geq 1$. It follows
that ${\mathbf x}\in K$ and $K$ is non-empty.

(ii) Since $K\subseteq K_{p}$ it follows
that
\[\rho(K,K_{p})=\sup_{{\mathbf e}\in K_{p}}\inf_{{\mathbf k}\in K}
\|{\mathbf e}-{\mathbf k}\|\]
and, in particular that $\rho(K,K_{p})$ is a decreasing 
positive sequence. 

Thus if $K_{p}\underset{\rho}{\nrightarrow}K$ there must exist an
$\eta>0$ with
\[\rho(K,K_{p})\geq 2\eta\]
and there must exist ${\mathbf k}_{p}\in K_{p}$
with
\[\|{\mathbf k}_{p}-{\mathbf k}\|\geq\eta\]
for all ${\mathbf k}\in K$.

Since $K_{1}$ is compact and 
${\mathbf k}_{p}\in K_{1}$ for every $p$ we can find
an ${\mathbf x}\in K_{1}$ and $p(j)\geq j$ such
that  ${\mathbf k}_{p(j)}\rightarrow{\mathbf x}$
(in the Euclidean metric) as $j\rightarrow\infty$.
As in part~(i), we know that ${\mathbf x}\in K$
so 
\[\|{\mathbf k}_{p(j)}-{\mathbf x}\|\geq\eta.\]
for all $j$ giving us a contradiction.

Part~(ii) follows by reductio ad absurdum.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;extend compact}]
If ${\mathbf z}_{n}\in K+\bar{B}(0,r)$, then
${\mathbf z}_{n}={\mathbf x}_{n}+{\mathbf y}_{n}$
with ${\mathbf x}_{n}\in K$, $\|{\mathbf y}_{n}\|\leq r$.
By compactness, we can first extract a convergent subsequence
${\mathbf x}_{n(j)}\in K$ and then a convergent
subsequence ${\mathbf y}_{n(j(k))}\in \bar{B}(0,r)$.
It follows that 
${\mathbf z}_{n(j(k))}={\mathbf x}_{n(j(k))}+{\mathbf y}_{n(j(k))}$
converges to a point in $K+\bar{B}(0,r)$ so we are done.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Hausdorff complete}] By
Lemma~\ref{L;fast Cauchy}, it suffices to show that, if
we have sequence of non-empty compact sets with
$\rho(E_{n},E_{n+1})<8^{-n}$ for $n\geq 1$, then the
sequence converges. Set 
\[K_{n}=E_{n}+\bar{B}(0,6\times 8^{-n}).\]
Then $K_{n}$ is compact and $\rho(E_{n},K_{n})=6\times 8^{-n}$,
so it is sufficient to show that $K_{n}$ converges.

To do this, we observe that $K_{n+1}\subseteq K_{n}$ and
so we may apply Theorem~\ref{T;decreasing compact}.
\end{proof}
\begin{proof}[Proof for Example~\ref{E;conjugate}]
Observe that, taking $C$ to be the
contour $z=e^{i\theta}$ as $\theta$ runs from $0$ to $2\pi$,
we have
\begin{align*}
\sup_{z\in\bar{D}}|f(z)-p(z)|&
\geq\frac{1}{2\pi}\left|\int_{C}f(z)-p(z)\,dz\right|\\
&=\frac{1}{2\pi}\left|\int_{C}f(z)\,dz\right|
=\frac{1}{2\pi}
\left|\int_{0}^{2\pi}e^{-i\theta}ie^{i\theta}\,d\theta\right|\\
&=\frac{1}{2\pi}\left|\int_{0}^{2\pi}i\,d\theta\right|
=1.
\end{align*}
\end{proof}
\begin{proof}[Proof for Example~\ref{E;polo}]
By exactly the same computations as in 
Example~\ref{E;conjugate}, 
\[\sup_{z\in T}|f(z)-p(z)|
\geq\frac{1}{2\pi}\left|\int_{C}f(z)-p(z)\,dz\right|
=1.\]
\end{proof}
\begin{proof}[Solution for Exercise~\ref{E;no single power}]

  (i) Just observe that
\[\frac{1}{z}=\frac{1}{w+(z-w)}=\frac{1}{w(1+(z-w)/w)}=
\sum_{j=0}^{\infty}\frac{(-1)^{j}(z-w)^{j}}{w^{j+1}}\]
for $|(z-w)/w|<1$.

(ii) It is easy to check that $\Omega$ is open and bounded.
To see that $\Omega$ is connected, suppose that 
$w_{1},\,w_{2}\in\Omega$. Then we can find $r_{k}$
and $\theta_{k}$ with $10^{-2}<r_{k}<1$
and $-\pi<\theta<\pi$ such that
$w_{k}=r_{k}e^{i\theta_{k}}$ $[k=1,\,2]$.
If we define $\gamma:[0,1]\rightarrow\Omega$ by
\[\gamma(t)=\big((1-t)r_{1}+tr_{2}\big)
\exp\big(i(1-t)\theta_{1}+it\theta_{2}\big),\]
then $\gamma$ gives a path from $w_{1}$ to $w_{2}$.

Suppose, if possible, that
\[z^{-1}=\sum_{j=0}^{\infty}b_{j}(z-z_{0})^{j}\]
for all $z\in\Omega$. Then the power series
converges on some open disc $D$ centre $z_{0}$
with $D\supseteq \Omega$. Thus 
$D\supseteq\{z\,:\,|z|<1\}$. By Lemma~\ref{L;unique analytic},
\[z^{-1}=\sum_{j=0}^{\infty}b_{j}(z-z_{0})^{j}\]
for all $z$ with $0<|z|<1$. Allowing $z\rightarrow 0$,
gives a contradiction.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;Runge contour}]
We may suppose 
$K$ non-empty. 
Since $K$ is compact, ${\mathbb C}\setminus\Omega$
closed and the two sets are disjoint, it follows that 
$\eta=\tau(K,{\mathbb C}\setminus\Omega)/8>0$
(i.e. $|k-w|>8\eta$ for all $k\in K$, $w\notin\Omega$).

Consider a grid of squares side $\eta$. We consider the
collection $\Gamma$ of closed squares $S$ lying entirely
within $\Omega$ with boundary contours $C(S)$.
Observe that 
\[\bigcup_{S\in\Gamma}C(S)\supseteq\{k+u\,:k\in K,\ |u|\leq2\eta\}\] 
By Cauchy's theorem
\[f(z)=\frac{1}{2\pi i}\sum_{S\in\Gamma}\int_{C(S)}\frac{f(w)}{w-z}\,dw\]
for all $z\in K$ such that $z$ does not lie on the boundary
of some $S$. By cancelling internal sides, 
\[f(z)=\sum_{m=1}^{M}\int_{C_{m}}\frac{f(w)}{w-z}\,dw\tag*{$\bigstar$}\]
with the piece-wise linear contours $C_{m}$ $[1\leq m\leq M]$
lying entirely within $\Omega\setminus K$.

We deal with the case when  $z$ lies on the boundary
of some $S$ by erasing any sides through $z$ and repeating the
argument with the new (non-regular) grid. (Alternatively,
we could observe that both sides of equation $\bigstar$
are continuous.)
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;note Runge}]
Observe that
$K$ and $\bigcup_{m=1}^{M} C_{m}$ are compact and disjoint.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L:Runge to simple}]
By  Lemma 11.13 it is sufficient to show that,
if $C$ is a straight line segment joining
lying in $\Omega\setminus K$,
then, given $\epsilon$, we can find $B_{m}\in{\mathbb C}$ and 
$\beta_{m}\in C$ with 
\[\left|\frac{1}{2\pi i}\int_{C}\frac{f(w)}{w-z}\,dw
-\sum_{m=1}^{M}\frac{B_{m}}{z-\beta_{m}}\right|
<\epsilon\]
for all $z\in K$.

To this end, note that
\[\frac{1}{2\pi i}\int_{C}\frac{f(w)}{w-z}\,dw
=\int_{0}^{1}F(t,z)\,dt\]
where $F:[0,1]\times K\rightarrow{\mathbb C}$
is defined by
\[F(t,z)=\frac{1}{2\pi i}\frac{f(\gamma(t))}{\gamma(t)-z}\gamma'(t)\]
with $\gamma(t)=(1-t)z_{1}+tz_{2}$.
Since $[0,1]\times K$ is compact and $F$ is continuous, $F$ must
be uniformly continuous so there exists a $\delta>0$
such that
\[|F(t,z)-F(s,z)|<\epsilon\ \text{for all}\ |t-s|<\delta.\]
If we choose an integer $M>\delta^{-1}$ and set
$F_{M}(t,z)=F(m/M,z)$ whenever $(m-1)/M<t\leq m/M$ $[1\leq m\leq M]$,
then $|F(t,z)-F_{M}(t,z)|\leq\epsilon$ so
\[\left|\int_{0}^{1}F(t,z)\,dt-\int_{0}^{1}F_{M}(t,z)\,dt\right|
\leq \epsilon.\]
Since 
\[\int_{0}^{1}F_{M}(t,z)\,dt=\sum_{m=1}^{M}\frac{B_{m}}{z-\beta_{m}}\]
for appropriate $B_{m}$ and $\beta_{m}$, we are done.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Runge}
from Lemma~\ref{L;simple Runge 1}]
We use the result and notation of Lemma~\ref{L:Runge to simple}.
Choose polynomials $P_{n}$ such that
\[\left|P_{n}(z)-\frac{1}{z-\alpha_{n}}\right|
\leq\frac{\epsilon}{(N+1)(|A_{n}|+1)}\]
for all $z\in K$. Then, if 
\[P(z)=\sum_{n=1}^{N}A_{n}P_{n}(z),\]
$P$ is a polynomial and
\begin{align*}
|f(z)-P(z)|&\leq 
\left|f(z)-\sum_{n=1}^{N}\frac{A_{n}}{z-\alpha_{n}}\right|
+\sum_{n=1}^{N}|A_{n}|
\left|P_{n}(z)-\frac{1}{z-\alpha_{n}}\right|\\
&\leq \epsilon+N\frac{\epsilon}{N+1}\leq 2\epsilon.
\end{align*}
Since $\epsilon$ was arbitrary the result follows.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;far Runge}]
Since $K$ is compact, it is bounded and
we can find an $R>0$ such that $|z|<R/2$ whenever
$z\in K$. The standard geometric series result shows
that if $|\alpha|>R$
\[\frac{-1}{\alpha}\sum_{r=0}^{n}\frac{z^{r}}{\alpha^{r}}
\rightarrow \frac{-1}{\alpha}\times \frac{1}{1-(z/\alpha)}
= \frac{1}{z-\alpha}\]
uniformly for $|z|\leq R/2$ and so for $z\in K$.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;simple Runge 2}]
Since $\alpha\in\Lambda(K)$ we know that there
exists a sequence
of polynomials $P_{n}$ such that
\[P_{n}(z)\rightarrow\frac{1}{z-\alpha}\]
uniformly on $K$. Moreover, since (by compactness)
$z\mapsto(z-\alpha)^{-1}$ is bounded on $K$,
the $P_{n}$ are uniformly bounded.

On the other hand,
\[\frac{1}{z-\beta}=\frac{1}{z-\alpha-(\beta-\alpha)}
  =\frac{1}{z-\alpha}\times
  \frac{1}{1-\frac{\beta-\alpha}{z-\alpha}}.\]
Since 
\[\left|\frac{\beta-\alpha}{z-\alpha}\right|
\leq \frac{|\beta-\alpha|}{d(\alpha,K)}
<1\]
for all $z\in K$, we know that, given $\epsilon>0$, 
there exists an $N$ with
\[\left|\frac{1}{z-\beta}-\sum_{j=0}^{N}
\frac{(\beta-\alpha)^{j}}{(z-\alpha)^{j+1}}\right|
<\epsilon/2\]
for all $z\in K$. By the first paragraph, we can find an $M$
such that
\[\left|
\frac{(\beta-\alpha)^{j}}{(z-\alpha)^{j+1}}
-(\beta-\alpha)^{j}P_{M}(z)^{j}\right|<\epsilon/(2N+4)\]
for each $0\leq j\leq N$ and so
\[\left|\frac{1}{z-\beta}-\sum_{j=0}^{N}
(\beta-\alpha)^{j}P_{M}(z)^{j}\right|
<\epsilon\]
for all $z\in K$. We have shown that $\beta\in\Lambda(K)$. 
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;simple Runge 3}]
  Let $a\in {\mathbb C}\setminus K$. By 
Lemma~\ref{L;far Runge}, $\Lambda(K)$ is non-empty
so we may choose a $b\in\Lambda(K)$.
Since ${\mathbb C}\setminus K$ is path connected 
we can find a continuous 
$\gamma:[0,1]\rightarrow {\mathbb C}\setminus K$
with $\gamma(0)=b$, $\gamma(1)=a$. The continuous image of
a compact set is compact and $\gamma([0,1])\cap K=\emptyset$
so (see  Lemma~\ref{L;compact compact}) there exists a $\delta>0$
such that $|\gamma(t)-k|>\delta$ for all $k\in K$ and all
$t\in[0,1]$.

By uniform continuity, we can find an $N$ such that
\[|s-t|\leq 1/N\Rightarrow |\gamma(t)-\gamma(s)|<\delta/2.\]
Writing $x_{r}=\gamma(r/N)$, we see that $x_{0}=b\in \Lambda(K)$
and, applying Lemma~\ref{L;simple Runge 2},
\[x_{r-1}\in \Lambda(K)\Rightarrow x_{r}\in \Lambda(K)\]
for $1\leq r\leq N$. Thus $a=x_{N}\in \Lambda(K)$
and we are done.
\end{proof}
\begin{proof}[Proof of Example~\ref{E;bite round}]
  Consider the map $T_{n}$ given by
\[T_{n}(z)=(2^{-n}+z)\exp(-2^{-n}i\pi)\]
(a translation followed by a rotation). 

Let $g_{n}=T_{n}^{-1}fT_{n}$ and 
\[l_{n}=\{r\exp(i2^{-n})-2^{-n}\,:\,r\in{\mathbb R},\ r\geq 0\}
=T_{n}^{-1}\{x\,:\,x\in{\mathbb R},\ x\geq 0\}\]
so $g_{n}$ is analytic on ${\mathbb C}\setminus l_{n}$.                          
We see that $g_{n}(z)\rightarrow f(z)$ pointwise
as $n\rightarrow\infty$.  
(The reader may find it convenient
to examine the case when $z=x$ with $x$ real and $x\geq 0$
separately.)

We now set
\[U_{n}=l_{n}+\Int D(0,2^{-8n})=\{z+w,\,:\,z\in l_{n},\ |w|<2^{-8n}\}\]
so that $U_{n}$ is open and $U_{n}\cap U_{m}=\emptyset$ for $n\neq m$.
Finally we take
\[K_{n}=\Cl{D}\setminus U_{n}\]
so that $K_{n}$ is compact. By Runge's theorem we can
find a polynomial $P_{n}$ such that $|P_{n}(z)-g_{n}(z)|\leq 2^{-n}$
for all $z\in K_{n}$.

Now choose a particular $z\in D$. We know that there exists
an $N$ (depending on $z$) such that $z\in K_{n}$ for all $n\geq N$.
Considering only $n\geq N$, we have $|P_{n}(z)-g_{n}(z)|\rightarrow 0$
and (as we observed in the first paragraph) $g_{n}(z)\rightarrow f(z)$
so  $P_{n}(z)\rightarrow f(z)$ as $n\rightarrow\infty$. 
Since $z$ was arbitrary, we are done.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;irrational exponential}]
  This is probably familiar from 1A. 

Suppose, if possible, that $e=p/q$ with $p$ and $q$
integers and $q\geq 2$. Then
\[q!e\ \text{and}\ q!\sum_{r=0}^{q}\frac{1}{r!}\]
are integers so
\[M=q!\sum_{r=q+1}^{\infty}\frac{1}{r!}=
q!e-q!\sum_{r=0}^{q}\frac{1}{r!}\]
is an integer. But
\[
0<M= q!\sum_{r=q+1}^{\infty}\frac{1}{r!}
\leq \sum_{r=q+1}^{\infty}\frac{1}{q^{r-q}}
=\frac{1}{q}\times\frac{1}{1-q^{-1}}
=\frac{1}{q-1}<1
\]
and there is no integer strictly between $0$ and $1$.
Our assumption has led to a contradiction so
$e$ must be irrational.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;onto pi}]
Observe that 
\[f_{n}(x)=\sum_{s=0}^{n}\binom{n}{s}\pi^{n-s}x^{n+s}\]
Thus 
\[f^{(r)}(0)=0\]
if $0\leq r\leq n-1$ or $2n+1\leq r$ and
\[f^{(n+r)}(0)=(n+r)!\binom{n}{r}\pi^{n-r}\]
for $0\leq r\leq n$.
By symmetry about $\pi/2$,
\[f^{(r)}(\pi)=(-1)^{r}f^{(r)}(0).\]
Thus $f^{(r)}(0)$ and $f^{(r)}(\pi)$
always take the form of $M\times n!\times \pi^{k}$ 
where $M$ is an integer and $k$ is an integer with
$0\leq k\leq n$.

Now integration by parts gives
\begin{align*}
\int_{0}^{\pi}f^{(m)}(x)\cos x\,dx
&=\left[f^{(m)}(x)\sin x\right]_{0}^{\pi}
-\int_{0}^{\pi}f^{(m+1)}(x)\sin x\,dx\\
&=-\int_{0}^{\pi}f^{(m+1)}(x)\sin x\,dx
\end{align*}
and
\begin{align*}
\int_{0}^{\pi}f^{(m)}(x)\sin x\,dx
&=-\left[f^{(m)}(x)\cos x\right]_{0}^{\pi}
+\int_{0}^{\pi}f^{(m+1)}(x)\cos x\,dx\\
&=(f^{(m)}(\pi)-f^{(m)}(0))+\int_{0}^{\pi}f^{(m+1)}(x)\cos x\,dx.
\end{align*} 
Thus integration by parts $2n+1$ times
gives
\[\int_{0}^{\pi}f(x)\sin x\,dx=n!U(\pi)\]
where $U$ is a polynomial 
of degree at most $n$ with integer coefficients.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;pi} from Lemma~\ref{L;onto pi}]
Suppose that $\pi=p/q$ with $p$ and $q$ integers
and $q\geq 1$. It follows from Lemma~\ref{L;onto pi}
that
\[\frac{q^{n}}{n!}\int_{0}^{\pi}f_{n}(x)\sin x\,dx
=q^{n}\sum_{j=0}^{n}a_{j}\pi^{j}=\sum_{j=0}^{n}a_{j}q^{n-j}p^{j}
\in{\mathbb Z}.\]
But (by school calculus or completing the square or
the AM-GM inequality) $x(\pi-x)$ takes its maximum
when $x=\pi/2$ so
\[0\leq f_{n}(x)\leq (\pi/2)^{2n}\]
and, since $f_{n}(x)\sin x$ is strictly positive
for $0<x<\pi$,
\[0<\int_{0}^{\pi}f_{n}(x)\sin x\,dx
\leq\int_{0}^{\pi} (\pi/2)^{2n}\,dx=\pi^{2n+1}2^{-2n}.\]
Thus
\[0<\frac{q^{n}}{n!}\int_{0}^{\pi}f_{n}(x)\sin x\,dx
\leq  \frac{1}{n!}\pi^{2n+1}2^{-2n}q^{n}<1\]
for $n$ sufficiently large.

However there is no integer strictly between $0$ and $1$.
Our assumption has led to a contradiction.
Thus $\pi$ is irrational.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;algebraic numbers}]
\emph{Only if} is trivial since integers are rational numbers.

To see \emph{if}, observe that, if $\alpha$ satisfies
\[\sum_{j=0}^{N}\frac{p_{j}}{q_{j}}\alpha^{j}=0\]
with $p_{j}$, $q_{j}$ integers, $q_{j}\neq 0$ for all
$j$, $p_{N}\neq 0$, $N\geq 1$, then
\[\sum_{j=0}^{N}p_{j}\prod_{i\neq j}q_{i}\alpha^{j}=0.\]
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;algebraic countable}]
This was done in 1A. There are only finitely
many polynomials of the form
\[\sum_{j=0}^{N}a_{j}x^{j}\]
with $n\geq N\geq 1$, $a_{N}\neq 0$ and all $a_{j}$
integers with $|a_{j}|\leq n$. 
A polynomial has only finitely many roots,
so the set $E_{n}$ of roots of such polynomials
is finite so countable. Thus $E=\bigcup_{n=1}^{\infty}E_{n}$
is the countable union of countable sets so countable.
But $E$ is the set of algebraic numbers, so we are done.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Liouville}]
  Let
\[P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\dots+a_{0}.\]
Since
a polynomial has only finitely many roots,
we can find an $R\geq 1$ such that all the
roots of $P$ lie in $[-R+1,R-1]$. If we take $0<c\leq 1$,
the required result will be automatic for
$p/q\notin[-R,R]$. 

Now $P'$ is continuous, so, by compactness,
there exists an $M>1$ such that $|P'(t)|\leq M$
for $t\in [-R,R]$. (We could also prove this directly.)
If $\alpha$ is an irrational root,
$p,\,q\in{\mathbb Z}$ with $q\neq 0$,
$p/q\in [-R,R]$ and $P(p/q)\neq 0$, then
the mean value theorem yields
\[|P(\alpha)-P(p/q)|\leq M\left|\alpha-\frac{p}{q}\right|\]
so, since $P(\alpha)=0$, 
\[|P(p/q)|\leq M\left|\alpha-\frac{p}{q}\right|.\]
Now $q^{n}P(p/q)$ is a non-zero integer, so
$|q^{n}P(p/q)|\geq 1$ and
\[q^{-n}\leq M\left|\alpha-\frac{p}{q}\right|,\]
that is to say
\[M^{-1}q^{-n}\leq\left|\alpha-\frac{p}{q}\right|.\]

Since there are only a finite number of roots
and so only a finite number of irrational roots,
we know that there is a $c'>0$ such that
\[\left|\alpha-\frac{p}{q}\right|\geq c'q^{-n}\] 
whenever $\alpha$ is an irrational root,
$p,\,q\in{\mathbb Z}$ with $q\neq 0$ and $P(p/q)=0$.

Taking $c=\min\{M^{-1},c',1\}$, we have the required result.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Liouville number}]
Let 
\[L=\sum_{n=0}^{\infty}\frac{1}{10^{n!}}.\]
We observe that $L$ is irrational since its decimal 
expansion is not recurring.
If $q_{m}=10^{m!}$ and 
\[p_{m}=q_{m}\sum_{n=0}^{m}\frac{1}{10^{n!}},\]
then $p_{m}$ and $q_{m}$ are integers with $q_{m}\neq 0$.

We observe that
\[
\left|L-\frac{p_{m}}{q_{m}}\right|
=\sum_{j=m+1}^{\infty}\frac{1}{10^{j!}}
\leq \frac{1}{10^{(m+1)!}} \sum_{j=0}^{\infty}\frac{1}{10^{j}}
\leq\frac{2}{10^{(m+1)!}}
\]
and, given any $c>0$ and any integer $n\geq 1$, we can find an 
$m$ such that
\[\left|L-\frac{p_{m}}{q_{m}}\right|\leq \frac{2}{10^{(m+1)!}}
< \frac{c}{q^{n}}.\]

Thus Theorem~\ref{T;Liouville} tells us that
$L$ is transcendental.
\end{proof}
\begin{proof}[Solution of
 Exercise~\ref{E;uncountable Liouville}]
  Essentially 
the same argument as for Theorem~\ref{T;Liouville number}
tells us that
\[\sum_{n=0}^{\infty}\frac{b_{j}}{10^{n!}}\]
with $b_{j}\in\{1,\,2\}$ is transcendental.

The map
\[\theta:\{0,1\}^{\mathbb N}\rightarrow{\mathbb R}\]
given by
\[\theta({\boldsymbol \zeta})
=\sum_{n=0}^{\infty}\frac{\zeta(j)+1}{10^{n!}}\]
is injective and its image (as we have just seen) consists
of transcendental numbers. Since, as we
saw in 1A, the set $\{0,1\}^{\mathbb N}$ is uncountable
and $\theta$ is injective, $\theta({\mathbb N})$ is uncountable
and  we are done.
\end{proof}
\begin{proof}[Proof of Theorem\ref{T;Baire}]
We construct $x_{j}\in X$ and $\delta_{j}>0$
inductively as follows. Choose any $x_{0}\in X$ and
set $\delta_{0}=1$.

Suppose that $x_{j}$ and $\delta_{j}$ have been found. Since
$X\setminus U_{j+1}$ has empty interior, we can find
an $x_{j+1}\in U_{j+1}$ with $d(x_{j+1},x_{j})\leq \delta_{j}/4$.
Since $U_{j+1}$ is open we can find a $\delta_{j+1}>0$
with $\delta_{j+1}\leq\delta_{j}/4$ such that
$B(x_{j+1},\delta_{j+1})\subseteq U_{j+1}$.

By induction, $\delta_{j+k}\leq 4^{-k}\delta_{j}$ for $j,k\geq 0$,
so,
if $m\geq n\geq 0$,
\begin{align*}
d(x_{n},x_{m})&\leq\sum_{r=0}^{m-n-1}d(x_{n+r},x_{n+r+1})\\    
&\leq \sum_{r=0}^{m-n-1}\delta_{n+r}/4\leq
\sum_{r=0}^{m-n-1}\delta_{n}4^{-r-1}\leq \delta_{n}/2,
\end{align*}
so the sequence $x_{n}$ is Cauchy and so converges to
some point $a$.

We observe that
\[d(x_{n},a)\leq d(x_{n},x_{m})+d(x_{m},a)
\leq \delta_{n}/2+d(x_{m},a)\rightarrow  \delta_{n}/2\]
as $m\rightarrow\infty$. Thus
\[a\in B(x_{j},\delta_{j})\subseteq U_{j}\]
for all $j\geq 1$ and
\[a\in\bigcap_{j=1}^{\infty}U_{j}.\]
The result is proved
\end{proof}
\begin{proof}[Proof of the equivalence of Theorems~\ref{T;Baire}
and~\ref{T;complement Baire}] Set $F_{j}=X\setminus U_{j}$.
\end{proof}
\begin{proof}[Proof of the equivalence of Theorems~\ref{T;Baire}
and~\ref{T;informal}]
Let $x$ have the property $P_{j}$ if
and only if $x\notin U_{j}$.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;Baire obvious}]
(i) This is just a restatement of 
Theorem~\ref{T;complement Baire}.

(ii) The countable union of countable sets is countable.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;no isolated}]
Suppose that $(E,d)$ is a non-empty countable
complete space with no isolated points.
Then each $\{e\}$ with $e\in E$ is closed
(since singletons are always closed in metric spaces).
However, since $e$ not isolated,
$B(x,\delta)\not\subseteq \{e\}$ for all $\delta>0$,
so $\{e\}$ is not open and $\{e\}$ has empty interior.
Thus $E$ is the countable union of closed sets
$\{e\}$ with empty interior contradicting
Theorem~\ref{T;complement Baire}.
The required result follows by reductio ad absurdum.
\end{proof}
\begin{proof}[Proof of Corollary~\ref{C;Cantor}]
Observe that ${\mathbb R}$ with the usual metric
is complete without isolated points.
Theorem~\ref{T;no isolated} now tells us that
${\mathbb R}$ is uncountable.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;nowhere}]
  Banach's clever idea is to consider the set
$E_{m}$ consisting of all those $f\in C([0,1])$
such that there exists an $x\in[0,1]$ 
with the property
\[|f(x)-f(y)|\leq m|x-y|\]
for all $y\in[0,1]$. Our proof falls into several parts.

(a) We show that, if $f$ is differentiable at some point
$x\in [0,1]$, then there exists a positive integer $m$
such that $f\in E_{m}$. It will then follow that
any
$g\in C([0,1])\setminus\bigcup_{m=1}^{\infty}E_{m}$
is nowhere differentiable.

To this end,  suppose that $f$ is differentiable
at $x$. We can find an $\epsilon>0$ such  that
\[\left|\frac{f(x+h)-f(x)}{h}-f'(x)\right|\leq 1\]
for all $0<|h|<\epsilon $, when $x+h\in [0,1]$.
Thus
\[|f(x+h)-f(x)|\leq (|f'(x)|+1)|h|\]
for all $0<|h|<\epsilon $ when $x+h\in [0,1]$.
We thus have
\[|f(x)-f(y)|\leq (|f'(x)|+1)|x-y|\]
for all $y\in[0,1]$ such that $|y-x|<\epsilon$.
If we choose $m$ with $m\geq |f'(x)|+1$ and
$m\geq 2K\epsilon^{-1}$, we will have $f\in E_{m}$.

(b) We now show that $E_{m}$ is closed. 

Suppose that $f_{n}\in E_{m}$ and 
$\|f_{n}-f\|_{\infty}\rightarrow 0$.
By definition, there exists an $x_{n}\in[0,1]$ with the property
\[|f_{n}(x_{n})-f(y)|\leq m|x_{n}-y|\]
for all $y\in[0,1]$. By the Bolzano--Weierstrass
property, we can find $x\in[0,1]$
and $n(r)\rightarrow\infty$ such that
$x_{n(r)}\rightarrow x$ as $r\rightarrow\infty$.

Let $y\in [0,1]$. We have
\begin{align*}
|f(x)-f(y)|&\leq |f(x)-f(x_{n(r)})|
+|f(x_{n(r)})-f_{n(r)}(x_{n(r)})|\\
&\qquad\qquad+|f_{n(r)}(x_{n(r)})-f_{n(r)}(y)|
+|f_{n(r)}(y)-f(y)|\\
&\leq 2\|f-f_{n(r)}\|_{\infty}+|f(x)-f(x_{n(r)})|
+m|x_{n(r)}-y|\\
&\rightarrow 0+0+m|x-y|=m|x-y|.
\end{align*}
Since $y$ was arbitrary, $f\in E_{m}$.

(c) Next we show that $E_{m}$ has a dense complement.

Suppose that $f\in C([0,1])$ and $\epsilon>0$.
By Weierstrass's theorem on polynomial 
approximation (see Theorem~\ref{T;Bernstein}),
we can find a polynomial $P$ such that
\[\|f-P\|_{\infty}\leq \epsilon/3.\]
Since $P$ is continuously differentiable,
there is a $K$ such that $|P'(t)|\leq K$
for all $t\in[0,1]$. By the mean value theorem,
it follows that
\[|P(x)-P(y)|\leq K|x-y|\]
for all $x,\,y\in[0,1]$.

Let $g(t)=P(t)+(\epsilon/3)\cos 2\pi Nt$. Automatically,
\[\|g-f\|_{\infty}\leq \|f-P\|_{\infty}+\epsilon/3
\leq 2\epsilon/3<\epsilon.\] 
We claim that, provided only that $N$ is large enough,
$g\notin E_{m}$.

To see this choose $r$ an integer with $0\leq r\leq N-1$
such that $0\leq x-r/N\leq 1/N$. We have
\begin{align*}
\max\{|g(r/N)-g(x)|&,|g((r+1)/N)-g(x)|\}\\
&\geq\frac{|g(r/N)-g(x)|+|g((r+1)/N)-g(x)|}{2}\\
&\geq\frac{|g(r/N)-g((r+1)/N)|}{2}\\
&\geq\frac{2\epsilon/3-|P(r/N)-P((r+1)/N)|}{2}\\
&\geq \epsilon/3-K/N\geq \epsilon/6\geq 4m/N.
\end{align*}
Thus at least one of the statements
\[|g(r/N)-g(x)|>m|r/n-x|\ \text{or}
\ |g((r+1)/N)-g(x)|>m|(r+1)/n-x|\]
is true for $N$ sufficiently large (with 
$N$ not depending on the choice of $x$).

(d) Thus $\bigcup_{m=1}^{\infty}E_{m}$ is a set of first category
and  we are done.
\end{proof}
\begin{proof}[Proof of Corollary~\ref{C;perfect}]
Observe that
a closed subset of a complete metric space
is complete under the inherited metric
and that ${\mathbb R}$ is complete under the standard metric.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;splendid isolation}]
(i) Suppose that $E_{n}\in {\mathcal E}_{k}$
and $E_{n}\rightarrow E$ in the Hausdorff metric.
By definition, we can find $x_{n}\in E_{n}$ with
$B(x_{n},1/k)\cap E=\{x_{n}\}$. By Bolzano--Weierstrass,
we can find $n(j)\rightarrow\infty$ and $x\in[0,1]$
such that $|x_{n}(j)-x|\rightarrow 0$. We observe
that $x\in E$.

Suppose, if possible, that $B(x,1/k)\cap E\neq\{x\}$.
Then we can find a $y\in E$ such that $|x-y|<1/k$.
Set $\delta=(1/k-|x-y|)/2$. Since
$E_{n}\rightarrow E$ and $n(j)\rightarrow\infty$,
we can find a $J$ such that the Hausdorff distance 
$\rho(E_{n(J)},E)<\delta$ and so there exists a
$y'\in E_{n(J)}$ with $|y'-y|<\delta$ and so with
$|x_{n(J)}-y'|<1/k$, contrary to our hypothesis.

Thus  $E\in {\mathcal E}_{k}$ and ${\mathcal E}_{k}$
is closed.

(ii) Let $G\in{\mathcal K}$ and let $\epsilon>0$.
Choose an integer $N>5(\epsilon^{-1}+k+1)$.
Let
\[F=\{r/N\,:\,|r/N-x|\leq 4/N\ \text{for some $x\in G$}\}.\]
By construction,  
\[\sigma(G,F)=\sup_{{\mathbf y}\in G}d(y,F)\leq 1/N
\ \text{and}
\ \sigma(F,G)=\sup_{{\mathbf y}\in F}d(y,G)\leq 4/N\]
so
\[\rho(G,F)=\sigma(G,F)+\sigma(F,G)\leq 5/N<\epsilon\]
But, if $y\in G$, then either $y+1/N$ or $y-1/N$
(or both) lies in $G$, so $G\notin {\mathcal E}_{k}$.

(iii) Observe that 
${\mathcal E}=\cup_{k=1}^{\infty}{\mathcal E}_{k}$.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;empty interior}]
(i) Suppose that $F_{n}\in {\mathcal F}_{j,k}$
and $F_{n}\rightarrow F$ in the Hausdorff metric.
By definition, $F_{n}\supseteq[j/k,(j+1)/k]$, so
$F\supseteq[j/k,(j+1)/k]$.

Thus ${\mathcal F}_{j,k}$ is closed.

(ii) Let $G\in{\mathcal K}$ and let $\epsilon>0$.
Choose an integer $N>2\epsilon^{-1}+1$.
Let
\[E=\{r/N\,:\,|r/N-x|\leq 1/N\ \text{for some $x\in G$}\}.\]
By construction,  
\[\sigma(G,E)=\sup_{{\mathbf y}\in G}d(y,E)\leq 1/N
\ \text{and}
\ \sigma(E,G)=\sup_{{\mathbf y}\in E}d(y,G)\leq 1/N\]
so
\[\rho(G,E)=\sigma(G,E)+\sigma(E,G)\leq 2/N<\epsilon\]
but $E\notin{\mathcal F}_{j,k}$.

(iii) Observe that 
${\mathcal F}=\bigcup_{k=1}^{\infty}\bigcup_{j=0}^{k}{\mathcal F}_{j,k}$,
so ${\mathcal F}$ is the countable union of closed nowhere dense sets.
\end{proof} 
\begin{proof}[Proof of Theorem~\ref{T;many Cantor}]
With the notation of
Lemmas~\ref{L;splendid isolation} and~\ref{L;empty interior},
\[{\mathcal K}\setminus{\mathcal C}={\mathcal E}\cup{\mathcal F}.\]
Since the union of two first category sets is of first category,
${\mathcal K}\setminus{\mathcal C}$ is of the first category.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;many witches}]
(i) (This may be familiar from~1B.) Set
\[g_{n}(x)=
\begin{cases}
2^{2n}x&\text{if $0\leq x\leq 2^{-n-1}$,}\\
2^{2n}(2^{-n}-x)&\text{if $2^{-n-1}\leq x\leq 2^{-n}$,}\\
0&\text{otherwise.}
\end{cases}\]
If $x\neq 0$, then $x\geq 2^{-m}$ for some $m$
and so $g_{n}(x)=0$ for $n\geq m$. Since $g_{n}(0)=0$
for all $n$, we have $g_{n}(x)\rightarrow 0$ as 
$n\rightarrow\infty$ for all $x$.

However,
\[\sup_{t\in[0,1]}g_{n}(t)=g(2^{-n-1})=2^{n-1}\rightarrow\infty\]
as $n\rightarrow\infty$.

(ii) Extend $g_{n}$ to a function on ${\mathbb R}$ by setting
$g_{n}(t)=0$ for $t\notin[0,1]$.  
Set $f_{n}(t)=\sum_{j=1}^{\infty}2^{-j}g_{n}\big(2^{j}(t-2^{-j})\big)$
and use~(i).
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;bound on interval}]
Observe that
\[E_{n,m}=\{x\,:\,|f_{n}(x)|\leq m\}=f_{n}^{-1}([-m,m])\]
is closed (since $f_{n}$ is continuous), so
\[E_{m}=\bigcap_{n=1}^{\infty}E_{n,m}\]
is.

If we fix $x\in[0,1]$ for the moment, we know that 
$f_{n}(x)\rightarrow 0$
as $n\rightarrow\infty$. In particular,
we can find an $N(x)$ such that $|f_{n}(x)|\leq 1$
for all $n\geq N(x)$. Thus
\[|f_{n}(x)|\leq \max\{1,\max_{1\leq j\leq N(x)}|f_{n}(x)|\}\]
and so $x\in E_{m(x)}$ for some integer $m(x)$.

The previous paragraph shows that
\[[0,1]=\bigcup_{m=1}^{\infty}E_{m},\]
but Baire's category theorem tells us that $[0,1]$
cannot be the countable union of closed sets with 
empty interior. Thus there must exist an $M$ such that
$E_{M}$ has non-empty interior, so $E_{M}\supseteq(a,b)$
for some non-empty interval $(a,b)$.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;100/37}]
\begin{align*}
\frac{100}{37}&=2+\frac{26}{37},\\
\frac{37}{26}&=1+\frac{11}{26},\\
\frac{26}{11}&=2+\frac{4}{11},\\
\frac{11}{4}&=2+\frac{3}{4},\\
\frac{4}{3}&=1+\frac{1}{3}.
\end{align*}
Thus
\[\frac{100}{37}=2+\cfrac{1}
{1+\cfrac{1}
{2+\cfrac{1}
{2+\cfrac{1}
{1+\cfrac{1}
{3}}}}}.\]
\end{proof}
\begin{proof}[Lemma~\ref{L;continued Euclid}]
(i) This is immediate.

(ii) We saw in 1A that the Euclidean algorithm terminates. (Or
we could repeat the 1A proof by observing that the elements of the
pairs are strictly decreasing.)
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;square root}]
We know that $1<\sqrt{2}<2$, so
\[\sqrt{2}=1+\alpha\]
with $0<\alpha=\sqrt{2}-1<1$.

Now
\[\frac{1}{\alpha}=\frac{1}{\sqrt{2}-1}=\sqrt{2}+1=2+\alpha\]
so $N(\alpha)=2$ and $T(\alpha)=2+\alpha$.
Thus $\sqrt{2}$ has the \emph{non-terminating} continued fraction
\[1+\cfrac{1}
{2+\cfrac{1}
{2+\cfrac{1}
{2+\cfrac{1}
{2+\dots}}}}\]
and cannot be  rational.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;decimal}]
We have
\[Dx=10x-[10x]=10x-Nx\]
so
\[x=10^{-1}(Dx+Nx).\]
Since $Dx\in [0,1)$, we have
\begin{align*}
x&=10^{-1}(Dx+Nx)=10^{-1}\big(10^{-1}\big(D(Dx)+N(Dx)\big)+Nx\big)\\
&=10^{-1}Nx+10^{-2}NDx+10^{-2}D^{2}x\\
&=10^{-1}Nx+10^{-2}NDx+10^{-3}ND^{2}x+10^{-3}D^{3}x\\
&=\ldots.
\end{align*}

We have
\begin{align*}
\Pr(ND^{r}X&=k_{r}\ \text{for}\ 1\leq r\leq n)\\
&=\Pr\left(\sum_{r=1}^{n}k_{r}10^{-r}\leq X
<10^{-n}+\sum_{r=1}^{n}k_{r}10^{-r}\right)=10^{-n},
\end{align*}
so
\[\Pr(ND^{k}X=j)=1/10\]
for $0\leq j\leq 9$
and
\[\Pr(ND^{r}X=k_{r}\ \text{for}\ 1\leq r\leq n\}=10^{-n}
=\prod_{r=1}^{n}\Pr(ND^{r}X=k_{r}),\]
showing that $NX$, $NDX$, $ND^{2}X$, $\ldots$
are independent
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;Gauss}]
  Observe that
\begin{align*}
\Pr(TX\leq a)
&=\Pr(n\leq X^{-1}\leq n+a\ \text{for some integer $n\geq 1$})\\
&=\Pr\big((n+a)^{-1}\leq X\leq n^{-1}
\ \text{for some integer $n\geq 1$}\big)\\
&=\sum_{n=1}^{\infty}\Pr\big((n+a)^{-1}\leq X\leq n^{-1}\big)\\
&=\sum_{n=1}^{\infty}\frac{1}{\log 2}
\int_{(n+a)^{-1}}^{n^{-1}}\frac{1}{1+x}\,dx\\
&=\sum_{n=1}^{\infty}\frac{1}{\log 2}
\Big[\log(1+x)\Big]_{(n+a)^{-1}}^{n^{-1}}\\
&=\frac{1}{\log 2}\sum_{n=1}^{\infty}
\big(\log (1+n^{-1})-\log (1+(n+a)^{-1})\big)\\
&=\frac{1}{\log 2}\sum_{n=1}^{\infty}
\big(\big(\log(n+1)-\log n\big))-\big(\log(1+n+a)-\log(n+a)\big)\big)\\
&=\frac{1}{\log 2}\lim_{N\rightarrow\infty}
\big(\log(N+1)-\log(1+N+a)+\log (1+a)\big)\\
&=\frac{1}{\log 2}\left(\log(1+a)+
\lim_{N\rightarrow\infty}\log\frac{N+1}{1+N+a}\right)\\
&=\frac{\log(1+a)}{\log 2}=\Pr(X\leq a).
\end{align*}
\end{proof}
\begin{proof}[Proof of Corollary~\ref{C;continued random}]
By Lemma~\ref{L;Gauss},
\begin{align*}
\Pr(NT^{m}X=j)&=\Pr(NX=j)\\
&=\frac{1}{\log 2}
\int_{j^{-1}}^{(j+1)^{-1}}\frac{1}{1+x}\,dx\\
&=\frac{1}{\log 2}
\Big[\log(1+x)\Big]_{(j+1)^{-1}}^{j^{-1}}\\
&=\frac{1}{\log 2}\big(\log\frac{j+1}{j}-\log\frac{j+2}{j+1}\big)
=\frac{1}{\log 2}\log\frac{(j+1)^{2}}{j(j+2)}.
\end{align*}
\end{proof}  
\begin{proof}[Proof of Lemma~\ref{L;continued matrices start}]
  (i) We use backwards induction on $k$.
Since
\[\frac{r_{n}}{s_{n}}=a_{n}\]
the result is true for $k=n$. 

Suppose the result is true
for $m+1$ with $0\leq m\leq n-1$.
Then, by definition,
\[\begin{pmatrix}r_{m}\\s_{m}\end{pmatrix}
=\begin{pmatrix}a_{m}&1\\1&0\end{pmatrix}
\begin{pmatrix}r_{m+1}\\s_{m+1}\end{pmatrix}
=\begin{pmatrix}a_{m}r_{m+1}+s_{m+1}\\r_{m+1}\end{pmatrix},
\]
and, by the inductive hypothesis,
\begin{align*}
a_{m}+&
\cfrac{1}
{a_{m+1}+\cfrac{1}
{a_{m+2}+\cfrac{1}
{a_{m+3}+\cfrac{1}
{a_{m+4}+\cfrac{1}
{\ddots\cfrac{\ }
{a_{n-1}+\cfrac{1}
{a_{n}}}}}}}}\\
&=a_{m}+\frac{1}{r_{m+1}/s_{m+1}}\\
&=a_{m}+\frac{s_{m+1}}{r_{m+1}}\\
&=\frac{a_{m}r_{m+1}+s_{m+1}}{r_{m+1}}=\frac{r_{m}}{s_{m}}.
\end{align*}

The required result now follows.

(ii) Apply (i) repeatedly.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;continued matrices}]
(i) This is just a restatement of 
Lemma~\ref{L;continued matrices start}~(ii).

(ii) We have
\[\begin{pmatrix}p_{n-1}\\q_{n-1}\end{pmatrix}=
\begin{pmatrix}a_{0}&1\\1&0\end{pmatrix}
\begin{pmatrix}a_{1}&1\\1&0\end{pmatrix}
\dots\
\begin{pmatrix}a_{n-2}&1\\1&0\end{pmatrix}
\begin{pmatrix}a_{n-1}\\1\end{pmatrix}
\]
and
\[\begin{pmatrix}a_{n-1}\\1\end{pmatrix}
=\begin{pmatrix}a_{n-1}&1\\1&0\end{pmatrix}
\begin{pmatrix}1\\0\end{pmatrix}.\]
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;continued convergence}]
(i) Using Lemma~\ref{L;continued matrices}~(ii),
we have
\begin{align*}
 p_{k}q_{k-1}-q_{k}p_{k-1}
&=\det\begin{pmatrix}p_{k}&p_{k-1}\\q_{k}&q_{k-1}\end{pmatrix}\\
&=\det\begin{pmatrix}a_{0}&1\\1&0\end{pmatrix}
\begin{pmatrix}a_{1}&1\\1&0\end{pmatrix}
\cdots
\begin{pmatrix}a_{k}&1\\1&0\end{pmatrix}\\
&=\det\begin{pmatrix}a_{0}&1\\1&0\end{pmatrix}
\det\begin{pmatrix}a_{1}&1\\1&0\end{pmatrix}
\cdots
\det\begin{pmatrix}a_{k}&1\\1&0\end{pmatrix}\\
&=(-1)^{k+1}.
\end{align*}

(ii) Either use the matricial formula 
\[\begin{pmatrix}p_{k}&p_{k-1}\\q_{k}&q_{k-1}\end{pmatrix}
=\begin{pmatrix}p_{k-1}&p_{k-2}\\q_{k-1}&q_{k-2}\end{pmatrix}
\begin{pmatrix}a_{k}&1\\1&0\end{pmatrix}
\]
or direct computation.

(iii) Follows from the formula of~(i).

(iv) By~(ii) (or direct observation),
the $q_{k}$ form a strictly increasing sequence
of strictly positive integers. Thus the
$q_{k-1}q_{k}$  form a strictly increasing sequence
of strictly positive integers.

The formula of~(i) gives
\[\frac{p_{k}}{q_{k}}-\frac{p_{k-1}}{q_{k-1}}=(-1)^{k+1}
\frac{1}{q_{k}q_{k-1}},\]
so the remark of the previous paragraph shows
that 
\[\frac{p_{k}}{q_{k}}-\frac{p_{k-1}}{q_{k-1}}\]
is an alternating sequence with decreasing magnitude.
Thus
\[\frac{p_{2k}}{q_{2k}}<\frac{p_{2k-2}}{q_{2k-2}},
\ \frac{p_{2k-1}}{q_{2k-1}}<\frac{p_{2k+1}}{q_{2k+1}}.\]

We also have
\[\left|\frac{p_{k}}{q_{k}}-\frac{p_{k-1}}{q_{k-1}}\right|
  =\frac{1}{q_{k}q_{k-1}}\rightarrow 0.\]

(v) A decreasing sequence bounded below tends to a limit,
so
\[\frac{p_{2k+1}}{q_{2k+1}}\rightarrow\alpha\]
as $k\rightarrow\infty$ for some $\alpha$.
Since
\[\left|\frac{p_{k}}{q_{k}}-\frac{p_{k-1}}{q_{k-1}}\right|
\rightarrow 0\]
this tells us that
\[\frac{p_{2k}}{q_{2k}}\rightarrow\alpha\]
as $k\rightarrow\infty$. Thus
 \[\frac{p_{n}}{q_{n}}\rightarrow \alpha\]
and
\[\frac{p_{2k+1}}{q_{2k+1}}>\alpha>\frac{p_{2k}}{q_{2k}}.\]
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;above below}]
Observe that if $a>0$
\[s>t>0\Rightarrow\frac{1}{a+t}>\frac{1}{a+s}.\]
Thus (using a formal induction if more details are required)
\[\frac{p_{2k}}{q_{2k}}<x<
\frac{p_{2k-1}}{q_{2k-1}}.\]
We know from Theorem~\ref{T;continued convergence}~(v)
that 
\[\frac{p_{n}}{q_{n}}\rightarrow \alpha,\]
so $\alpha=x$.
\end{proof}
\begin{proof}[Proof of Theorem~\ref {T;good continue}]
Observe that if $q$ and $u$ are positive
integers with $q\leq q_{n}$, then
\[\left|\frac{u}{q}-\frac{p_{n+1}}{q_{n+1}}\right|
\geq\frac{1}{qq_{n+1}},\]
with equality only if $q=q_{n}$ and, in this case, only
if $u=p_{n}$. Thus
$p_{n}/q_{n}$ is the closest fraction of the form $u/q$
(with $q\leq q_{n}$) to $p_{n+1}/q_{n+1}$. But
$\alpha$ lies between $p_{n}/q_{n}$ and $p_{n+1}/q_{n+1}$,
so  $p_{n}/q_{n}$ is also the closest fraction of the form $u/q$
(with $q\leq q_{n}$) to $\alpha$.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;good Liouville}]
We may assume that $0<x<1$ without loss of generality.
Using the notation of this section we
observe that $x$ lies between $p_{n}/q_{n}$ and $p_{n+1}/q_{n+1}$
so
\[\left|\frac{p_{n}}{q_{n}}-x\right|
<\left|\frac{p_{n}}{q_{n}}-\frac{p_{n+1}}{q_{n+1}}\right|=
\frac{1}{q_{n}q_{n+1}}<\frac{1}{q_{n}^{2}}.\]
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;bad quadratic approximation}]
Theorem~\ref{T;Liouville} with $n=2$.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;Lewis}]
(i) Observe that
\[\sigma=\frac{1}{1+\sigma}\]
so that
\[\sigma^{2}+\sigma-1=0\]
and
\[\sigma=\frac{-1\pm\sqrt{5}}{2}.\]
Since $\sigma>0$, we must have
\[\sigma=\frac{-1+\sqrt{5}}{2}.\] 

(ii) By Theorem~\ref{T;continued convergence}~(iii), 
$q_{k}=a_{k}q_{k-1}+q_{k-2}$ and
$p_{k}=a_{k}p_{k-1}+p_{k-2}$ with $a_{k}=1$.
Thus
\[q_{k}=q_{k-1}+q_{k-2}\ \text{and}
\ p_{k}=p_{k-1}+p_{k-2}.\]
Now $q_{0}=1=F_{1}$, $q_{1}=1=F_{2}$, $p_{0}=0=F_{0}$, 
$p_{1}=1=F_{1}$, so by an inductive argument
(or general knowledge
of recurrence relations),
\[q_{n}=F_{n+1}\ \text{and}\ p_{n}=F_{n}.\]

(iii) By Theorem~\ref{T;continued convergence}~(i),
\[F_{n+1}F_{n-1}-F_{n}^{2}=
-(p_{n-1}q_{n}-q_{n-1}p_{n})=(-1)^{n+1}.\]
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;prepare entry}]
By Theorem~\ref{T;good continue} $F_{n}/F_{n+1}$
is closer to $\sigma$ than any other fraction with 
denominator no larger than $F_{n+1}$.
Thus
\begin{align*}
\left|\frac{p}{q}-\sigma\right|&\geq 
\max\left\{\left|\frac{F_{n}}{F_{n+1}}-\sigma\right|,
\left|\frac{F_{n+1}}{F_{n+2}}-\sigma\right|\right\}\
\geq\frac{1}{2}
\left(\left|\frac{F_{n}}{F_{n+1}}-\sigma\right|+
\left|\frac{F_{n+1}}{F_{n+2}}-\sigma\right|\right)\\
&=\frac{1}{2}
\left|\frac{F_{n}}{F_{n+1}}-\frac{F_{n+1}}{F_{n+2}}\right|\
=\frac{1}{2F_{n+1}F_{n+2}}
\end{align*}
whenever $q\leq F_{n}$ and so whenever $F_{n-1}\leq q\leq F_{n}$.

Now $F_{r}\leq 2F_{r-1}$ so
\[\left|\frac{p}{q}-\sigma\right|\geq \frac{1}{2F_{n+1}F_{n+2}}
\geq \frac{1}{64 F_{n-1}^{2}}\geq \frac{1}{64 q^{2}}\]
whenever $F_{n-1}\leq q\leq F_{n}$ for all $n\geq 2$
and the result follows.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;Carroll}]
Observe that $F_{5}=5$, $F_{6}=8$, $F_{7}=13$
so the difference in areas is $1$ so we only need to hide
one unit of area.

Identify the Fibonacci numbers in the diagram and
generalise.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;generalise continued matrices}]
 (i) The proof follows the lines of that of
Lemma~\ref{L;continued matrices start}. 

Observe that, if $s,\,r\neq 0$,
\[\begin{pmatrix}r'\\s'\end{pmatrix}
=\begin{pmatrix}a&b\\1&0\end{pmatrix}
\begin{pmatrix}r\\s\end{pmatrix}
=\begin{pmatrix}ar+bs\\r\end{pmatrix},
\]
and
\[\frac{ar+bs}{r}=a+\frac{b}{r/s}.\]

Thus, by induction, if
\[\begin{pmatrix}p_{n}\\q_{n}\end{pmatrix}=
\begin{pmatrix}a_{0}&b_{0}\\1&0\end{pmatrix}
\begin{pmatrix}a_{1}&b_{1}\\1&0\end{pmatrix}
\dots\
\begin{pmatrix}a_{n-1}&b_{n-1}\\1&0\end{pmatrix}
\begin{pmatrix}a_{n}\\1\end{pmatrix},
\]
then
\[\frac{p_{n}}{q_{n}}
=a_{0}+\cfrac{b_{0}}
{a_{1}+\cfrac{b_{1}}
{a_{2}+\cfrac{b_{2}}
{a_{3}+\cfrac{b_{3}}
{a_{4}+\cfrac{b_{4}}
{\ddots\cfrac{\ }
{a_{n-1}+\cfrac{b_{n-1}}
{a_{n}}}}}}}}.\]

Observe that
\begin{align*}
\begin{pmatrix}a_{0}&b_{0}\\1&0\end{pmatrix}&
\begin{pmatrix}a_{1}&b_{1}\\1&0\end{pmatrix}
\dots\
\begin{pmatrix}a_{n-1}&b_{n-1}\\1&0\end{pmatrix}
\begin{pmatrix}1\\0\end{pmatrix}\\
&=\begin{pmatrix}a_{0}&b_{0}\\1&0\end{pmatrix}\dots
\begin{pmatrix}a_{n-2}&b_{n-2}\\1&0\end{pmatrix}
\begin{pmatrix}a_{n-1}\\1\end{pmatrix}
=\begin{pmatrix}p_{n-1}\\q_{n-1}\end{pmatrix}
\end{align*}
and thus
\[\begin{pmatrix}p_{n}&b_{n}p_{n-1}\\q_{n}&b_{n}q_{n-1}\end{pmatrix}
=\begin{pmatrix}a_{0}&b_{0}\\1&0\end{pmatrix}
\begin{pmatrix}a_{1}&b_{1}\\1&0\end{pmatrix}
\dots
\begin{pmatrix}a_{n}&b_{n}\\1&0\end{pmatrix}.
\]

We deduce that
\[\begin{pmatrix}p_{n}&b_{n}p_{n-1}\\q_{n}&b_{n}q_{n-1}\end{pmatrix}
=\begin{pmatrix}p_{n-1}&b_{n-1}p_{n-2}\\q_{n-1}&b_{n-1}q_{n-2}\end{pmatrix}
\begin{pmatrix}a_{n}&b_{n}\\1&0\end{pmatrix}.\]
Looking at the first column gives
\begin{align*}
p_{n}&=a_{n}p_{n-1}+b_{n-1}p_{n-2},\\
q_{n}&=a_{n}q_{n-1}+b_{n-1}q_{n-2},
\end{align*}
as required.
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;more Lambert}]
We have
\[S_{0}(x)=\int_{0}^{x}\cos t\,dt=\sin x,\]
so $p_{0}(x)=0$, $q_{0}(x)=1$. Integration by parts gives
\begin{align*}
S_{1}(x)&=\frac{1}{2}\int_{0}^{x}(x^{2}-t^{2})\cos t\,dt\\
&=\left[\frac{1}{2}(x^{2}-t^{2})\sin t\right]_{0}^{x}
+\int_{0}^{x}t\sin t\,dt
=\int_{0}^{x}t\sin t\,dt\\
&=\left[-t\cos t\right]_{0}^{x}+\int_{0}^{x}t\cos t\,dt
=-x\cos x+\sin x
\end{align*}
so $p_{1}(x)=x$, $q_{1}(x)=1$. 

If $n\geq 2$, a similar repeated integration by parts
gives
\begin{align*}
S_{n}(x)&=\frac{1}{2^{n}n!}\int_{0}^{x}(x^{2}-t^{2})^{n}\cos t\,dt\\
&=\left[\frac{1}{2^{n}n!}(x^{2}-t^{2})^{n}\sin t\right]_{0}^{x}
+\frac{1}{2^{n-1}(n-1)!}\int_{0}^{x}t(x^{2}-t^{2})^{n-1}\sin t\,dt\\
&=\frac{1}{2^{n-1}(n-1)!}\int_{0}^{x}t(x^{2}-t^{2})^{n-1}\sin t\,dt\\
&=\frac{1}{2^{n-1}(n-1)!}\left[-t(x^{2}-t^{2})^{n-1}\cos t\right]_{0}^{x}\\
&\qquad+\frac{1}{2^{n-1}(n-1)!}
\int_{0}^{x}\big((x^{2}-t^{2})^{n-1}-2(n-1)t^{2}(x^{2}-t^{2})^{n-2}\big)
\cos t \,dt\\
&=S_{n-1}(x)-\frac{1}{2^{n-2}(n-2)!}
\int_{0}^{x}\big(t^{2}(x^{2}-t^{2})^{n-2}\big)\cos t\,dt\\
&=S_{n-1}(x)+\frac{1}{2^{n-2}(n-2)!}\left(
\int_{0}^{x}\big((x^{2}-t^{2})t^{2}(x^{2}-t^{2})^{n-2}\big)\cos t\,dt\right.\\
&\left.\qquad-x^{2}\int_{0}^{x}(x^{2}-t^{2})^{n-2}\cos t\,dt\right)\\
&=(2n-1)S_{n-1}(x)-x^{2}S_{n-2}(x).
\end{align*}

Thus
\begin{align*}
p_{n}(x)&=(2n-1)p_{n-1}(x)-x^{2}p_{n-2}(x),\\
q_{n}(x)&=(2n-1)q_{n-1}(x)-x^{2}q_{n-2}(x)
\end{align*}
and we are done.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;Lambert}]
Since
\[S_{n}(x)=q_{n}(x)\sin x-p_{n}(x)\cos x,\]
rearrangement gives
\[\tan x=\frac{p_{n}(x)}{q_{n}(x)}
+\frac{S_{n}(x)}{q_{n}(x)\cos x}\]
so we need to show that
\[\frac{S_{n}(x)}{q_{n}(x)\cos x}\rightarrow 0.\]

It is easy to see that
\begin{align*}
|S_{n}(x)|&\leq
\left|\frac{1}{2^{n}n!}\int_{0}^{x}(x^{2}-t^{2})^{n}\cos t\,dt\right|\\
&\leq \frac{1}{2^{n}n!}|x||x|^{2n}\rightarrow 0
\end{align*}
as $n\rightarrow\infty$ for all $x$.

We shall show that if $|x|\leq 1$ then $q_{n}(x)\rightarrow\infty$.
(Actually it can be shown that $|q_{n}(x)|\rightarrow\infty$
for all $x$.) Observe that
\[q_{n}(x)=(2n-1)q_{n-1}(x)-x^{2}q_{n-2}(x)\]
so, if $|x|\leq 1$,
\[q_{n}(x)\geq (2n-1)q_{n-1}(x)-q_{n-2}(x)\geq 3q_{n-1}(x)-q_{n-2}(x)\]
for $n\geq 2$. Since $q_{0}(x)=q_{1}(x)=1$ we have
$q_{2}(x)\geq 2$ and a simple induction gives
$q_{n}(x)\geq 2^{n-1}$ for $n\geq 1$ and $|x|\leq 1$.

Notice the rapidity of convergence of the continued fraction
in this case.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;track argument}]
We leave uniqueness to follow
from Exercise~\ref{E;start argument}.
Let $E$ be the set of $u\in[0,1]$
for which there exists a
continuous function $\theta:[0,u]\rightarrow{\mathbb R}$
with $\theta(0)=\theta_{0}$ 
such that $g(t)=e^{i\theta(t)}$ for all $t\in[0,u]$.
Since $0\in E$ (just take $\theta(0)=\theta_{0}$)
and $E$ is bounded, $E$ must have an upper bound
$w$. 

Suppose that $w\in(0,1)$. Since $g$ is continuous,
we can find a $\delta>0$ such that 
$(w-2\delta,w+2\delta)\subseteq [0,1]$ and
$|g(t)-g(w)|<1/2$ for $t\in(w-2\delta,w+2\delta)$
We know that there is a unique continuous function
\[\phi:\{z\,:\,|z-1|<1/2,\ |z|=1\}\rightarrow [-\pi/2,\pi/2]\]
such that
\[z=e^{i\phi(z)}
\ \text{for all}\ |z-1|<1/2,\ |z|=1.\]
Thus, if we choose $\theta_{1}$ such that $e^{i\theta_{1}}=g(w)$
and define 
$\tilde{\theta}:(w-2\delta,w+2\delta)\rightarrow [-\pi/2,\pi/2]$ by
\[\tilde{\theta}(t)=\theta_{1}+\phi\big(g(t)/g(w)\big)\]
we will have $\tilde{\theta}$ continuous and
\[g(t)=e^{i\tilde{\theta}(t)}\]
for $t\in (w-2\delta,w+2\delta)$.

By the definition of an upper bound, we can find 
$u\in (w-\delta,w]$ and a continuous function
$\psi:[0,u]\rightarrow{\mathbb R}$
with $\psi(0)=\theta_{0}$ 
such that $g(t)=e^{i\psi(t)}$ for all $t\in[0,u]$.
Since
\[e^{i\tilde{\theta}(u)}=g(u)=e^{i\psi(u)}\]
we must have $\tilde{\theta}(u)=\psi(u)+2N\pi$
for some integer $N$.
Taking
\[\theta(t)=
\begin{cases}
\psi(t)&\text{for $t\in[0,u]$}\\
\tilde{\theta}(t)-2N\pi&\text{for $t\in[u,u+\delta]$}
\end{cases}\]
we see that $\theta:[0,u+\delta]\rightarrow{\mathbb R}$
is a continuous function with $\theta(0)=\theta_{0}$ 
such that $g(t)=e^{i\theta(t)}$ for all $t\in[0,u+\delta]$.
Thus $u+\delta\in E$ and $u+\delta>w$, contradicting our assumption
that $u$ is an upper bound.

A similar argument shows that $0$ is not an upper bound.
Thus $\sup E=1$ and much the same argument as above 
shows that $1\in E$,
so we are done.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;start argument}]
Observe that
$f:[0,1]\rightarrow{\mathbb R}$ defined by
\[f(t)= \frac{\psi(t)-\phi(t)}{2\pi}\]
is an integer valued continuous function on $[0,1]$
and so must be constant. (Or quote the intermediate value 
theorem directly.)
\end{proof}
\begin{proof}[Proof of Corollary~\ref{C;unwind}]
 Set
$g(t)=\gamma(t)/|\gamma(t)|$ and use Theorem~\ref{T;track argument}.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;closed integer}]
(i) Since $\gamma(0)\neq 0$ and
\[|\gamma(0)|e^{i\theta(0)}=\gamma(0)=\gamma(1)
=|\gamma(1)|e^{i\theta(1)}=|\gamma(0)|e^{i\theta(1)},\]
we have $e^{i(\theta(1)-\theta(0))}=1$, so $\theta(1)-\theta(0)$
is an integer multiple of $2\pi$.

(ii) If we take $\gamma(t)=\exp(irt)$, we get
$w(\gamma,0)=r$ $[r\in{\mathbb Z}]$
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;dogmatic}]
By Corollary~\ref{C;unwind}, we can write
\[\gamma_{j}(t)=|\gamma_{j}(t)|\exp\big(i\theta_{j}(t)\big)\]
with $\theta_{j}:[0,1]\rightarrow{\mathbb R}$ continuous.
We now have
\begin{align*}
\gamma_{1}(t)\gamma_{2}(t)&
=|\gamma_{1}(t)|\exp\big(i\theta_{1}(t)\big)
|\gamma_{2}(t)|\exp\big(i\theta_{2}(t)\big)\\
&=|\gamma_{1}(t)\gamma_{2}(t)|
\exp\big(i(\theta_{1}(t)+\theta_{2}(t))\big),
\end{align*}
so that
\begin{align*}
w(\gamma_{1}\gamma_{2},0)&=\frac{1}{2\pi}
\big(
\big(\theta_{1}(1)+\theta_{2}(1)\big)-
\big(\theta_{1}(0)+\theta_{2}(0)\big)\\
&=\frac{1}{2\pi}
\big(\theta_{1}(1)-\theta_{1}(0)\big)+
\frac{1}{2\pi}
\big(\theta_{2}(1)-\theta_{2}(0)\big)
=w(\gamma_{1},0)+w(\gamma_{2},0).
\end{align*}
\end{proof}
\begin{proof}[Proof of Lemma~\ref{L;dog walk}]
This argument may be familiar from 1B
complex variable.

Write $\gamma(t)=\big(1+\gamma_{2}(t)/\gamma_{1}(t)\big)$. 
By Lemma~\ref{L;dogmatic},
\[w(\gamma_{1}+\gamma_{2},0)=w(\gamma_{1}\gamma,0)
=w(\gamma_{1},0)+w(\gamma,0),\]
so it suffices to prove that $w(\gamma,0)=0$.
We shall do this by noting that
$|\gamma_{2}(t)/\gamma_{1}(t)|<1$ and so
\[\Re\gamma(t)>0\]
for all $t\in[0,1]$.

By Corollary~\ref{C;unwind}, we can write
\[\gamma(t)=|\gamma(t)|\exp\big(i\theta(t)\big)\]
with $\theta:[0,1]\rightarrow{\mathbb R}$ continuous
and $\theta(0)\in(-\pi/2,\pi/2)$. If $|\theta(t)|\geq\pi/2$
for any $t\in[0,1]$, the intermediate value theorem tells
us that there is an $s\in[0,t]$ such that
$|\theta(s)|=\pi/2$ and so $\Re\gamma(s)=0$, which
is impossible. Thus  $|\theta(t)|<\pi/2$
for all $t\in [0,1]$.

In particular  $|\theta(0)|,|\theta(1)|<\pi/2$,
so $|\theta(1)-\theta(0)|<\pi$. It follows that
$w(\gamma,0)$ is an integer with $|w(\gamma,0)|<1/2$
and so  $w(\gamma,0)=0$.
\end{proof}
\begin{proof}[Solution of Exercise~\ref{E;homotopy equivalence}]
Setting
\[\Gamma(s,t)=\gamma(t),\]
we see that $\gamma\simeq\gamma$.

If $\gamma_{0}\simeq\gamma_{1}$, then we can find
a continuous function
$\Gamma:[0,1]^{2}\rightarrow{\mathbb C}\setminus\{0\}$
such that
\begin{alignat*}{2}
\Gamma(s,0)&=\Gamma(s,1)&&\qquad\text{for all $s\in[0,1]$},\\
\Gamma(0,t)&=\gamma_{0}(t)&&\qquad\text{for all $t\in[0,1]$},\\
\Gamma(1,t)&=\gamma_{1}(t)&&\qquad\text{for all $t\in[0,1]$}.
\end{alignat*}
If we set $\tilde{\Gamma}(s,t)=\Gamma(1-s,t)$,
then 
$\tilde{\Gamma}:[0,1]^{2}\rightarrow{\mathbb C}\setminus\{0\}$
is a continuous function
such that
\begin{alignat*}{2}
\tilde{\Gamma}(s,0)&=\tilde{\Gamma}(s,1)
&&\qquad\text{for all $s\in[0,1]$},\\
\tilde{\Gamma}(0,t)&=\gamma_{1}(t)
&&\qquad\text{for all $t\in[0,1]$},\\
\tilde{\Gamma}(1,t)&=\gamma_{0}(t)&&\qquad\text{for all $t\in[0,1]$},
\end{alignat*}
and so  $\gamma_{1}\simeq\gamma_{0}$.

If $\gamma_{0}\simeq\gamma_{1}$ and
$\gamma_{1}\simeq\gamma_{2}$,
then we can find
a continuous functions
$\Gamma_{j}:[0,1]^{2}\rightarrow{\mathbb C}\setminus\{0\}$
such that
\begin{alignat*}{2}
\Gamma_{j}(s,0)&=\Gamma_{j}(s,1)&&\qquad\text{for all $s\in[0,1]$},\\
\Gamma_{j}(0,t)&=\gamma_{0+j}(t)&&\qquad\text{for all $t\in[0,1]$},\\
\Gamma_{j}(1,t)&=\gamma_{1+j}(t)&&\qquad\text{for all $t\in[0,1]$}
\end{alignat*}
for $j=0,\,1$.

If we set 
\[\Gamma(s,t)=\begin{cases}
\Gamma_{0}(2s,t)&\text{for all $s\in[0,1/2]$, $t\in[0,1]$}\\
\Gamma_{1}(2s-1,t)&\text{for all $s\in(1/2,1]$, $t\in[0,1]$}
\end{cases}\]
then 
$\Gamma:[0,1]^{2}\rightarrow{\mathbb C}\setminus\{0\}$
is a continuous function
such that
\begin{alignat*}{2}
\tilde{\Gamma}(s,0)&=\tilde{\Gamma}(s,1)
&&\qquad\text{for all $s\in[0,1]$},\\
\tilde{\Gamma}(0,t)&=\gamma_{0}(t)
&&\qquad\text{for all $t\in[0,1]$},\\
\tilde{\Gamma}(1,t)&=\gamma_{2}(t)&&\qquad\text{for all $t\in[0,1]$},
\end{alignat*}
and so  $\gamma_{0}\simeq\gamma_{2}$.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{T;canal}]
Let $\Gamma$ be as in Definition~\ref{D;homotopy}.
The map $(s,t)\mapsto |\Gamma(s,t)|$ is continuous
so, by compactness, $|\Gamma(s,t)|$ attains a minimum
$m$ on the compact set $[0,1]^{2}$. Since $\Gamma$ is never zero,
we must have $m>0$.

By compactness (see Theorem~\ref{T;uniform continuity}
if necessary), $\Gamma$ is uniformly continuous and so
we can find a strictly positive integer $N$ such that
\[|s-s'|,|t-t'|<2/N\Rightarrow |\Gamma(s,t)-\Gamma(s',t')|<m/2.\]
If $0\leq r\leq N$ let us define
\[\beta_{r}(t)=\Gamma(r/N,t)\]
for $t\in[0,1]$. We observe that
\begin{align*}
|\beta_{r}(t)|&=|\Gamma(r/N,t)|\geq m>m/2\\
&>\big|\Gamma\big(r/N,t\big)-\Gamma\big((r+1)/N,t\big)\big|
=|\beta_{r}(t)-\beta_{r+1}(t)|
\end{align*}
for all $t\in[0,1]$, so by the dog walking lemma
(Lemma~\ref{L;dog walk}),
\[w(\beta_{r},0)=w(\beta_{r+1},0)\]
for all $0\leq r\leq N-1$. It follows that
\[w(\gamma_{0},0)= w(\beta_{0},0)=w(\beta_{N},0)=
w(\gamma_{1},0).\]
\end{proof}
\begin{proof}[Proof of Corollary~\ref{C;dizy dog}]
Suppose, if possible, that
$f(z)\neq 0$ for $z\in D$.
The nowhere-zero
function $G:[0,1]^{2}\mapsto{\mathbb C}$
given by
\[G(s,t)=f(se^{2\pi it})\]
is continuous with $G(s,0)=G(s,1)$ for all 
$s\in[0,1]$, 
$G(1,t)=\gamma(t)$ 
and $G(0,t)=\gamma_{0}(t)$ 
where $\gamma_{0}(t)=f(0)$
for all $t\in[0,1]$. Thus $\gamma$ 
and $\gamma_{0}$ are homotopic using 
closed curves  not passing through $0$.
By Theorem~\ref{T;canal},
$w(\gamma,0)=w(\gamma_{0},0)=0$
contradicting our hypothesis.
\end{proof}
\begin{proof}[Proof of Corollary~\ref{C;money}]
It is sufficient to consider polynomials $P$
of the form
\[P(z)=z^{n}+Q(z)\]
with $Q(z)=\sum_{j=0}^{n-1}a_{j}z^{j}$. 
If we set $R=1+\sum_{j=0}^{n-1}|a_{j}|$
and consider $p(z)=R^{-n}p(Rz)$
we see that $P$ has a root if $p$ has root
and that
\[p(z)=z^{n}+q(z)\]
with $|q(z)|<1$ when $|z|=1$.

By the dog walking lemma, the map
$t\mapsto p(e^{2\pi it})$ for $t\in[0,1]$ 
has the same winding number
as
$t\mapsto (e^{2\pi it})^{n}=e^{2\pi int}$, 
that is to say, $n$. By Corollary~\ref{C;dizy dog},
there
must exist a $z\in D$ with $p(z)=0$,
so we are done.
\end{proof}
\begin{proof}[Proof of Corollary~\ref{C;second Brouwer}]
Suppose such a function existed.
The continuous map $G:[0,1]^{2}\rightarrow\partial D$
given by
\[G(s,t)=f(se^{2\pi it})\]
gives a homotopy between $\gamma_{0}$
defined by $\gamma_{0}(t)=f(0)$ and 
$\gamma_{1}$ defined by $\gamma_{1}(t)=f(t)=e^{2\pi t}$
using closed curves not passing through $0$.
By Theorem~\ref{T;canal}, this gives
\[1=w(\gamma_{1},0)=w(\gamma_{0},0)=0,\]
which is absurd.

The required result follows by reductio ad absurdum.
\end{proof}
\newpage
\begin{verse}
`You are old, Father William' the young man said,\\
And your hair has become very white;\\
And yet you incessantly stand on your head\\ 
Do you think, at your age, it is right?'

`In my youth' Father William replied to his son,\\
`I feared it might injure the brain;\\
But, now that I'm perfectly sure I have none,\\
Why, I do it again and again.'

`You are old' said the youth `as I mentioned before,\\
And have grown most uncommonly fat;\\
Yet you turned a back-somersault in at the door –\\
Pray, what is the reason of that?'

`In my youth' said the sage, as he shook his grey locks,\\
`I kept all my limbs very supple\\
By the use of this ointment – one shilling the box –\\
Allow me to sell you a couple?'

`You are old' said the youth `and your jaws are too weak\\
For anything tougher than suet;\\
Yet you finished the goose, with the bones and the beak –\\
Pray how did you manage to do it?'

`In my youth' said his father `I took to the law,\\
And argued each case with my wife;\\
And the muscular strength, which it gave to my jaw,\\
Has lasted the rest of my life.'

`You are old' said the youth `one would hardly suppose\\
That your eye was as steady as ever;\\
Yet you balanced an eel on the end of your nose –\\
What made you so awfully clever?'

`I have answered three questions, and that is enough'\\
Said his father; `don't give yourself airs!\\
Do you think I can listen all day to such stuff?\\
Be off, or I'll kick you down stairs!'

\begin{flushright}
Lewis Carroll
\end{flushright}
\end{verse}
\end{document}
