\documentclass{article}
\input{18100bpreamble}

\begin{document}
\pset{9}{Dan Ports}{2003/05/09}{drkp@mit.edu}

\begin{ppart}{Problem 1}
Let $f$ be a complex-valued function continuous on $[0,1]$ such that $\int_0^1 f(x)x^n\,dx = 0$ for any $n \in \N$. We show $f(x) = 0$ on $[0,1]$. First, note that any polynomial $P(x)$ can be written $\sum_{i=0}^\infty a_i x^i$ for some set of constants $\{a_i\}$. Then applying theorem 6.12(a),
\[ \int_0^1 f(x) P(x) \, dx = \sum_{i=0}^\infty a_i \int_0^1 f(x) x^i = 0 \]
So the integral of the product of $f$ with any polynomial is zero.
\paragraph{}
Next, note that since $f$ is a continuous function on $[0,1]$, its complex conjugate $\overline{f}$ is also continuous. To see this, note that a complex function can be written as a real part and an imaginary part: $f = a+bi$ for real $a,b$. For $f$ to be continuous, both $a$ and $b$ must be continuous functions; if one were not then we could easily contradict the continuity of $f$. Thus the complex conjugate $\overline{f} = a-bi$ is a linear combination of continuous functions, which is continuous. (Of course, if $f$ is real, $\overline{f} = f$.) Therefore by the Weierstrass approximation theorem there exists a sequence of polynomials $\{P_n\}$ such that $\{P_n\}$ converges uniformly to $\overline{f}$ on $[0,1]$. Then $\{f P_n\}$ converges uniformly to $f\overline{f} = \abs{f}^2$ (via a result from the previous problem set). But since $P_n$ is a polynomial, by the above result $\forall n \: \int_0^1 f(x) P_n(x) \, dx = 0$. By the uniform convergence of $fP_n \to \abs{f}^2$,
\[ \int_0^1 \abs{f}^2(x)\,dx = \lim_{n\to \infty} \int_0^1 f(x) P_n(x) = \lim_{n\to\infty} 0 = 0\]
Thus $\int_0^1 
\abs{f}^2(x)\,dx = 0$. Clearly $\abs{f}^2(x) \ge 0$, so by a result from another previous problem set, $\forall x  \in [0,1] \: \abs{f(x)}^2 = 0$. This requires $\abs{f(x)} = 0$ on the entire interval, which means $\forall x \in [0,1] \: f(x) = 0$. 
\end{ppart}

\begin{ppart}{Problem 2}
Let $P$ be defined by $P_{n+1}(x) = P_n(x) + \frac{x^2-P_n^2(x)}{2}$ and $P_0 = 0$. We show that $\lim_{n \to \infty} P_n(x) = \abs{x}$ uniformly on $[-1,1]$. Applying the recursive definition of $P_{n+1}$, we find
\begin{eqnarray*}
 \abs{x} - P_{n+1}(x) &=& \abs{x} - \left( P_n(x) + \frac{x^2-P_n^2(x)}{2} \right) \\
 &=& \frac{P_n^2(x)}{2} - P_n(x) + \abs{x} - \frac{x^2}{2} \\
 &=& \left[\abs{x} - P_n(x)\right] +  \frac{1}{2}\left[\abs{x}+P_n(x)\right]\left[\abs{x}-P_n(x)\right] \\
 &=& \left[\abs{x} - P_n(x)\right]\left[1 - \frac{\abs{x} + P_n(x)}{2}\right] \\
\end{eqnarray*}
We next show by induction that $\forall n \in \N \; \forall x \in [-1,1] \;\; 0\le P_n(x) \le P_{n+1}(x) \le \abs{x}$. The $n=0$ base case is clearly true because $P_0 = 0$ by definition and $P_1 = \frac{x^2}{2}$. Next assume that for arbitrary $n > 0$, $0\le P_{n-1}(x) \le P_{n}(x) \le \abs{x}$. We will show $0\le P_{n}(x) \le P_{n+1}(x) \le \abs{x}$. Certainly $0\le P_{n}(x) \le \abs{x}$ by the inductive hypothesis, so we need only prove $P_{n}(x) \le P_{n+1}(x) \le \abs{x}$. By the above assumptions, it follows that $0 \le \abs{x}-P_n(x) \le 1$ and $0 \le \frac{\abs{x} + P_n(x)}{2} \le 1$, so $0 \le \left[\abs{x} - P_n(x)\right]\left[1 - \frac{\abs{x} + P_n(x)}{2}\right] \le 1$ and by the identity above, $0 \le \abs{x} - P_{n+1}(x) \le 1$. So we have shown that $P_{n+1}(x) \le \abs{x}$. Next we show that $P_n \le P_{n+1}$. This follows from the definition of $P_{n+1}$: since $P_n(x) \le \abs{x}$, we know $P_n^2 \le x^2$, and $\frac{x^2 - P_n^2(x)}{2} \ge 0$. By definition, $P_{n+1}(x) = P_n(x) + \frac{x^2-P_n^2(x)}{2} \ge P_n$. So we have shown that $0\le P_{n}(x) \le P_{n}(x) \le \abs{x}$. We have proven the inductive hypothesis for $n$, so by induction it is true for all $n \in \N$.
\paragraph{}
Next we show by induction that $\forall n \in \N \; \forall x \in [-1,1] \;\; \abs{x} - P_n(x) \le \abs{x}\left(1-\frac{\abs{x}}{2}\right)^n$. The $n=0$ base case reduces to $\abs{x} \le \abs{x}$, which is trivially true. Now assume that $\abs{x} - P_n(x) \le \abs{x}\left(1-\frac{\abs{x}}{2}\right)^n$. Then consider $\abs{x} - P_{n+1}(x)$
\begin{eqnarray*}
\abs{x} - P_{n+1}(x) &=& \left[\abs{x} - P_n(x)\right]\left[1 - \frac{\abs{x} + P_n(x)}{2}\right] \textrm{  by the identity above} \\
&\le&  \left[ \abs{x} - P_n(x) \right] \left(1 - \frac{\abs{x}}{2}\right) \textrm{   since $P_n(x) \ge 0$} \\
&\le& \abs{x}\left(1-\frac{\abs{x}}{2}\right)^n\left(1 - \frac{\abs{x}}{2}\right) \textrm{   by the inductive hypothesis} \\
&=& \abs{x}\left(1-\frac{\abs{x}}{2}\right)^{n+1}
\end{eqnarray*}
We have proven the inductive hypothesis for $n+1$, so by induction it is true for all $n \in \N$.
\paragraph{}
Next we show, again by induction on $n$, that $\forall n \in N \: \forall x\in[-1,1]\; \abs{x}\left(1-\frac{\abs{x}}{2}\right)^n < \frac{2}{n+1}$. The $n=0$ base case reduces to $\abs{x} < 2$, which is true since $\abs{x} \le 1$. Assume by induction that for some $n$, $\abs{x}\left(1-\frac{\abs{x}}{2}\right)^n < \frac{2}{n+1}$. Then consider 
\begin{eqnarray*}
\abs{x}\left(1-\frac{\abs{x}}{2}\right)^{n+1} &=& \abs{x}\left(1-\frac{\abs{x}}{2}\right)^n\left(1-\frac{\abs{x}}{2}\right) \\
&<& \frac{2}{n+1}\left(1-\frac{\abs{x}}{2}\right) \textrm{   by the inductive hypothesis} \\
&\le& \frac{2}{n+1}\frac{n+1}{n+2} \textrm{   since $\left(1-\frac{\abs{x}}{2}\right) \le \frac{1}{2}$ because $\abs{x} \le 1$, and $\forall n>0 \: \frac{n+1}{n+2} \ge \frac{1}{2}$} \\
&=& \frac{2}{n+2} \\
\end{eqnarray*}
Thus by induction this inequality holds for all $n\in\N$.
\paragraph{}
We have shown that $\abs{x} - P_n(x) < \frac{2}{n+1}$ for $\abs{x} \le 1$. We can use this to show that the series $\{P_n(x)\}$ converges absolutely to $\abs{x}$ on $[-1,1]$: given any $\epsilon > 0$, we will find a $N$ such that $\forall n \ge N \: \forall x \in [-1,1] \; \abs{\abs{x} - P_n(x)} < \epsilon$. Take $N = \frac{2}{\epsilon}$. Then by the inequalities proven above, for all $x$ in this interval, $\abs{\abs{x} - P_n(x)} \le \abs{x} - P_n(x) < \frac{2}{n+1} \le \frac{2}{\frac{2}{\epsilon} + 1} < \epsilon$. Thus $\{P_n(x)\}$ converges absolutely to $\abs{x}$ on $[-1,1]$.
\end{ppart}

\begin{ppart}{Problem 3}
We show that the series $\sum_{\{p\: \textrm{prime}\}} \frac{1}{p}$ diverges. For any fixed $N$, define $p_1, \ldots, p_k$ to be the set of primes that divide at least one integer less than or equal to $N$. Then observe that
\[\sum_{n=1}^N \frac{1}{n} \le \prod_{j=1}^k \left(1 + \frac{1}{p_j} + \frac{1}{p_j^2} + \cdots \right) \]
To see that this inequality holds, note that by the fundamental theorem of arithmetic any integer $n \le N$ has a unique prime factorization: a set of primes $\{p_{i_\alpha}\}$ such that $n = p_{i_1}p_{i_2}p_{i_3}\cdots$ (each prime may be repeated more than once in this factorization). Then $\frac{1}{n} = \frac{1}{p_{i_1}}\frac{1}{p_{i_2}}\cdots$. By our definition of $k$, we need only consider the primes in the set $p_1, \ldots, p_k$ since $n \le N$; i.e. $\forall \alpha \; p_{i_\alpha} \in \{p_1, \ldots, p_k\}$. However, the expansion of the right side of the equation, $\prod_{j=1}^k \left(1 + \frac{1}{p_j} + \frac{1}{p_j^2} + \cdots \right)$ contains the sum of all possible fractions that can be written as a product of the reciprocal of primes drawn from $\{p_1, \ldots, p_k\}$. Thus, the factorization of $\frac{1}{n}$ is contained in the right side of the inequality. Since $n$ was arbitrary, this is true for any $n \le N$. The fundamental theorem of arithmetic guarantees that the prime factorization will be unique, so the prime factorization of every term of $\sum_{n=1}^N \frac{1}{n}$ will be different. We showed that each term is contained in the expansion of the right side of the inequality, so the right side contains every term on the left side. Thus the inequality $\sum_{n=1}^N \frac{1}{n} \le \prod_{j=1}^k \left(1 + \frac{1}{p_j} + \frac{1}{p_j^2} + \cdots \right)$ holds.
\paragraph{}
Next observe that
\[\sum_{n=1}^N \frac{1}{n} \le \prod_{j=1}^k \left(1 + \frac{1}{p_j} + \frac{1}{p_j^2} + \cdots \right) = \prod_{j=1}^k \left(1-\frac{1}{p_j}\right)^{-1}\]
Each term of the product is simply the sum of an infinite geometric series. Since each prime $p_j$ is greater than one, its reciprocal is less than one, and each series converges to the value given above.
\paragraph{}
Next we note that on the domain $[0,\frac{1}{2}]$, $\frac{1}{1-x} \le e^{2x}$. To prove this, consider the derivative of $e^{2x} - \frac{1}{1-x}$, which is $2e^{2x} + \frac{1}{(x-1)^2}$. This derivative is certainly positive, and since $e^{0} = 1 = \frac{1}{1-0}$, we know $e^{2x} \ge \frac{1}{1-x}$ on $[0,\frac{1}{2}]$. Every prime $p_j$ is greater than 2, so $0 < \left(1-\frac{1}{p_j}\right)^{-1} \le \frac{1}{2}$. Thus we can apply the inequality we just proved to show that
\[\sum_{n=1}^N \frac{1}{n} \le \prod_{j=1}^k \left(1-\frac{1}{p_j}\right)^{-1} \le \prod_{j=1}^k e^{\frac{2}{p_j}} = e^{\sum_{j=1}^k \frac{2}{p_j}}\]
(The final step is an application of the properties of the exponential function.)
\paragraph{}
Finally, we use this to show that the sum over all primes of $\frac{1}{p}$ diverges. Given any $K \in \R$, we will show that $\sum_{\{p\: \textrm{prime}\}} \frac{1}{p} > K$. We apply the divergence of the harmonic series to find a value of $N$ such that $\sum_{n=1}^N \frac{1}{n} > e^K$. Then, letting $p_1, \ldots, p_k$ be the set of primes that divide at least one integer less than or equal to $N$, we have shown that $e^K < \sum_{n=1}^N \frac{1}{n} < e^{\sum_{j=1}^k \frac{2}{p_j}}$. By the monotonicity of the exponential function, this can only be the case if $\sum_{j=1}^k \frac{2}{p_j} > K$. Certainly the set $\{p_j\}$ is a subset of the primes, and all primes are positive, so the sum over all primes will be greater than the sum over $\{p_j\}$ which is greater than $K$. So $\sum_{\{p\: \textrm{prime}\}} \frac{1}{p}$ diverges.
\end{ppart}

\begin{ppart}{Problem 4}
Consider the function $f$ defined by $f(x) = (m+1-x)\log m + (x-m)\log(m+1)$, for $m \in \N, m \le x < m+1$, or equivalently $f(x) = (\lfloor x \rfloor + 1 - x) \log \lfloor x \rfloor + (x - \lfloor x \rfloor) \log (\lfloor x \rfloor + 1)$. Also, define the function $g$ by $g(x) = \frac{x}{m} - 1 + \log m$ for $m \in \N, m - \frac{1}{2} \le x < m + \frac{1}{2}$, which is equivalent to $g(x) = \frac{x}{\lfloor x + \frac{1}{2} \rfloor} -1 + \log (\lfloor x + \frac{1}{2} \rfloor)$. A plot of $f$, $g$, and $\log x$ is attached.
\paragraph{}
We show that $f(x) \le \log x \le g(x)$. We will first show that this is true on all intervals $[k,k+\frac{1}{2})$ with $k \in \J$. First, note that the inequality holds at $x=k$: there $\lfloor k \rfloor = \lfloor k + \frac{1}{2} \rfloor = k$. Then $f(k)$ and $g(k)$ both reduce to $\log k$, so $f(k) \le \log k \le g(k)$. On this interval, $\lfloor k \rfloor$ does not change. So $f'(x) = -\log \lfloor x \rfloor + \log (\lfloor x \rfloor + 1) = \log(\frac{\lfloor x \rfloor +1}{\lfloor x \rfloor })$. This is less than the derivative of $\log x$, $\frac{1}{x}$, whenever $x \ge 1$. Thus, $f(x) \le \log x$ on any interval  $[k,k+\frac{1}{2})$. Now consider the derivative $g'(x) = \frac{1}{\lfloor x + \frac{1}{2} \rfloor} \ge \frac{1}{x}$ since $\lfloor x + \frac{1}{2} \rfloor = \lfloor x \rfloor \le x$ on this interval. Thus we have shown that on this interval $f(x) \le \log x \le g(x)$.
\paragraph{}
Next we show the same result on intervals of the form $[k+\frac{1}{2},k+1)$ ($k \in \J$). Note that $f(k+\frac{1}{2}) = \frac{1}{2} \log k + \frac{1}{2} \log (k+1)$, and $g(k + \frac{1}{2}) = \frac{k+\frac{1}{2}}{k+1} - 1 + \log(k+1)$. Thus $f(k+\frac{1}{2}) = \log(\sqrt{k}\sqrt{k+1}) < \log(\frac{k+k+1}{2}) = \log(k+\frac{1}{2})$ (the inequality follows from the arithmetic-mean/geometric-mean inequality and the monotonicity of the logarithm). Furthermore, $\log(\frac{k+1}{k+\frac{1}{2}}) - \frac{1}{2(k+1)} > 0$ so $g(k+\frac{1}{2}) = \log(k+1) - \frac{1}{2(k+1)} > \log(k+\frac{1}{2})$. Thus $f(k+\frac{1}{2}) \le \log(k+\frac{1}{2}) \le g(k+\frac{1}{2})$. On this interval, $f'(x) = \log(\frac{\lfloor x \rfloor +1}{\lfloor x \rfloor })$, which is everywhere less than $(\log x)' = \frac{1}{x}$ on these intervals. Thus, $f(x) \le \log x$ on any interval $[k+\frac{1}{2}, k+1)$. Note also that on these intervals $g'(x) = \frac{1}{\lfloor x + \frac{1}{2} \rfloor} = \frac{1}{k+1} \le \frac{1}{x}$.  Thus we have also shown that $\log x \le g(x)$ on these intervals. So on the union of both classes of intervals, which is the set of points $x \ge 1$, we have shown $f(x) \le \log x \le g(x)$.
\paragraph{}
Next we show that (for integer $n$), $\int_1^n f(x)\,dx = \log(n!) - \frac{1}{2} \log n$. We will do so by dividing the interval $[1,n]$ into a sequence of intervals of length 1: $[1,2], [2,3], \ldots , [n-1,n]$ and integrating over each one separately. So we need to find 
\begin{eqnarray*}
\int_k^{k+1} f(x)\,dx &=& \int_k^{k+1} (\lfloor x \rfloor + 1) \log \lfloor x \rfloor - x \log \lfloor x \rfloor + x \log (\lfloor x \rfloor +1) - \lfloor x \rfloor \log (\lfloor x \rfloor + 1) \, dx \\
&=& \int_k^{k+1} (k+1) \log k - x \log k + x \log (k+1) - k \log (k+1) \\ 
&=& \left[\left(k+1\right) - \left(k+\frac{1}{2}\right)\right]\log k + \left[\left(-k\right) + \left(k+\frac{1}{2}\right)\right]\log(k+1) \\
&=& \frac{1}{2} \log k + \frac{1}{2} \log (k+1)
\end{eqnarray*}
Therefore, we can sum these to find the integral:
\[\int_1^n f(x)\,dx = \sum_{k=1}^{n-1} \frac{1}{2} \log k + \frac{1}{2} \log (k+1) = \left(\sum_{k=1}^{n-1} \log k\right) + \frac{1}{2} \log n = \left(\sum_{k=1}^{n} \log k\right) - \frac{1}{2} \log n\]
Applying the properties of the logarithm,
\[\int_1^n f(x)\,dx = \left(\sum_{k=1}^{n} \log k\right) - \frac{1}{2} \log n = \log\left(\prod_{k=1}^n k\right) - \frac{1}{2} \log n = \log(n!) - \frac{1}{2} \log n\]
\paragraph{}
Now we will integrate $g(x)$ over the interval $[1,n]$. We will use the same type of strategy, dividing it into intervals of length 1: $[1+\frac{1}{2}, 2+\frac{1}{2}], \ldots, [n-1-\frac{1}{2}, n-\frac{1}{2}]$, as well as the two smaller intervals $[1,1+\frac{1}{2}]$ and $[n-\frac{1}{2}, n]$. So we will need to find the integral from $k+\frac{1}{2}$ to $k+1+\frac{1}{2}$:
\[\int_{k+\frac{1}{2}}^{k+1+\frac{1}{2}} g(x) \, dx = \int_{k+\frac{1}{2}}^{k+1+\frac{1}{2}} \frac{x}{k+1} - 1 + \log (k+1) \, dx = \frac{k+1}{k+1} - 1 + \log (k+1) = \log (k+1)\]
We will also need the integrals over the two smaller intervals:
\begin{eqnarray*}
\int_1^{1+\frac{1}{2}} g(x) \, dx &=& \int_1^{1+\frac{1}{2}} \frac{x}{1} - 1 + \log 1\,dx = \frac{1}{8} \\
\int_{n-\frac{1}{2}}^n g(x) \, dx &=& \int_{n-\frac{1}{2}}^n \frac{x}{n} -1 + \log n = \frac{1}{2} \log n - \frac{1}{8n} \\
\end{eqnarray*}
To find the integral over the full interval, we sum over the subintervals:
\begin{eqnarray*}
\int_1^n g(x) \, dx &=& \frac{1}{8} + \sum_{k=1}^{n-2} \log (k+1) + \frac{1}{2} \log n - \frac{1}{8n} \\
&=& \sum_{k=1}^{n} \log (k) - \frac{1}{2} \log n + \frac{1}{8} - \frac{1}{8n} \\
&=& \log(n!) - \frac{1}{2} \log n + \frac{1}{8} - \frac{1}{8n}
\end{eqnarray*}
We can therefore see that $\int_1^n f(x)\,dx > \int_1^n g(x)\,dx - \frac{1}{8}$:
\begin{eqnarray*}
\int_1^n f(x)\,dx - \int_1^n g(x)\,dx + \frac{1}{8} &=& \log(n!) - \frac{1}{2} \log n - \left(\log(n!) - \frac{1}{2} \log n + \frac{1}{8} - \frac{1}{8n}\right) + \frac{1}{8} \\
&=& -\frac{1}{8} + \frac{n}{8} + \frac{1}{8} \; = \frac{1}{8n}
\end{eqnarray*}
This is clearly greater than zero for $x \ge 1$, so $\int_1^n f(x)\,dx > \int_1^n g(x)\,dx - \frac{1}{8}$.
\paragraph{}
Next, note that using integration by parts, we find that $\int_1^n \log x \, dx = n \log n - n + 1$. We proved above that $\forall x \ge 1 \; f(x) \le \log x \le g(x)$. Therefore, by theorem 6.12(b), we know $\int_1^n f(x)\,dx \le \int_1^n \log x \,dx \le \int_1^n g(x)\,dx$. Therefore:
\begin{eqnarray*}
\int_1^n \log x \,dx &\le& \int_1^n g(x)\,dx \\
n \log n -n +1 &\le& \log(n!) - \frac{1}{2} \log n + \frac{1}{8} + \frac{1}{8n} \\
n \log n -n +1  &<& \log(n!) - \frac{1}{2} \log n + \frac{1}{8}\\
\frac{7}{8} &<& \log(n!) - (n+\frac{1}{2}) \log n +n
\end{eqnarray*}
Moreover, since we know $ \int_1^n g(x)\,dx -\frac{1}{8} <\int_1^n f(x)\,dx \le \int_1^n \log x$,
\begin{eqnarray*}
\int_1^n g(x)\,dx - \frac{1}{8} &<& \int_1^n \log x  \\
\log(n!) - \frac{1}{2} \log n + \frac{1}{8n}  &<& n \log n -n +1 \\
\log(n!) - \frac{1}{2} \log n &<& n \log n -n +1 \\
\log(n!) - (n+\frac{1}{2}) \log n +n &<& 1 \\
\end{eqnarray*}
So, combining these two inequalities, we have shown
\[\frac{7}{8} < \log(n!) - (n+\frac{1}{2}) \log n +n < 1\]
Exponentiating each side of the inequality (which is valid since the exponential function is monotonically increasing), we finally arrive at the desired approximation to Stirling's formula:
\[e^{\frac{7}{8}} < \frac{n!}{\left(\frac{n}{e}\right)^n \sqrt{n}} < e\]

\end{ppart}
\end{document}