\documentclass[11pt,letterpaper]{article}
\usepackage{amsmath,amsfonts}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.7in}
\setlength{\textheight}{9.1in}
\setlength{\parskip}{0.4em}
\parindent0mm
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\C{\mathbb{C}}
\begin{document}
\begin{center}
{\bf \Large Math 112 Homework 9 Solutions}\medskip
\end{center}


{\bf Problem 1.}

Let $f:[0,1]\to\R$ be a continuous function such that $\int_0^1
f(x)x^n\,dx=0$ for all integers $n\ge 0$. By the Weierstrass theorem,
there exists a sequence of polynomials $\{P_n\}$ converging to $f$ uniformly
over $[0,1]$. We know that $\int_0^1 f(x)P_n(x)\,dx=0$ for every value of
$n$ (because $P_n$ is of the form $P_n(x)=\sum_{k=0}^N c_k x^k$, and each of
the terms leads to an integral equal to zero).

Since $f$ and $P_n$ are bounded over $[0,1]$ (they are continuous and 
$[0,1]$ is compact), and since $P_n\to f$ uniformly, we know that $fP_n$ 
converges uniformly to $f^2$. Indeed, letting $M=\sup_{x\in [0,1]} |f(x)|$
we have $\sup_{x\in [0,1]} |f(x)P_n(x)-f(x)^2|\le M\,\sup_{x\in [0,1]}
|P_n(x)-f(x)|\to 0$ as $n\to +\infty$ (or we can apply the result proved
in the previous problem set).
By Theorem 7.16, the uniform convergence of $fP_n$ to $f^2$ implies that
$\int_0^1 f(x)^2\,dx=\lim_{n\to\infty} \int_0^1 f(x)P_n(x)\,dx=
\lim_{n\to\infty} 0 = 0.$

The function $f^2$ takes non-negative values, is continuous over $[0,1]$,
and $\int_0^1 f^2\,dx=0$. Therefore $f(x)^2=0$ for every $x\in [0,1]$
(see e.g.\ Chapter 6 Exercise 2 and HW7 solutions). Therefore $f=0$.
\medskip

{\bf Problem 2.}

Since $P_{n+1}(x)=P_n(x)+\frac{1}{2}(x^2-P_n^2(x))$, we have the following 
identity: $|x|-P_{n+1}(x)=|x|-P_n(x)-\frac{1}{2}(|x|-P_n(x))(|x|+P_n(x))=
\bigl(|x|-P_n(x)\bigr)\bigl(1-\frac{1}{2}(|x|+P_n(x))\bigr)$\ \ (*). 

We first prove by induction that $0\le P_n(x)\le |x|$ for every $x\in
[-1,1]$. Indeed, the statement is clearly true for $n=0$ since $P_0=0$;
and if $x\in [-1,1]$ and $0\le P_n(x)\le |x|$ then we have
$0\le 1-|x|\le 1-\frac{1}{2}(|x|+P_n(x))\le 1-\frac{1}{2}|x|\le 1$, so
from the identity (*) we get $0\le |x|-P_{n+1}(x)\le |x|-P_n(x)$, i.e.\
$0\le P_n(x)\le P_{n+1}(x)\le |x|$. Therefore, the sequence of functions
$\{P_n\}$ is increasing, and $0\le P_n(x)\le |x|$ $\forall x\in[-1,1]$
for every $n$.

Moreover, for $x\in [-1,1]$ the inequality $0\le 1-\frac{1}{2}(|x|+P_n(x))\le
1-\frac{1}{2}|x|$ and the identity (*) imply that 
$0\le |x|-P_{n+1}(x)\le (|x|-P_n(x))(1-\frac{1}{2}|x|)$; therefore, by
induction on $n$ we get that, for every integer $n\ge 0$ and for every
$x\in [-1,1]$, $0\le |x|-P_n(x)\le (|x|-P_0(x))(1-\frac{1}{2}|x|)^n =
|x|(1-\frac{1}{2}|x|)^n$.

Now define $f(t)=t(1-\frac{1}{2}t)^n$ for $t\in [0,1]$. The function $f$
is differentiable and its derivative is
$f'(t)=(1-\frac{1}{2}t)^n-t\,\frac{n}{2}(1-\frac{1}{2}t)^{n-1}=
(1-\frac{n+1}{2}t)(1-\frac{1}{2}t)^{n-1}$. Observing that
$f'(t)$ has the same sign as $(1-\frac{n+1}{2}t)$ over the interval $[0,1]$,
we get that $f$ is increasing on $[0,\frac{2}{n+1}]$ and decreasing on
$[\frac{2}{n+1},1]$, i.e.\ it reaches its maximum for $t=\frac{2}{n+1}$.
Therefore, $\forall t\in [0,1]$, $f(t)\le f(\frac{2}{n+1}) = \frac{2}{n+1}
(\frac{n}{n+1})^n < \frac{2}{n+1}$. In particular we conclude that,
$\forall x\in [-1,1]$, $0\le |x|-P_n(x)\le f(|x|)< \frac{2}{n+1}$. Since
$\frac{2}{n+1}$ does not depend on $x$ and converges to $0$ as $n\to \infty$,
we conclude that $P_n(x)$ converges to $|x|$ uniformly on the interval $[-1,1]$.
\medskip

{\bf Problem 3.}

Recall that every positive integer can be expressed in a unique way as
a product of prime numbers. Fixing $N$, let $p_1,\dots,p_k$ be all prime
numbers less than $N$, and for $1\le j\le k$ let $m_j$ be the largest
positive integer such that $p_j^{m_j}\le N$. Then every integer between 
$1$ and $N$ can be put in the form $p_1^{r_1}\dots p_k^{r_k}$ for some
integers $r_1,\dots,r_k$ satisfying $0\le r_j\le m_j$. Therefore
$$\sum_{n=1}^N \frac{1}{n}\le \sum_{r_1=0}^{m_1}\dots\sum_{r_k=0}^{m_k}
\frac{1}{p_1^{r_1}\dots p_k^{r_k}} = \prod_{j=1}^k \Bigl(1+\frac{1}{p_j}+
\dots+\frac{1}{p_j^{m_j}}\Bigr)\le \prod_{j=1}^k \Bigl(\sum_{r=0}^\infty
\frac{1}{p_j^r}\Bigr)=\prod_{j=1}^k\frac{1}{1-\frac{1}{p_j}},$$
where we have bounded the partial sum of the $m_j+1$ first terms of the geometric
series $\sum \frac{1}{p_j^r}$ by the total sum $1/(1-\frac{1}{p_j})$.

Next we prove the inequality $1/(1-x)\le e^{2x}$ for all $0\le x\le
\frac{1}{2}$. Indeed, let $\phi(x)=(1-x)e^{2x}$, and observe that
$\phi'(x)=-e^{2x}+2(1-x)e^{2x}=(1-2x)e^{2x}\ge 0$ for all $x\in
[0,\frac{1}{2}]$. Therefore $\phi$ is increasing over $[0,\frac{1}{2}]$,
and since $\phi(0)=1$ we conclude that $\forall x\in [0,\frac{1}{2}]$, 
$\phi(x)\ge 1$, i.e.\ $1/(1-x)\le \exp(2x)$. Applying this for
$x=\frac{1}{p_j}$, we have $1/(1-\frac{1}{p_j})\le \exp(\frac{2}{p_j})$.
Therefore, \vspace{-2.5mm}$$\sum_{n=1}^N \frac{1}{n}\le \prod_{j=1}^k
\frac{1}{1-\frac{1}{p_j}}\le \prod_{j=1}^k e^{2/p_j} = \exp \Bigl(
\sum_{j=1}^k \frac{2}{p_j}\Bigr),\ \ \mbox{which implies that}\ \ 
\sum_{j=1}^k \frac{1}{p_j}\ge \frac{1}{2} \log\Bigl(
\sum_{n=1}^N \frac{1}{n}\Bigr)\vspace{-1mm}$$ by
taking the logarithm of both sides (recall that $\log$ is an increasing
function). Next observe that, because the series $\sum \frac{1}{n}$ is
divergent, the partial sum $\sum_{n=1}^N \frac{1}{n}$ can be made as large
as desired by taking $N$ sufficiently large. Since $\lim_{x\to +\infty}
(\log x)=+\infty$, we conclude that $\log(\sum_{n=1}^N
\frac{1}{n})$ can be made as large as desired. Therefore the
partial sums of the series $\sum_{p\ \mathrm{prime}} \frac{1}{p}$ are
unbounded, i.e.\ the series is divergent.
\medskip

{\bf Problem 4.}
% (bonus +2 points
%if you prove carefully that $f(x)\le \log x\le g(x)$ for every $x\ge 1$).

Observe that $f$ and $g$ are piecewise affine functions, whose graphs
approximate that of the logarithm function: the continuous function
$f$ is affine over all intervals $[m,m+1]$ and coincides with $\log$ at 
all integers; $g$ is affine over all intervals 
$[m-\frac{1}{2},m+\frac{1}{2})$ and its graph is tangent to that of $\log$ 
at all integers (in fact $g$ is discontinuous at $m+\frac{1}{2}$).

For $x\in [m,m+1]$, define $\phi(x)=\log x-f(x)$: 
substituting $x=m$ and $x=m+1$ in the definition of $f$ we get
$\phi(m)=\phi(m+1)=0$. The function $\phi$ is
differentiable over $[m,m+1]$, and $\phi'(x)=\frac{1}{x}-f'(x)=
\frac{1}{x}+\log m-\log (m+1)=\frac{1}{x}-\log(1+\frac{1}{m})$.
Applying the mean value theorem to $\phi$ over $[m,m+1]$, there exists
$\alpha\in (m,m+1)$ such that $\phi(m+1)-\phi(m)=\phi'(\alpha)$, 
i.e.\ $\phi'(\alpha)=\frac{1}{\alpha}-\log(1+\frac{1}{m})=0$.
(This can also be checked directly but the argument given here is simpler). 
Since the function $\phi'$ is decreasing, we have $\phi'\ge 0$ over
$[m,\alpha]$ and $\phi'\le 0$ over $[\alpha,m+1]$, so the function
$\phi$ is increasing over $[m,\alpha]$ and decreasing over $[\alpha,m+1]$.
In particular, since $\phi(m)=\phi(m+1)=0$ we conclude that $\phi(x)\ge 0$,
i.e.\ $f(x)\le \log x$ for every $x\in [m,m+1]$. Since this holds
$\forall m\ge 1$, we have $f(x)\le \log x$ over $[1,+\infty)$.

For $x\in [m-\frac{1}{2},m+\frac{1}{2})$, define $\psi(x)=g(x)-\log x$:
one easily checks that $\psi(m)=0$. The function $\psi$ is differentiable
over $[m-\frac{1}{2},m+\frac{1}{2})$, and $\psi'(x)=g'(x)-\frac{1}{x}=
\frac{1}{m}-\frac{1}{x}$, which is negative for $x<m$ and positive for
$x>m$. Therefore $\psi$ is decreasing over $[m-\frac{1}{2},m]$ and
increasing over $[m,m+\frac{1}{2})$, and so it reaches its minimum at
$m$. We conclude that $\psi(x)\ge \phi(m)=0$, i.e.\ $\log x\le g(x)$
for every $x\in [m-\frac{1}{2},m+\frac{1}{2})$. Since this holds 
$\forall m\ge 1$, we have $\log x\le g(x)$ over
$[\frac{1}{2},+\infty)$.

The definition of $f$ gives $\int_{m}^{m+1} f(x)\,dx=
\bigl[((m+1)x-\frac{1}{2}x^2)\log m+(\frac{1}{2}x^2-mx)\log (m+1)
\bigr]_{m}^{m+1}=\frac{1}{2}\log m+\frac{1}{2}\log (m+1)$ (this can be
obtained directly geometrically). Therefore,
breaking the integral into intervals between consecutive integers we have
$\int_1^n f(x)\,dx=(\frac{1}{2} \log 2)+(\frac{1}{2}\log 2+\frac{1}{2}\log
3)+\dots+(\frac{1}{2}\log (n-1)+\frac{1}{2}\log n)=\log 2+\dots+\log
n-\frac{1}{2}\log n=\log(n!)-\frac{1}{2}\log n$.

Similarly: $\int_{m-\frac{1}{2}}^{m+\frac{1}{2}} g(x)\,dx =
\bigl[\frac{1}{2m}x^2-x+x\log m\bigr]_{m-1/2}^{m+1/2}=\log m$, so
$\int_{\frac{3}{2}}^{n+\frac{1}{2}} g(x)\,dx=\log 2+\dots+\log n=\log(n!)$.
We can also compute $\int_{1}^{3/2} g(x)\,dx=(\frac{9}{8}-\frac{3}{2})-
(\frac{1}{2}-1)=\frac{1}{8}$, and $\int_{n}^{n+\frac{1}{2}} g(x)\,dx>
\frac{1}{2} g(n)=\frac{1}{2}\log n$ (because $g$ is increasing).
So $\int_1^n g(x)\,dx<\int_1^{n+\frac{1}{2}} g(x)\,dx-\frac{1}{2}\log n
=\log(n!)+\frac{1}{8}-\frac{1}{2}\log n$. We conclude that $\int_1^n
f(x)\,dx=\log(n!)-\frac{1}{2}\log n>-\frac{1}{8}+\int_1^n g(x)\,dx$.

Finally, integration by parts (using the functions $\log x$ and $x$) yields
the formula
$\int_1^n \log x\,dx=n\log n-\int_1^n \frac{1}{x}\,x\,dx=n\log n-(n-1)$.
Therefore, since $f(x)\le \log x\le g(x)$ $\forall x\in [1,n]$ we have
$\int_1^n \log x\,dx>\int_1^n f(x)\,dx>-\frac{1}{8}+\int_1^n g(x)\,dx
>-\frac{1}{8}+\int_1^n\log x\,dx$, i.e.\ $n\log
n-(n-1)>\log(n!)-\frac{1}{2}\log n>-\frac{1}{8}+n\log n-(n-1)$. Subtracting
$n\log n-n$ from every term we conclude that $1>\log(n!)-(n+\frac{1}{2})\log
n+n>\frac{7}{8}$, i.e.\ (exponentiating),
$e^{7/8}<n!/(n^n \sqrt{n} e^{-n})<e$.
\end{document}
