\documentclass{article}
\usepackage{amsmath,amsthm,amssymb,fancyhdr,epic,eepic,multicol,graphicx}

\renewcommand{\baselinestretch}{1.1}

\theoremstyle{plain}
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem*{answer}{Answer}

\newcommand{\bp}{\begin{problem}}
\newcommand{\ep}{\end{problem}}
\newcommand{\ba}{\begin{answer}}
\newcommand{\ea}{\end{answer}}
\newcommand{\ds}{\displaystyle}
\newcommand{\ben}{\renewcommand{\theenumi}{\alph{enumi}}\renewcommand{\labelenumi}{(\theenumi)}\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}

\fancyhead[L]{\Large \textbf{Math 157 Fall 2013}}
\fancyhead[R]{\large \textbf{Homework 5 - selected answers}}



\begin{document}
\pagestyle{fancy}
\fancyfoot[R,L,C]{}

\bp Read the rest of chapter I (through page 43).
\ep

% \bp True or False:  
% \ben
% \item $\ds \forall n\in \N \exists m \in \N ( 2^n >m )$
% \item $\ds \forall \epsilon >0 \exists n\in \N \left (
%   \frac{1}{2^n}<\epsilon \right)$
% \item $\ds \forall x\in \R \forall y \in \R \exists z \in \R (x+y=z).$
% \item $\ds \forall x\in \R \forall y \in \R \exists z \in \R (x+z=y).$
% \item $\ds \forall x\in \R \exists z \in \R \forall y \in \R (x+z=y).$
% \item $\ds \forall x\in \R \forall y\in \R ((x\leq y )\wedge (y\leq x)
%   \Rightarrow x=y )$
% \een
% \ep


\bp Find the least upper bound of the set
$\left\{\frac{1}{2},\frac{2}{3},\frac{3}{4},\ldots \right\}$.  Prove
your answer.
\ba $1$ is the least upper bound for this set.  Every element of this
set has the form $\frac{n}{n+1}$ for some $n\in \N$.  Since $n<n+1$,
$\frac{n}{n+1}<\frac{n+1}{n+1}=1$, so $1$ is an upper bound.  To see
that $1$ is the least upper bound, let $x<1$.  We will show that $x$
is not an upper bound for this set.  Note that $\frac{x}{1-x}$ is a
real number, so by the Archimidean property,
there is a natural number $$n>\frac{x}{1-x}=\frac{1}{1-x}-\frac{1-x}{1-x}=\frac{1}{1-x}-1.$$  Then
$$n+1>\frac{1}{1-x}\Rightarrow \frac{1}{n+1}<1-x.$$ Subtracting a
smaller number from yields a larger result so
$$1-\frac{1}{n+1}>1-(1-x)=x.$$  Since $1-\frac{1}{n+1}=\frac{n}{n+1}$,
we've shown that
$$\frac{n}{n+1}>x.$$
Thus, any number $x<1$ is not an upper bound for the given set.  
\ea
\ep


\bp True or False:
\ben
\item $p\Rightarrow (q \vee r) \equiv (p \wedge \neg q )\Rightarrow r$
\item $(p \wedge q)\Rightarrow r \equiv (p \wedge \neg r)\Rightarrow
  \neg q.$
\een
\ep

\bp Prove that 
$$\text{If }a,b,c >0\text{ and }a+b+c=1\text{ then }(1-a)(1-b)(1-c)\geq
8abc.$$
\ba
First note that for any $x,y\in \R$, we have 
$(x+y)^2\geq 4xy$ since $(x+y)^2-4xy=(x-y)^2\geq 0$.  Dividing by $4$ and taking square
roots yields
$$\frac{x+y}{2} \geq \sqrt{xy}.$$
Now, begin with  $(1-a)(1-b)(1-c) $ and use $a+b+c=1$ to get
\begin{align*}
(1-a)(1-b)(1-c) & = (b+c)(a+c)(a+b)\\
&= 8
\left(\frac{b+c}{2}\right)\left(\frac{a+c}{2}\right)\left(\frac{a+b}{2}\right)\\
&\geq 8\sqrt{bc}\sqrt{ac}\sqrt{ab}\\
&=8abc
\end{align*}

  
\ea
\ep

\bp $n!$ may be defined inductively for $n=0,1,2,\ldots$ by 
\begin{itemize}
\item $0!=1$ and
\item $n!=n\times (n-1)!$
\end{itemize}
For $n,k =0,1,2,\ldots$, define $\binom{n}{k}$ by
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$
Prove that $$\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}.$$
\ba We give a direct proof using the definition:
\begin{align*}
\binom{n}{k-1}+\binom{n}{k} & =
\frac{n!}{(n-k+1)!(k-1)!}+\frac{n!}{(n-k!)k!}\\
&=\frac{(n!)(k)+(n!)(n-k+1)}{(n-k+1)!k!}\\
&=\frac{(n!)(n+1)}{(n-k+1)!k!}\\
&=\frac{(n+1)!}{n+1-k)!(k!)}\\
&=\binom{n+1}{k!}.
\end{align*}
\ea
\ep

\bp Prove that for all $x\in \R$, $0\leq |x|-x \leq 2|x|.$
\ep

\bp Prove that for all $n\in \N$, $\ds \sum_{k=1}^n 2k-1=n^2$.
\ba We use a proof by induction.  For $n=1$, the statement is that
$2(1)-1=1^2$, which is true.

Now assume that $\ds \sum_{k=1}^n 2k-1=n^2$.  Consider $\ds
\sum_{k=1}^{n+1} 2k-1$:
\begin{align*}
\sum_{k=1}^{n+1} 2k-1 & = \left(\sum_{k=1}^{n} 2k-1 \right) + \left( 2(n+1)-1\right)\\
& = n^2 + 2(n+1)-1\\
&= n^2+2n+1 \\
&=(n+1)^2
\end{align*}
This completes a proof by mathematical induction.

\ea
\ep

\end{document}